Title: Meet-in-the-middle Attacks on Permutations: Simplified Cell-based
Modeling and Quantum Attacks
Abstract: Meet-in-the-middle (MITM) is a general cryptanalytic technique
where internal states are computed along two independent paths
(‘forwards’ and ‘backwards’) and then matched. Over time, MITM attacks
improved using more refined techniques and exploiting additional freedoms
and structure, which makes it more involved to find and optimize them.
This has led to the use of detailed attack models for generic solvers to
automatically search for improved attacks.
In this paper, we propose a simple MILP modeling for MITM attacks
on permutations, with applications to preimage attacks on hash functions.
We benefit from a greatly simplified model and a theoretical analysis
that, for any solution, proves the existence of a detailed attack and its
complexity. This model yields new results on several families of constructions.
First, we improve the MITM step in distinguishers on the permutations
of the Spongent hash functions. Second, on AES-based permutation designs,
our model recovers the best previous results despite being much simpler.
The only limitation is that we do not use degrees of freedom from the key
schedule in AES-based hashing. Third, we extend the model to target more
permutations, like Feistel networks. Here we give generic guess-and-determine
distinguishers with complexity 1 which target up to 2/3 of the rounds of Simpira v2,
preimage attacks on reduced versions of Simpira v2 and practical distinguishers
on reduced-round Sparkle permutations.
Finally, we extend our model to find quantum MITM attacks, and we give several
quantum preimage attacks on reduced-round hash functions (e.g. Haraka v2, Simpira v2).
Joint work with Marc Stevens (Cryptology Group, CWI)
Slides:
