Topics

On the Security of 64-bit Block Cipher MISTY1

July 16, 2015
CRYPTREC Cryptographic Technology Evaluation Committee

A new cryptanalytic result on MISTY1, which is a 64-bit block cipher on the CRYPTREC Candidate Recommended Ciphers List^[1], was published. The paper describing a new result^[2] was accepted at CRYPTO 2015^[3], an international conference sponsored by International Association for Cryptologic Research (IACR), and published by the IACR ePrint Archive^[4] before the conference.

The paper shows that a 128-bit secret key of full-round MISTY1 can be recovered with less complexity than that for the key exhaustive search attack (brute force attack) for the first time by reducing the complexity for the integral cryptanalysis. The complexities for the two attacks presented in the paper are shown in the table below. There is a trade-off between the required data and the time complexity.

The required data for the two attacks are as many as 2^63.58 and 2^63.994 pairs of chosen plaintexts and corresponding ciphertexts, respectively. Since there exist at most 264 pairs of plaintexts and ciphertexts for a 64-bit block cipher when the key is fixed, almost all the plaintexts and ciphertexts are required for the attacks. Moreover, the time complexities are huge (2¹²¹ and 2^107.9, respectively). Therefore, these attacks are not considered practical. Further evaluation results will be reported on the CRYPTREC web site.

Table: Complexities of Integral Cryptanalysis on MISTY1 [2]
	Required data^[5]	Time complexity^[6]
MISTY1 (full round)	2^63.58	2¹²¹
MISTY1 (full round)	2^63.994	2^107.9

https://www.cryptrec.go.jp/en/method.html
Yosuke Todo, “Integral Cryptanalysis on Full MISTY1”, to appear in the proceedings of CRYPTO 2015.
http://www.iacr.org/conferences/crypto2015/
https://eprint.iacr.org/2015/682
Unit of the required data is a pair of plaintext block and ciphertext block. Both blocks are 64-bit length. The attacks require chosen plaintexts and their corresponding ciphertexts.
Unit of the time complexity is the computational cost for one block encryption. The time complexity for the key exhaustive search attack for a 128-bit key is 2¹²⁸.

If you have any opinions, comments, or inquiries about this topic, please contact us at the following address.
CRYPTREC Secretariat
E-mail: