Date de l'exposé : 06 janvier 2023
Meet-in-the-middle Attacks on Permutations: Simplified Cell-based Modeling and Quantum Attacks
Joint work with Marc Stevens (Cryptology Group, CWI)
=====================
Meet-in-the-middle (MITM) preimage attacks compute internal states of a hash function along two independent paths ('forwards' and 'backwards') and match these choices to recover a valid (complete) path, which leads to the target hash value. Over time, MITM attacks were improved with more and more refined techniques, which makes it more difficult to find and optimize such attacks. This has led to the development of models for generic solvers to automatically search for improved attacks, notably a MILP model introduced by Bao et al. at EUROCRYPT 2021.
In this work, we propose a simpler MILP modeling of such attacks. The model comes with a theoretical analysis that, for any solution, proves the existence and complexity of a detailed attack. This allows to find both classical and quantum attacks on a broad class of hash functions based on cryptographic permutations. This includes AES-like designs which were studied by Bao et al. (and related works), but also other Substitution-Permutation Networks such as Present and the Spongent hash functions, and Feistel networks.
Apart from recovering previous results, our model allows us to improve classical attacks on the Haraka hash function family. We also find several new quantum preimage and pseudo-preimage attacks targeting the same number of rounds as the classical attacks.
