International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Zhiyu Zhang , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Siwei Sun , School of Cryptology, University of Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
Caibing Wang , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Lei Hu , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Download:
DOI: 10.46586/tosc.v2023.i2.224-252
URL: https://tosc.iacr.org/index.php/ToSC/article/view/10984
Search ePrint
Search Google
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 O(√n · 22n/3) to O( 3√n · 23n/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.
BibTeX
@article{tosc-2023-33314,
  title={Classical and Quantum Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 2},
  pages={224-252},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/10984},
  doi={10.46586/tosc.v2023.i2.224-252},
  author={Zhiyu Zhang and Siwei Sun and Caibing Wang and Lei Hu},
  year=2023
}