Cryptology ePrint Archive: Report 2015/746

A 2^{70} Attack on the Full MISTY1

Achiya Bar-On

Abstract: 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 Todo. The attack, using a new technique called {\it 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 a modified variant of Todo's division property, along with a variety of refined key-recovery techniques. Our attack requires the full codebook, 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.

Category / Keywords: MISTY1,block cipher, division property, integral cryptanalysis, partial sums, integral attack, 2D meet-in-the-middle

Date: received 24 Jul 2015, last revised 30 Jul 2015

Contact author: abo1000 at gmail com, nathan keller27@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150730:114728 (All versions of this report)

Short URL: ia.cr/2015/746

Discussion forum: Show discussion | Start new discussion