International Association
for Cryptologic Research

Since the seminal works by Aoki and Sasaki, meet-in-the-middle (MITM) attacks are known to be effective for preimage and collision attacks of hash functions. At Eurocrypt'21, Bao et al. initiated the automation of such preimage and collision MITM attacks for AES-like hash functions, which brought up models that could capture larger search spaces than what could be studied manually before. Follow-up works then integrated several techniques such as guess-and-determine, bidirectional propagation, and states in superposition. However, this research direction has been far from complete. In previous models, initial states were limited to single independent states and were not allowed to have bytes in superposition. Moreover, S-box inputs in superposition could not be propagated unless the full byte was guessed. Besides more advanced techniques, the general question of how the state-of-the-art results could be improved remained of high interest. In this work, we lift some of these limitations with novel techniques: We introduce the S-box linearization technique for automated MITM preimage attacks so that a superposition of bytes active in both the for- and the backward neutral chunk can pass through an S-box. We propose what we call distributed initial structures that allow more general definitions of initial states from multiple states to enlarge the search space. Beyond those, we exploit the similarity between encryption function and key schedule in constructions such as Whirlpool, and Streebog in our models to reduce the consumed degrees of freedom. To better integrate the proposed techniques, we present a refined and lightweight MILP-based search model. We illustrate the effectiveness of our enhanced MITM framework with improved preimage attacks on hash-function modes of standardized AES-like designs. We obtain the first preimage attacks on 10-round AES-192, 10-round Rijndael-192/256, and 7.75-round Whirlpool. Moreover, we can reduce time or memory complexities for attacks on 5- and 6-round Whirlpool, and 7.5- and 8.5-round Streebog. We show that our model is not limited to preimage attacks with improved collision attacks on 6- and 6.5-round Whirlpool.

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.