Weak Keys of the Full MISTY1 Recovered in Practical Time

The MISTY1 is a 64-bit block cipher designed by Matsui in 1997. It is listed on the Japanese CRYPTREC Candidate Recommended Ciphers List. Cryptanalysis against the full MISTY1 has already been known, which is the analysis of weak keys in a related-key setting and the integral attack using the division property in a single-key setting. However, these attacks require large amounts of data and time complexity that are practically infeasible. In this paper, we show the existence of new weak keys for the full MISTY1. The MISTY1 can be distinguished from a random permutation and the keys are recovered with a realistically feasible computational complexity, in a related-key setting. It means that a pair of weak keys, one key of which has a specific differential relationship with the other, is used. The computational complexity of the attacks is \(2^5\) chosen plaintexts for distinguishing the MISTY1 from a random permutation, and \(2^8\) chosen plaintexts, \(2^{25}\) bytes of memory and a few seconds computed by a desktop PC for key recovery.