Paper 2022/189

Simplified MITM Modeling for Permutations: New (Quantum) Attacks

André Schrottenloher, Centrum Wiskunde & Informatica
Marc Stevens, Centrum Wiskunde & Informatica
Abstract

Meet-in-the-middle (MITM) is a general paradigm where internal states are computed along two independent paths ('forwards' and 'backwards') that are 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 such attacks. This has led to the use of detailed attack models for generic solvers to automatically search for improved attacks, notably a MILP model developed by Bao et al. at EUROCRYPT 2021. In this paper, we study a simpler MILP modeling combining a greatly reduced attack representation as input to the generic solver, together with a theoretical analysis that, for any solution, proves the existence and complexity of a detailed attack. This modeling allows to find both classical and quantum attacks on a broad class of cryptographic permutations. First, Present-like constructions, with the permutations of the Spongent hash functions: we improve the MITM step in distinguishers by up to 3 rounds. Second, AES-like designs: despite being much simpler than Bao et al.'s, our model allows to recover the best previous results. The only limitation is that we do not use degrees of freedom from the key schedule. Third, we show that the model can be extended to target more permutations, like Feistel networks. In this context we give new Guess-and-determine attacks on reduced Simpira v2 and Sparkle. Finally, using our model, we find several new quantum preimage and pseudo-preimage attacks (e.g. Haraka v2, Simpira v2 ... ) targeting the same number of rounds as the classical attacks.

Note: Full version of the paper.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
MITM Attacks Permutation-based hashing Preimage attacks Merging algorithms Quantum cryptanalysis.
Contact author(s)
andre schrottenloher @ cwi nl
marc stevens @ cwi nl
History
2022-06-10: revised
2022-02-20: received
See all versions
Short URL
https://ia.cr/2022/189
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/189,
      author = {André Schrottenloher and Marc Stevens},
      title = {Simplified MITM Modeling for Permutations: New (Quantum) Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2022/189},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/189}},
      url = {https://eprint.iacr.org/2022/189}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.