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 263.58 and 263.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 (2121 and 2107.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) 263.58 2121
MISTY1 (full round) 263.994 2107.9

  2. Yosuke Todo, “Integral Cryptanalysis on Full MISTY1”, to appear in the proceedings of CRYPTO 2015.
  5. 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.
  6. 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 2128.

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