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.
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.
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.
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.
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.
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.
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.
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.
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.
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.)
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.
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.
[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
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.