CryptoDB
Diving Deep into the Preimage Security of AES-like Hashing
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2024 |
| Abstract: | 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. |
BibTeX
@inproceedings{eurocrypt-2024-33916,
title={Diving Deep into the Preimage Security of AES-like Hashing},
publisher={Springer-Verlag},
author={Shiyao Chen and Jian Guo and Eik List and Danping Shi and Tianyu Zhang},
year=2024
}