From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc2994.txt | 563 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 563 insertions(+) create mode 100644 doc/rfc/rfc2994.txt (limited to 'doc/rfc/rfc2994.txt') diff --git a/doc/rfc/rfc2994.txt b/doc/rfc/rfc2994.txt new file mode 100644 index 0000000..6f24b60 --- /dev/null +++ b/doc/rfc/rfc2994.txt @@ -0,0 +1,563 @@ + + + + + + +Network Working Group H. Ohta +Request for Comments: 2994 M. Matsui +Category: Informational Mitsubishi Electric Corporation + November 2000 + + + A Description of the MISTY1 Encryption Algorithm + +Status of this Memo + + This memo provides information for the Internet community. It does + not specify an Internet standard of any kind. Distribution of this + memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (2000). All Rights Reserved. + +Abstract + + This document describes a secret-key cryptosystem MISTY1, which is + block cipher with a 128-bit key, a 64-bit block and a variable number + of rounds. It documents the algorithm description including key + scheduling part and data randomizing part. + +1. Introduction + + This document describes a secret-key cryptosystem MISTY1, which is + block cipher with a 128-bit key, a 64-bit block and a variable number + of rounds. It is designed on the basis of the theory of provable + security against differential and linear cryptanalysis, and moreover + it realizes high-speed encryption on hardware platforms as well as on + software environments. As the result of weighing strength and speed, + 8-rounds of MISTY1 is recommended and used in most cases. + + Our implementation shows that MISTY1 with eight rounds can encrypt a + data stream in CBC mode at a speed of 57Mbps and 40Mbps on Pentium + II/266MHz and PA-7200/120MHz, respectively. For its hardware + performance, we have produced a prototype LSI by a process of 0.8- + micron CMOS gate-array and confirmed a speed of 512Mbps. + +2. Algorithm Description + + Algorithm [1] could be divided into two parts, namely "key scheduling + part" and "data randomizing part". Key scheduling part takes a 128- + bit input key and produces a 128-bit expanded key. Data randomizing + + + + + +Ohta & Matsui Informational [Page 1] + +RFC 2994 MISTY1 November 2000 + + + part takes a 64-bit input data and mixes it, namely encryption. If + data randomizing part is processed in reverse order, mixed data is + transformed to input data, namely decryption. + +2.1 Terminology + + Some operators are used in this document to describe the algorithm. + The operator `+' indicates two's complement addition. The operator + `*' indicates multiplication. The operator `/' yields the quotient, + and the operator `%' yields the remainder from the division. The + operator `&' indicates bitwise AND operation. The operator `|' + indicates bitwise inclusive OR operation. The operator `^' indicates + bitwise exclusive OR operation. The operator `<<' indicates bitwise + left shift operation. The operator `>>' indicates bitwise right + shift operation. + +2.2 Key Scheduling Part + + Key scheduling part consists of the following operations. + + for i = 0, ..., 7 do + EK[i] = K[i*2]*256 + K[i*2+1]; + for i = 0, ..., 7 do + begin + EK[i+ 8] = FI(EK[i], EK[(i+1)%8]); + EK[i+16] = EK[i+8] & 0x1ff; + EK[i+24] = EK[i+8] >> 9; + end + + K is an input key, and each element of K, namely K[i], holds an 8-bit + of the key, respectively. EK denotes an expanded key, and each + element of EK, namely EK[i], holds a 16-bit of the expanded key. + Input data of K[0], ..., K[15] are copied to EK[0], ..., EK[7]. + Expanded key is produced from EK[0], ..., EK[7] by using function FI, + and stored in EK[8], ..., EK[15]. Function FI is described in the + following section. + +2.3 Data Randomizing Part + + Data randomizing part uses two kinds of function, which are called + function FO and function FL. Function FO calls another function, + namely FI. The key expansion part also uses function FI. Function + FI uses two S-boxes, namely S7, S9. Each function is described as + follows. + + Function FO takes two parameters. One is a 32-bit width input data, + namely FO_IN. The other is an index of EK, namely k. And FO returns + a 32-bit width data, namely FO_OUT. + + + +Ohta & Matsui Informational [Page 2] + +RFC 2994 MISTY1 November 2000 + + + FO(FO_IN, k) + begin + var t0, t1 as 16-bit integer; + t0 = FO_IN >> 16; + t1 = FO_IN & 0xffff; + t0 = t0 ^ EK[k]; + t0 = FI(t0, EK[(k+5)%8+8]); + t0 = t0 ^ t1; + t1 = t1 ^ EK[(k+2)%8]; + t1 = FI(t1, EK[(k+1)%8+8]); + t1 = t1 ^ t0; + t0 = t0 ^ EK[(k+7)%8]; + t0 = FI(t0, EK[(k+3)%8+8]); + t0 = t0 ^ t1; + t1 = t1 ^ EK[(k+4)%8]; + FO_OUT = (t1<<16) | t0; + return FO_OUT; + end. + + Function FI takes two parameters. One is a 16-bit width input data, + namely FI_IN. The other is a part of EK, namely FI_KEY, which is + also 16-bit width. And FI returns a 16-bit width data, namely + FI_OUT. + + FI(FI_IN, FI_KEY) + begin + var d9 as 9-bit integer; + var d7 as 7-bit integer; + d9 = FI_IN >> 7; + d7 = FI_IN & 0x7f; + d9 = S9TABLE[d9] ^ d7; + d7 = S7TABLE[d7] ^ d9; + ( d7 = d7 & 0x7f; ) + d7 = d7 ^ (FI_KEY >> 9); + d9 = d9 ^ (FI_KEY & 0x1ff); + d9 = S9TABLE[d9] ^ d7; + FI_OUT = (d7<<9) | d9; + return FI_OUT; + end. + + S7TABLE and S9TABLE denote the S-boxes S7 and S9 respectively in + terms of look up table notation. Here are the description of S7TABLE + and S9TABLE in hexadecimal notation. + + + + + + + + +Ohta & Matsui Informational [Page 3] + +RFC 2994 MISTY1 November 2000 + + + S7TABLE: + 0 1 2 3 4 5 6 7 8 9 a b c d e f + 00: 1b 32 33 5a 3b 10 17 54 5b 1a 72 73 6b 2c 66 49 + 10: 1f 24 13 6c 37 2e 3f 4a 5d 0f 40 56 25 51 1c 04 + 20: 0b 46 20 0d 7b 35 44 42 2b 1e 41 14 4b 79 15 6f + 30: 0e 55 09 36 74 0c 67 53 28 0a 7e 38 02 07 60 29 + 40: 19 12 65 2f 30 39 08 68 5f 78 2a 4c 64 45 75 3d + 50: 59 48 03 57 7c 4f 62 3c 1d 21 5e 27 6a 70 4d 3a + 60: 01 6d 6e 63 18 77 23 05 26 76 00 31 2d 7a 7f 61 + 70: 50 22 11 06 47 16 52 4e 71 3e 69 43 34 5c 58 7d + + S9TABLE: + 0 1 2 3 4 5 6 7 8 9 a b c d e f + 000: 1c3 0cb 153 19f 1e3 0e9 0fb 035 181 0b9 117 1eb 133 009 02d 0d3 + 010: 0c7 14a 037 07e 0eb 164 193 1d8 0a3 11e 055 02c 01d 1a2 163 118 + 020: 14b 152 1d2 00f 02b 030 13a 0e5 111 138 18e 063 0e3 0c8 1f4 01b + 030: 001 09d 0f8 1a0 16d 1f3 01c 146 07d 0d1 082 1ea 183 12d 0f4 19e + 040: 1d3 0dd 1e2 128 1e0 0ec 059 091 011 12f 026 0dc 0b0 18c 10f 1f7 + 050: 0e7 16c 0b6 0f9 0d8 151 101 14c 103 0b8 154 12b 1ae 017 071 00c + 060: 047 058 07f 1a4 134 129 084 15d 19d 1b2 1a3 048 07c 051 1ca 023 + 070: 13d 1a7 165 03b 042 0da 192 0ce 0c1 06b 09f 1f1 12c 184 0fa 196 + 080: 1e1 169 17d 031 180 10a 094 1da 186 13e 11c 060 175 1cf 067 119 + 090: 065 068 099 150 008 007 17c 0b7 024 019 0de 127 0db 0e4 1a9 052 + 0a0: 109 090 19c 1c1 028 1b3 135 16a 176 0df 1e5 188 0c5 16e 1de 1b1 + 0b0: 0c3 1df 036 0ee 1ee 0f0 093 049 09a 1b6 069 081 125 00b 05e 0b4 + 0c0: 149 1c7 174 03e 13b 1b7 08e 1c6 0ae 010 095 1ef 04e 0f2 1fd 085 + 0d0: 0fd 0f6 0a0 16f 083 08a 156 09b 13c 107 167 098 1d0 1e9 003 1fe + 0e0: 0bd 122 089 0d2 18f 012 033 06a 142 0ed 170 11b 0e2 14f 158 131 + 0f0: 147 05d 113 1cd 079 161 1a5 179 09e 1b4 0cc 022 132 01a 0e8 004 + 100: 187 1ed 197 039 1bf 1d7 027 18b 0c6 09c 0d0 14e 06c 034 1f2 06e + 110: 0ca 025 0ba 191 0fe 013 106 02f 1ad 172 1db 0c0 10b 1d6 0f5 1ec + 120: 10d 076 114 1ab 075 10c 1e4 159 054 11f 04b 0c4 1be 0f7 029 0a4 + 130: 00e 1f0 077 04d 17a 086 08b 0b3 171 0bf 10e 104 097 15b 160 168 + 140: 0d7 0bb 066 1ce 0fc 092 1c5 06f 016 04a 0a1 139 0af 0f1 190 00a + 150: 1aa 143 17b 056 18d 166 0d4 1fb 14d 194 19a 087 1f8 123 0a7 1b8 + 160: 141 03c 1f9 140 02a 155 11a 1a1 198 0d5 126 1af 061 12e 157 1dc + 170: 072 18a 0aa 096 115 0ef 045 07b 08d 145 053 05f 178 0b2 02e 020 + 180: 1d5 03f 1c9 1e7 1ac 044 038 014 0b1 16b 0ab 0b5 05a 182 1c8 1d4 + 190: 018 177 064 0cf 06d 100 199 130 15a 005 120 1bb 1bd 0e0 04f 0d6 + 1a0: 13f 1c4 12a 015 006 0ff 19b 0a6 043 088 050 15f 1e8 121 073 17e + 1b0: 0bc 0c2 0c9 173 189 1f5 074 1cc 1e6 1a8 195 01f 041 00d 1ba 032 + 1c0: 03d 1d1 080 0a8 057 1b9 162 148 0d9 105 062 07a 021 1ff 112 108 + 1d0: 1c0 0a9 11d 1b0 1a6 0cd 0f3 05c 102 05b 1d9 144 1f6 0ad 0a5 03a + 1e0: 1cb 136 17f 046 0e1 01e 1dd 0e6 137 1fa 185 08c 08f 040 1b5 0be + 1f0: 078 000 0ac 110 15e 124 002 1bc 0a2 0ea 070 1fc 116 15c 04c 1c2 + + + + + + +Ohta & Matsui Informational [Page 4] + +RFC 2994 MISTY1 November 2000 + + + Function FL takes two parameters. One is a 32-bit data, namely + FL_IN. The other is an index of EK, namely k. And FL returns a 32- + bit width data, namely FL_OUT. + + FL(FL_IN, k) + begin + var d0, d1 as 16-bit integer; + d0 = FL_IN >> 16; + d1 = FL_IN & 0xffff; + if (k is an even number) then + d1 = d1 ^ (d0 & EK[k/2]); + d0 = d0 ^ (d1 | EK[(k/2+6)%8+8]); + else + d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8]); + d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8]); + endif + FL_OUT = (d0<<16) | d1; + return FL_OUT; + end. + + When the algorithm is used for decryption, function FLINV is used + instead of function FL. + + FLINV(FL_IN, k) + begin + var d0, d1 as 16-bit integer; + d0 = FL_IN >> 16; + d1 = FL_IN & 0xffff; + if (k is an even number) then + d0 = d0 ^ (d1 | EK[(k/2+6)%8+8]); + d1 = d1 ^ (d0 & EK[k/2]); + else + d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8]); + d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8]); + endif + FL_OUT = (d0<<16) | d1; + return FL_OUT; + end. + + In most cases, data randomizing part consists of 8 "rounds". Round + contains the call of function FO. Additionally, even-number round + includes the calls of function FL. After the final round, FLs are + called again. The detail description is as follows. + + 64-bit plaintext P is divided into the leftmost 32-bit D0 and the + rightmost 32-bit D1. + + + + + +Ohta & Matsui Informational [Page 5] + +RFC 2994 MISTY1 November 2000 + + + // 0 round + D0 = FL(D0, 0); + D1 = FL(D1, 1); + D1 = D1 ^ FO(D0, 0); + // 1 round + D0 = D0 ^ FO(D1, 1); + // 2 round + D0 = FL(D0, 2); + D1 = FL(D1, 3); + D1 = D1 ^ FO(D0, 2); + // 3 round + D0 = D0 ^ FO(D1, 3); + // 4 round + D0 = FL(D0, 4); + D1 = FL(D1, 5); + D1 = D1 ^ FO(D0, 4); + // 5 round + D0 = D0 ^ FO(D1, 5); + // 6 round + D0 = FL(D0, 6); + D1 = FL(D1, 7); + D1 = D1 ^ FO(D0, 6); + // 7 round + D0 = D0 ^ FO(D1, 7); + // final + D0 = FL(D0, 8); + D1 = FL(D1, 9); + + 64-bit ciphertext C is constructed from D0 and D1 as following + operation. + + C = (D1<<32) | D0; + + When data randomizing part is used as decrypting operation, it should + be executed in reverse order. The detail description is as follows. + + D0 = C & 0xffffffff; + D1 = C >> 32; + D0 = FLINV(D0, 8); + D1 = FLINV(D1, 9); + D0 = D0 ^ FO(D1, 7); + D1 = D1 ^ FO(D0, 6); + D0 = FLINV(D0, 6); + D1 = FLINV(D1, 7); + D0 = D0 ^ FO(D1, 5); + D1 = D1 ^ FO(D0, 4); + D0 = FLINV(D0, 4); + D1 = FLINV(D1, 5); + + + +Ohta & Matsui Informational [Page 6] + +RFC 2994 MISTY1 November 2000 + + + D0 = D0 ^ FO(D1, 3); + D1 = D1 ^ FO(D0, 2); + D0 = FLINV(D0, 2); + D1 = FLINV(D1, 3); + D0 = D0 ^ FO(D1, 1); + D1 = D1 ^ FO(D0, 0); + D0 = FLINV(D0, 0); + D1 = FLINV(D1, 1); + P = (D0<<32) | D1; + +3. Object Identifier + + The Object Identifier for MISTY1 in Cipher Block Chaining (CBC) mode + is as follows: + + MISTY1-CBC OBJECT IDENTIFIER ::= + {iso(1) member-body(2) jisc(392) + mitsubishi-electric-corporation(200011) isl(61) security(1) + algorithm(1) symmetric-encryption-algorithm(1) misty1-cbc(1)} + + MISTY1-CBC needs Initialization Vector (IV) as like as other + algorithms, such as DES-CBC, DES-EDE3-CBC and so on. To determine + the value of IV, MISTY1-CBC takes parameter as: + + MISTY1-CBC Parameter ::= IV + + where IV ::= OCTET STRING -- 8 octets. + + When this Object Identifier is used, plaintext is padded before + encrypt it. At least 1 padding octet is appended at the end of the + plaintext to make the length of the plaintext to the multiple of 8 + octets. The value of these octets is as same as the number of + appended octets. (e.g., If 5 octets are needed to pad, the value is + 0x05.) + +4. Security Considerations + + The algorithm, which is described in this document, is designed in + consideration of the theory of provable security against differential + cryptanalysis and linear cryptanalysis [2][3][4]. According to the + recent result, when the algorithm consists of 8 rounds, both + differential characteristic probability and liner characteristic + probability are 2^-140. For reference, probabilities of DES are 2^- + 62 and 2^-46, respectively. + + + + + + + +Ohta & Matsui Informational [Page 7] + +RFC 2994 MISTY1 November 2000 + + +5. Legal Issues + + The algorithm description is applied for a patent in several + countries as PCT/JP96/02154. However, the algorithm is freely + available for academic (non-profit) use. Additionally, the algorithm + can be used for commercial use without paying the patent fee if you + contract with Mitsubishi Electric Corporation. For more information, + please contact at MISTY@isl.melco.co.jp. + +6. References + + [1] M. Matsui, "New Block Encryption Algorithm MISTY", Fast Software + Encryption - 4th International Workshop (FSE'97), LNCS 1267, + Springer Verlag, 1997, pp.54-68 + + [2] K. Nyberg and L.R. Knudsen, "Provable Security Against a + Differential Attack", Journal of Cryptology, Vol.8, No.1, 1995, + pp. 27-37 + + [3] K. Nyberg, "Linear Approximation of Block Ciphers", Advances in + Cryptology - Eurocrypt'94, LNCS 950, Springer Verlag, 1995, + pp.439-444 + + [4] M. Matsui, "New Structure of Block Ciphers with Provable + Security Against Differential and Linear Cryptanalysis", Fast + Software Encryption - Third International Workshop, LNCS 1039, + Springer Verlag, 1996, pp.205-218 + +7. Authors' Addresses + + Hidenori Ohta + Mitsubishi Electric Corporation, Information Technology R&D Center + 5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan + + Phone: +81-467-41-2183 + Fax: +81-467-41-2185 + EMail: hidenori@iss.isl.melco.co.jp + + + Mitsuru Matsui + Mitsubishi Electric Corporation, Information Technology R&D Center + 5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan + + Phone: +81-467-41-2181 + Fax: +81-467-41-2185 + EMail: matsui@iss.isl.melco.co.jp + + + + + +Ohta & Matsui Informational [Page 8] + +RFC 2994 MISTY1 November 2000 + + +Appendix A. Example Data of MISTY1 + + Here is an example ciphertext of MISTY1 when the key and the + plaintext are set as following value. + + Key: 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff + Plaintext: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 + Ciphertext: 8b 1d a5 f5 6a b3 d0 7c 04 b6 82 40 b1 3b e9 5d + + In the above example, because the plaintext has a length of 128-bit, + MISTY1 is used two times to each 64-bit, namely ECB mode. + + Following example is ciphertext of MISTY1 in CBC mode. + + Key: 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff + IV: 01 02 03 04 05 06 07 08 + Plaintext: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 + Ciphertext: 46 1c 1e 87 9c 18 c2 7f b9 ad f2 d8 0c 89 03 1f + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Ohta & Matsui Informational [Page 9] + +RFC 2994 MISTY1 November 2000 + + +Full Copyright Statement + + Copyright (C) The Internet Society (2000). All Rights Reserved. + + This document and translations of it may be copied and furnished to + others, and derivative works that comment on or otherwise explain it + or assist in its implementation may be prepared, copied, published + and distributed, in whole or in part, without restriction of any + kind, provided that the above copyright notice and this paragraph are + included on all such copies and derivative works. However, this + document itself may not be modified in any way, such as by removing + the copyright notice or references to the Internet Society or other + Internet organizations, except as needed for the purpose of + developing Internet standards in which case the procedures for + copyrights defined in the Internet Standards process must be + followed, or as required to translate it into languages other than + English. + + The limited permissions granted above are perpetual and will not be + revoked by the Internet Society or its successors or assigns. + + This document and the information contained herein is provided on an + "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING + TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING + BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION + HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF + MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + + + + + + + + + + + + + +Ohta & Matsui Informational [Page 10] + -- cgit v1.2.3