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