Paper 2024/352

Improved Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing

Xiaoyang Dong, Tsinghua University
Jian Guo, Nanyang Technological University
Shun Li, University of Chinese Academy of Sciences
Phuong Pham, Nanyang Technological University
Tianyu Zhang, Nanyang Technological University

The Nostradamus attack was originally proposed as a security vulnerability for a hash function by Kelsey and Kohno at EUROCRYPT 2006. It requires the attacker to commit to a hash value y of an iterated hash function H. Subsequently, upon being provided with a message prefix P, the adversary’s task is to identify a suffix S such that H(P||S) equals y. Kelsey and Kohno demonstrated a herding attack requiring $O(\sqrt{n}\cdot 2^{2n/3})$ evaluations of the compression function of H, where n represents the output and state size of the hash, placing this attack between preimage attacks and collision searches in terms of complexity. At ASIACRYPT 2022, Benedikt et al. transform Kelsey and Kohno’s attack into a quantum variant, decreasing the time complexity from $O(\sqrt{n}\cdot 2^{2n/3})$ to $O(\sqrt[3]{n}\cdot 2^{3n/7})$. At ToSC 2023, Zhang et al. proposed the first dedicated Nostradamus attack on AES-like hashing in both classical and quantum settings. In this paper, we have made revisions to the multi-target technique incorporated into the meet-in-the-middle automatic search framework. This modification leads to a decrease in time complexity during the online linking phase, effectively reducing the overall attack time complexity in both classical and quantum scenarios. Specifically, we can achieve more rounds in the classical setting and reduce the time complexity for the same round in the quantum setting.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2024
Hash FunctionMeet-in-the-middle AttackAES-likeNostradamus Attack
Contact author(s)
xiaoyangdong @ tsinghua edu cn
guojian @ ntu edu sg
lishun @ ucas ac cn
pham0079 @ e ntu edu sg
tianyu005 @ e ntu edu sg
2024-03-01: approved
2024-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaoyang Dong and Jian Guo and Shun Li and Phuong Pham and Tianyu Zhang},
      title = {Improved Meet-in-the-Middle Nostradamus Attacks on {AES}-like Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2024/352},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.