Paper 2023/772

Classical and Quantum Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing

Zhiyu Zhang, Institute of Information Engineering, Chinese Academy of Sciences, University of Chinese Academy of Sciences
Siwei Sun, University of Chinese Academy of Sciences, State Key Laboratory of Cryptology
Caibing Wang, Institute of Information Engineering, Chinese Academy of Sciences, University of Chinese Academy of Sciences
Lei Hu, Institute of Information Engineering, Chinese Academy of Sciences, University of Chinese Academy of Sciences
Abstract

At EUROCRYPT 2006, Kelsey and Kohno proposed the so-called chosen target forced-prefix (CTFP) preimage attack, where for any challenge prefix $P$, the attacker can generate a suffix $S$ such that $H(P\|S) = y$ for some hash value $y$ published in advance by the attacker. Consequently, the attacker can pretend to predict some event represented by $P$ she did not know before, and thus this type of attack is also known as the Nostradamus attack. At ASIACRYPT 2022, Benedikt et al. convert Kelsey et al.'s attack to a quantum one, reducing the time complexity from $\mathcal{O}(\sqrt{n}\cdot 2^{2n/3})$ to $\mathcal{O}(\sqrt[3]{n} \cdot 2^{3n/7})$. CTFP preimage attack is less investigated in the literature than (second-)preimage and collision attacks and lacks dedicated methods. In this paper, we propose the first dedicated Nostradamus attack based on the meet-in-the-middle (MITM) attack, and the MITM Nostradamus attack could be up to quadratically accelerated in the quantum setting. According to the recent works on MITM preimage attacks on AES-like hashing, we build an automatic tool to search for optimal MITM Nostradamus attacks and model the tradeoff between the offline and online phases. We apply our method to AES-MMO and Whirlpool, and obtain the first dedicated attack on round-reduced version of these hash functions. Our method and automatic tool are applicable to other AES-like hashings.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2023
Keywords
Meet-in-the-middle AttackCTFP AttackHash FuntionQuantum Attack
Contact author(s)
zhangzhiyu @ iie ac cn
siweisun isaac @ gmail com
wangcaibing @ iie ac cn
hulei @ iie ac cn
History
2023-05-30: approved
2023-05-27: received
See all versions
Short URL
https://ia.cr/2023/772
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/772,
      author = {Zhiyu Zhang and Siwei Sun and Caibing Wang and Lei Hu},
      title = {Classical and Quantum Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/772},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/772}},
      url = {https://eprint.iacr.org/2023/772}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.