summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc2994.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc2994.txt')
-rw-r--r--doc/rfc/rfc2994.txt563
1 files changed, 563 insertions, 0 deletions
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]
+