International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Xiaoyang Dong , Institute for Network Sciences and Cyberspace, BNRist, Tsinghua University, Beijing, China; State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China; Zhongguancun Laboratory, Beijing, China; Shandong Institute of Blockchain, Jinan, China
Jian Guo , Nanyang Technological University, Singapore, Singapore
Shun Li , School of Cryptology, University of Chinese Academy of Sciences, Beijing, China; Nanyang Technological University, Singapore, Singapore
Phuong Pham , Nanyang Technological University, Singapore, Singapore
Tianyu Zhang , Nanyang Technological University, Singapore, Singapore
Download:
DOI: 10.46586/tosc.v2024.i1.158-187
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11405
Search ePrint
Search Google
Abstract: 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(√n · 22n/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(√n · 22n/3) to O( 3√n · 23n/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.
BibTeX
@article{tosc-2024-34014,
  title={Improved Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={024 No. 1},
  pages={158-187},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11405},
  doi={10.46586/tosc.v2024.i1.158-187},
  author={Xiaoyang Dong and Jian Guo and Shun Li and Phuong Pham and Tianyu Zhang},
  year=2024
}