You are looking at a specific version 20200906:073140 of this paper. See the latest version.

Paper 2020/1030

Quantum Collision Attacks on AES-like Hashing with Low Quantum Random Access Memories

Xiaoyang Dong and Siwei Sun and Danping Shi and Fei Gao and Xiaoyun Wang and Lei Hu

Abstract

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum attack on hash functions --- a quantum version of the rebound attack exploiting differentials whose probabilities are too low to be useful in the classical setting. This work opens up a new perspective toward the security of hash functions against quantum attacks. In particular, it tells us that the search for differentials should not stop at the classical birthday bound. Despite these interesting and promising implications, the concrete attacks described by Hosoyamada and Sasaki make use of large quantum random access memories (qRAMs), a resource whose availability in the foreseeable future is controversial even in the quantum computation community. Without large qRAMs, these attacks incur significant increases in time complexities. In this work, we reduce or even avoid the use of qRAMs by performing a quantum rebound attack based on differentials with non-full-active super S-boxes. Along the way, an MILP-based method is proposed to systematically explore the search space of useful truncated differentials with respect to rebound attacks. As a result, we obtain improved attacks on AES-MMO, AES-MP, and the first classical collision attacks on 4- and 5-round Grostl-512. Interestingly, the use of non-full-active super S-box differentials in the analysis of AES-MMO gives rise to new difficulties in collecting enough starting points. To overcome this issue, we consider attacks involving two message blocks to gain more degrees of freedom, and we successfully compress the qRAM demand of the collision attacks on AES-MMO and AES-MP (EUROCRYPT 2020) from $2^{48}$ to a range from $2^{16}$ to $0$, while still maintaining a comparable time complexity. To the best of our knowledge, these are the first dedicated quantum attacks on hash functions that slightly outperform Chailloux, Naya-Plasencia, and Schrottenloher's generic quantum collision attack (ASIACRYPT 2017) in a model where large qRAMs are not available. This work demonstrates again how a clever combination of classical cryptanalytic technique and quantum computation leads to improved attacks, and shows that the direction pointed out by Hosoyamada and Sasaki deserves further investigation.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Keywords
Quantum computationqRAMCollision attacksRebound attacksAES-like hashingMILP
Contact author(s)
xiaoyangdong @ tsinghua edu cn,sunsiwei @ iie ac cn,shidanping @ iie ac cn,gaof @ bupt edu cn,xiaoyunwang @ tsinghua edu cn,hulei @ iie ac cn,siweisun isaac @ gmail com
History
2020-09-06: last of 2 revisions
2020-08-27: received
See all versions
Short URL
https://ia.cr/2020/1030
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.