Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
MISTY1block cipherdivision propertyintegral cryptanalysispartial sumsintegral attack2D meet-in-the-middle
Contact author(s)
abo1000 @ gmail com
nathan keller27 @ gmail com
History
2015-07-30: revised
2015-07-30: received
See all versions
Short URL
https://ia.cr/2015/746
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/746,
      author = {Achiya Bar-On},
      title = {A 2^{70} Attack on the Full MISTY1},
      howpublished = {Cryptology ePrint Archive, Paper 2015/746},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/746}},
      url = {https://eprint.iacr.org/2015/746}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.