MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan, and is recognized internationally as a European NESSIE-recommended cipher and an ISO standard. After almost 20 years of unsuccessful cryptanalytic attempts, a first attack on the full MISTY1 was presented at CRYPTO 2015 by Yosuke Todo. The attack, using a new technique called division property, requires almost the full codebook and has time complexity of 2~(107.3) encryptions. In this paper we present a new attack on the full MISTY1. It is based on Todo's division property, along with a variety of refined key-recovery techniques. Our attack requires almost the full codebook (like Todo's attack), but allows to retrieve 49 bits of the secret key in time complexity of only 2~(64) encryptions, and the full key in time complexity of 2~(69.5) encryptions. While our attack is clearly impractical due to its large data complexity, it shows that MISTY1 provides security of only 2~(70) - significantly less than what was considered before.
展开▼
