Paper 2015/367

Improved Higher-Order Differential Attacks on 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 an European NESSIE-recommended cipher and an ISO standard. Since its introduction, MISTY1 was subjected to extensive cryptanalytic efforts, yet no attack significantly faster than exhaustive key search is known on its full version. The best currently known attack is a higher-order differential attack presented by Tsunoo et al. in 2012 which breaks a reduced variant of MISTY1 that contains 7 of the 8 rounds and 4 of the 5 $FL$ layers in $2^{49.7}$ data and $2^{116.4}$ time. In this paper, we present improved higher-order differential attacks on reduced-round MISTY1. Our attack on the variant considered by Tsunoo et al. requires roughly the same amount of data and only $2^{100.4}$ time (i.e., is $2^{16}$ times faster). Furthermore, we present the first attack on a MISTY1 variant with 7 rounds and all 5 $FL$ layers, requiring $2^{51.4}$ data and $2^{121}$ time. To achieve our results, we use a new higher-order differential characteristic for 4-round MISTY1, as well as enhanced key recovery algorithms based on the {\it partial sums} technique.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in FSE 2015
Keywords
block cipherMISTY1higher-order differential attackpartial sumsintegral attackKASUMI
Contact author(s)
abo1000 @ gmail com
History
2015-04-23: received
Short URL
https://ia.cr/2015/367
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/367,
      author = {Achiya Bar-On},
      title = {Improved Higher-Order Differential Attacks on MISTY1},
      howpublished = {Cryptology ePrint Archive, Paper 2015/367},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/367}},
      url = {https://eprint.iacr.org/2015/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.