idnits 2.17.1 draft-ohta-misty1desc-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 7 longer pages, the longest (page 2) being 60 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 1998) is 9447 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '0' is mentioned on line 84, but not defined == Missing Reference: '15' is mentioned on line 85, but not defined == Missing Reference: '7' is mentioned on line 84, but not defined == Missing Reference: '8' is mentioned on line 85, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' Summary: 9 errors (**), 0 flaws (~~), 6 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT H. Ohta 3 Expires in six months M. Matsui 4 Mitsubishi Electric Corporation 5 June 1998 7 A Description of the MISTY1 Encryption Algorithm 9 11 Status of this Memo 13 This document is an Internet-Draft. Internet-Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its areas, 15 and its working groups. Note that other groups may also distribute 16 working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six months 19 and may be updated, replaced, or obsoleted by other documents at any 20 time. It is inappropriate to use Internet- Drafts as reference 21 material or to cite them other than as "work in progress." 23 To view the entire list of current Internet-Drafts, please check 24 the "1id-abstracts.txt" listing contained in the Internet-Drafts 25 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 26 (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 27 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu 28 (US West Coast). 30 1. Introduction 32 This document describes a secret-key cryptosystem MISTY1, which is 33 block cipher with a 128-bit key, a 64-bit block and a variable number 34 of rounds. It is designed on the basis of the theory of provable 35 security against differential and linear cryptanalysis, and moreover 36 it realizes high-speed encryption on hardware platforms as well as on 37 software environments. As the result of weighing strength and speed, 38 8-rounds of MISTY1 is recommended and used in most cases. 40 Our implementation shows that MISTY1 with eight rounds can encrypt a 41 data stream in CBC mode at a speed of 57Mbps and 40Mbps on Pentium 42 II/266MHz and PA-7200/120MHz, respectively. For its hardware 43 performance, we have produced a prototype LSI by a process of 0.8- 44 micron CMOS gate-array and confirmed a speed of 512Mbps. 46 2. Algorithm Description 48 Algorithm [1] could be divided into two parts, namely "key scheduling 49 part" and "data randomizing part". Key scheduling part takes a 128- 50 bit input key and produces a 128-bit expanded key. Data randomizing 51 part takes a 64-bit input data and mixes it, namely encryption. If 52 data randomizing part is processed in reverse order, mixed data is 53 transformed to input data, namely decryption. 55 2.1 Terminology 57 Some operators are used in this document to describe the algorithm. 58 The operator `+' indicates two's complement addition. The operator 59 `*' indicates multiplication. The operator `/' yields the quotient, 60 and the operator `%' yields the remainder from the division. The 61 operator `&' indicates bitwise AND operation. The operator `|' 62 indicates bitwise inclusive OR operation. The operator `^' indicates 63 bitwise exclusive OR operation. The operator `<<' indicates bitwise 64 left shift operation. The operator `>>' indicates bitwise right 65 shift operation. 67 2.2 Key Scheduling Part 69 Key scheduling part consists of the following operations. 71 for i = 0, ..., 7 do 72 EK[i] = K[i*2]*256 + K[i*2+1]; 73 for i = 0, ..., 7 do 74 begin 75 EK[i+ 8] = FI(EK[i], EK[(i+1)%8]); 76 EK[i+16] = EK[i+8] & 0x1ff; 77 EK[i+24] = EK[i+8] >> 9; 78 end 80 K is an input key, and each element of K, namely K[i], holds an 8-bit 81 of the key, respectively. EK denotes an expanded key, and each 82 element of EK, namely EK[i], holds a 16-bit of the expanded key. 83 Input data of K[0], ..., K[15] are copied to EK[0], ..., EK[7]. 84 Expanded key is produced from EK[0], ..., EK[7] by using function FI, 85 and stored in EK[8], ..., EK[15]. Function FI is described in the 86 following section. 88 2.3 Data Randomizing Part 90 Data randomizing part uses two kinds of function, which are called 91 function FO and function FL. Function FO calls another function, 92 namely FI. The key expansion part also uses function FI. Function 93 FI uses two S-boxes, namely S7, S9. Each function is described as 94 follows. 96 Function FO takes two parameters. One is a 32-bit width input data, 97 namely FO_IN. The other is an index of EK, namely k. And FO returns 98 a 32-bit width data, namely FO_OUT. 100 FO(FO_IN, k) 101 begin 102 var t0, t1 as 16-bit integer; 103 t0 = FO_IN >> 16; 104 t1 = FO_IN & 0xffff; 105 t0 = t0 ^ EK[k]; 106 t0 = FI(t0, EK[(k+5)%8+8]); 107 t0 = t0 ^ t1; 108 t1 = t1 ^ EK[(k+2)%8]; 109 t1 = FI(t1, EK[(k+1)%8+8]); 110 t1 = t1 ^ t0; 111 t0 = t0 ^ EK[(k+7)%8]; 112 t0 = FI(t0, EK[(k+3)%8+8]); 113 t0 = t0 ^ t1; 114 t1 = t1 ^ EK[(k+4)%8]; 115 FO_OUT = (t1<<16) | t0; 116 return FO_OUT; 117 end. 119 Function FI takes two parameters. One is a 16-bit width input data, 120 namely FI_IN. The other is a part of EK, namely FI_KEY, which is 121 also 16-bit width. And FI returns a 16-bit width data, namely 122 FI_OUT. 124 FI(FI_IN, FI_KEY) 125 begin 126 var d9 as 9-bit integer; 127 var d7 as 7-bit integer; 128 d9 = FI_IN >> 7; 129 d7 = FI_IN & 0x7f; 130 d9 = S9TABLE[d9] ^ d7; 131 d7 = S7TABLE[d7] ^ d9; 132 ( d7 = d7 & 0x7f; ) 133 d7 = d7 ^ (FI_KEY >> 9); 134 d9 = d9 ^ (FI_KEY & 0x1ff); 135 d9 = S9TABLE[d9] ^ d7; 136 FI_OUT = (d7<<9) | d9; 137 return FI_OUT; 138 end. 140 S7TABLE and S9TABLE denote the S-boxes S7 and S9 respectively in 141 terms of look up table notation. Here are the description of S7TABLE 142 and S9TABLE in hexadecimal notation. 144 S7TABLE: 145 0 1 2 3 4 5 6 7 8 9 a b c d e f 146 00: 1b 32 33 5a 3b 10 17 54 5b 1a 72 73 6b 2c 66 49 147 10: 1f 24 13 6c 37 2e 3f 4a 5d 0f 40 56 25 51 1c 04 148 20: 0b 46 20 0d 7b 35 44 42 2b 1e 41 14 4b 79 15 6f 149 30: 0e 55 09 36 74 0c 67 53 28 0a 7e 38 02 07 60 29 150 40: 19 12 65 2f 30 39 08 68 5f 78 2a 4c 64 45 75 3d 151 50: 59 48 03 57 7c 4f 62 3c 1d 21 5e 27 6a 70 4d 3a 152 60: 01 6d 6e 63 18 77 23 05 26 76 00 31 2d 7a 7f 61 153 70: 50 22 11 06 47 16 52 4e 71 3e 69 43 34 5c 58 7d 155 S9TABLE: 156 0 1 2 3 4 5 6 7 8 9 a b c d e f 157 000: 1c3 0cb 153 19f 1e3 0e9 0fb 035 181 0b9 117 1eb 133 009 02d 0d3 158 010: 0c7 14a 037 07e 0eb 164 193 1d8 0a3 11e 055 02c 01d 1a2 163 118 159 020: 14b 152 1d2 00f 02b 030 13a 0e5 111 138 18e 063 0e3 0c8 1f4 01b 160 030: 001 09d 0f8 1a0 16d 1f3 01c 146 07d 0d1 082 1ea 183 12d 0f4 19e 161 040: 1d3 0dd 1e2 128 1e0 0ec 059 091 011 12f 026 0dc 0b0 18c 10f 1f7 162 050: 0e7 16c 0b6 0f9 0d8 151 101 14c 103 0b8 154 12b 1ae 017 071 00c 163 060: 047 058 07f 1a4 134 129 084 15d 19d 1b2 1a3 048 07c 051 1ca 023 164 070: 13d 1a7 165 03b 042 0da 192 0ce 0c1 06b 09f 1f1 12c 184 0fa 196 165 080: 1e1 169 17d 031 180 10a 094 1da 186 13e 11c 060 175 1cf 067 119 166 090: 065 068 099 150 008 007 17c 0b7 024 019 0de 127 0db 0e4 1a9 052 167 0a0: 109 090 19c 1c1 028 1b3 135 16a 176 0df 1e5 188 0c5 16e 1de 1b1 168 0b0: 0c3 1df 036 0ee 1ee 0f0 093 049 09a 1b6 069 081 125 00b 05e 0b4 169 0c0: 149 1c7 174 03e 13b 1b7 08e 1c6 0ae 010 095 1ef 04e 0f2 1fd 085 170 0d0: 0fd 0f6 0a0 16f 083 08a 156 09b 13c 107 167 098 1d0 1e9 003 1fe 171 0e0: 0bd 122 089 0d2 18f 012 033 06a 142 0ed 170 11b 0e2 14f 158 131 172 0f0: 147 05d 113 1cd 079 161 1a5 179 09e 1b4 0cc 022 132 01a 0e8 004 173 100: 187 1ed 197 039 1bf 1d7 027 18b 0c6 09c 0d0 14e 06c 034 1f2 06e 174 110: 0ca 025 0ba 191 0fe 013 106 02f 1ad 172 1db 0c0 10b 1d6 0f5 1ec 175 120: 10d 076 114 1ab 075 10c 1e4 159 054 11f 04b 0c4 1be 0f7 029 0a4 176 130: 00e 1f0 077 04d 17a 086 08b 0b3 171 0bf 10e 104 097 15b 160 168 177 140: 0d7 0bb 066 1ce 0fc 092 1c5 06f 016 04a 0a1 139 0af 0f1 190 00a 178 150: 1aa 143 17b 056 18d 166 0d4 1fb 14d 194 19a 087 1f8 123 0a7 1b8 179 160: 141 03c 1f9 140 02a 155 11a 1a1 198 0d5 126 1af 061 12e 157 1dc 180 170: 072 18a 0aa 096 115 0ef 045 07b 08d 145 053 05f 178 0b2 02e 020 181 180: 1d5 03f 1c9 1e7 1ac 044 038 014 0b1 16b 0ab 0b5 05a 182 1c8 1d4 182 190: 018 177 064 0cf 06d 100 199 130 15a 005 120 1bb 1bd 0e0 04f 0d6 183 1a0: 13f 1c4 12a 015 006 0ff 19b 0a6 043 088 050 15f 1e8 121 073 17e 184 1b0: 0bc 0c2 0c9 173 189 1f5 074 1cc 1e6 1a8 195 01f 041 00d 1ba 032 185 1c0: 03d 1d1 080 0a8 057 1b9 162 148 0d9 105 062 07a 021 1ff 112 108 186 1d0: 1c0 0a9 11d 1b0 1a6 0cd 0f3 05c 102 05b 1d9 144 1f6 0ad 0a5 03a 187 1e0: 1cb 136 17f 046 0e1 01e 1dd 0e6 137 1fa 185 08c 08f 040 1b5 0be 188 1f0: 078 000 0ac 110 15e 124 002 1bc 0a2 0ea 070 1fc 116 15c 04c 1c2 189 Function FL takes two parameters. One is a 32-bit data, namely 190 FL_IN. The other is an index of EK, namely k. And FL returns a 32- 191 bit width data, namely FL_OUT. 193 FL(FL_IN, k) 194 begin 195 var d0, d1 as 16-bit integer; 196 d0 = FL_IN >> 16; 197 d1 = FL_IN & 0xffff; 198 if (k is an even number) then 199 d1 = d1 ^ (d0 & EK[k/2]); 200 d0 = d0 ^ (d1 | EK[(k/2+6)%8+8]); 201 else 202 d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8]); 203 d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8]); 204 endif 205 FL_OUT = (d0<<16) | d1; 206 return FL_OUT; 207 end. 209 When the algorithm is used for decryption, function FLINV is used 210 instead of function FL. 212 FLINV(FL_IN, k) 213 begin 214 var d0, d1 as 16-bit integer; 215 d0 = FL_IN >> 16; 216 d1 = FL_IN & 0xffff; 217 if (k is an even number) then 218 d0 = d0 ^ (d1 | EK[(k/2+6)%8+8]); 219 d1 = d1 ^ (d0 & EK[k/2]); 220 else 221 d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8]); 222 d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8]); 223 endif 224 FL_OUT = (d0<<16) | d1; 225 return FL_OUT; 226 end. 228 In most cases, data randomizing part consists of 8 "rounds". Round 229 contains the call of function FO. Additionally, even-number round 230 includes the calls of function FL. After the final round, FLs are 231 called again. The detail description is as follows. 233 64-bit plaintext P is divided into the leftmost 32-bit D0 and the 234 rightmost 32-bit D1. 236 // 0 round 237 D0 = FL(D0, 0); 238 D1 = FL(D1, 1); 239 D1 = D1 ^ FO(D0, 0); 240 // 1 round 241 D0 = D0 ^ FO(D1, 1); 242 // 2 round 243 D0 = FL(D0, 2); 244 D1 = FL(D1, 3); 245 D1 = D1 ^ FO(D0, 2); 246 // 3 round 247 D0 = D0 ^ FO(D1, 3); 248 // 4 round 249 D0 = FL(D0, 4); 250 D1 = FL(D1, 5); 251 D1 = D1 ^ FO(D0, 4); 252 // 5 round 253 D0 = D0 ^ FO(D1, 5); 254 // 6 round 255 D0 = FL(D0, 6); 256 D1 = FL(D1, 7); 257 D1 = D1 ^ FO(D0, 6); 258 // 7 round 259 D0 = D0 ^ FO(D1, 7); 260 // final 261 D0 = FL(D0, 8); 262 D1 = FL(D1, 9); 264 64-bit ciphertext C is constructed from D0 and D1 as following 265 operation. 267 C = (D1<<32) | D0; 269 When data randomizing part is used as decrypting operation, it should 270 be executed in reverse order. The detail description is as follows. 272 D0 = C & 0xffffffff; 273 D1 = C >> 32; 274 D0 = FLINV(D0, 8); 275 D1 = FLINV(D1, 9); 276 D0 = D0 ^ FO(D1, 7); 277 D1 = D1 ^ FO(D0, 6); 278 D0 = FLINV(D0, 6); 279 D1 = FLINV(D1, 7); 280 D0 = D0 ^ FO(D1, 5); 281 D1 = D1 ^ FO(D0, 4); 282 D0 = FLINV(D0, 4); 283 D1 = FLINV(D1, 5); 284 D0 = D0 ^ FO(D1, 3); 285 D1 = D1 ^ FO(D0, 2); 286 D0 = FLINV(D0, 2); 287 D1 = FLINV(D1, 3); 288 D0 = D0 ^ FO(D1, 1); 289 D1 = D1 ^ FO(D0, 0); 290 D0 = FLINV(D0, 0); 291 D1 = FLINV(D1, 1); 292 P = (D0<<32) | D1; 294 3. Object Identifier 296 The Object Identifier for MISTY1 in Cipher Block Chaining (CBC) mode 297 is as follows: 299 MISTY1-CBC OBJECT IDENTIFIER ::= 300 {iso(1) member-body(2) jisc(392) 301 mitsubishi-electric-corporation(200011) isl(61) security(1) 302 algorithm(1) symmetric-encryption-algorithm(1) misty1-cbc(1)} 304 MISTY1-CBC needs Initialization Vector (IV) as like as other 305 algorithms, such as DES-CBC, DES-EDE3-CBC and so on. To determine 306 the value of IV, MISTY1-CBC takes parameter as: 308 MISTY1-CBC Parameter ::= IV 310 where IV ::= OCTET STRING -- 8 octets. 312 When this Object Identifier is used, plaintext is padded before 313 encrypt it. At least 1 padding octet is appended at the end of the 314 plaintext to make the length of the plaintext to the multiple of 8 315 octets. The value of these octets is as same as the number of 316 appended octets. (e.g. If 5 octets are needed to pad, the value is 317 0x05.) 319 Security Considerations 321 The algorithm, which is described in this document, is designed in 322 consideration of the theory of provable security against differential 323 cryptanalysis and linear cryptanalysis [2][3][4]. According to the 324 recent result, when the algorithm consists of 8 rounds, both 325 differential characteristic probability and liner characteristic 326 probability are 2^-140. For reference, probabilities of DES are 2^- 327 62 and 2^-46, respectively. 329 Legal Issues 331 The algorithm description is applied for a patent in several 332 countries as PCT/JP96/02154. However, the algorithm is freely 333 available for academic (non-profit) use. 335 References 337 [1] M. Matsui, "New Block Encryption Algorithm MISTY", Fast Software 338 Encryption - 4th International Workshop (FSE'97), LNCS 1267, 339 Springer Verlag, 1997, pp.54-68 341 [2] K. Nyberg and L.R. Knudsen, "Provable Security Against a 342 Differential Attack", Journal of Cryptology, Vol.8, No.1, 1995, 343 pp. 27-37 345 [3] K. Nyberg, "Linear Approximation of Block Ciphers", Advances in 346 Cryptology - Eurocrypt'94, LNCS 950, Springer Verlag, 1995, 347 pp.439-444 349 [4] M. Matsui, "New Structure of Block Ciphers with Provable 350 Security Against Differential and Linear Cryptanalysis", Fast 351 Software Encryption - Third International Workshop, LNCS 1039, 352 Springer Verlag, 1996, pp.205-218 354 Appendix A. Example Data of MISTY1 356 Here is an example ciphertext of MISTY1 when the key and the 357 plaintext are set as following value. 359 Key: 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff 360 Plaintext: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 361 Ciphertext: 8b 1d a5 f5 6a b3 d0 7c 04 b6 82 40 b1 3b e9 5d 363 In the above example, because the plaintext has a length of 128-bit, 364 MISTY1 is used two times to each 64-bit. 366 Author's Addresses 368 Hidenori Ohta 369 Mitsubishi Electric Corporation, Information Technology R&D Center 370 5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan 371 Phone: +81-467-41-2181 372 FAX: +81-467-41-2138 373 EMail: hidenori@iss.isl.melco.co.jp 375 Mitsuru Matsui 376 Mitsubishi Electric Corporation, Information Technology R&D Center 377 5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan 378 Phone: +81-467-41-2181 379 FAX: +81-467-41-2138 380 EMail: matsui@iss.isl.melco.co.jp