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

DOI:

https://doi.org/10.46586/tosc.v2024.i1.158-187

Keywords:

Hash Function, Meet-in-the-middle Attack, AES-like, Nostradamus Attack

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(PS) 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( 3n · 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.

Downloads

Published

2024-03-01

Issue

Section

Articles

How to Cite

Improved Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing. (2024). IACR Transactions on Symmetric Cryptology, 2024(1), 158-187. https://doi.org/10.46586/tosc.v2024.i1.158-187