Paper 2015/682

Integral Cryptanalysis on Full MISTY1

Yosuke Todo

Abstract

MISTY1 is a block cipher designed by Matsui in 1997. It was well evaluated and standardized by projects, such as CRYPTREC, ISO/IEC, and NESSIE. In this paper, we propose a key recovery attack on the full MISTY1, i.e., we show that 8-round MISTY1 with 5 FL layers does not have 128-bit security. Many attacks against MISTY1 have been proposed, but there is no attack against the full MISTY1. Therefore, our attack is the first cryptanalysis against the full MISTY1. We construct a new integral characteristic by using the propagation characteristic of the division property, which was proposed in 2015. We first improve the division property by optimizing a public S-box and then construct a 6-round integral characteristic on MISTY1. Finally, we recover the secret key of the full MISTY1 with $2^{63.58}$ chosen plaintexts and $2^{121}$ time complexity. Moreover, if we can use $2^{63.994}$ chosen plaintexts, the time complexity for our attack is reduced to $2^{107.9}$. Note that our cryptanalysis is a theoretical attack. Therefore, the practical use of MISTY1 will not be affected by our attack.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
cryptanalysis
Contact author(s)
todo yosuke @ lab ntt co jp
History
2015-07-07: received
Short URL
https://ia.cr/2015/682
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/682,
      author = {Yosuke Todo},
      title = {Integral Cryptanalysis on Full {MISTY1}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/682},
      year = {2015},
      url = {https://eprint.iacr.org/2015/682}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.