Please use this identifier to cite or link to this item:
Title: Improved meet-in-the-middle Nostradamus attacks on AES-like hashing
Authors: Dong, Xiaoyang
Guo, Jian
Li, Shun
Pham, Phuong
Zhang, Tianyu
Keywords: Mathematical Sciences
Issue Date: 2024
Source: Dong, X., Guo, J., Li, S., Pham, P. & Zhang, T. (2024). Improved meet-in-the-middle Nostradamus attacks on AES-like hashing. IACR Transactions On Symmetric Cryptology, 2024(1), 158-187.
Project: RG93/23 
Journal: IACR Transactions on Symmetric Cryptology 
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.
ISSN: 2519-173X
DOI: 10.46586/tosc.v2024.i1.158-187
Schools: School of Physical and Mathematical Sciences 
Rights: © 2024 The Author(s). Licensed under Creative Commons License CC-BY 4.0.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
ToSC2024_1_06.pdf1.78 MBAdobe PDFThumbnail

Citations 50

Updated on Jul 18, 2024

Page view(s)

Updated on Jul 24, 2024


Updated on Jul 24, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.