Paper 2017/508

Generalized Distinguishing Attack: A New Cryptanalysis of AES-like Permutations

Victor Cauchois, Clément Gomez, and Reynald Lercier

Abstract

We consider highly structured truncated differential paths to mount rebound attacks on hash functions based on AES-like permutations. We explain how such differential paths can be computed using a Mixed-Integer Linear Programming approach. Together with the SuperSBox description, this allows us to build a rebound attack with a $6$-round inbound phase whereas classical rebound attacks have $4$-round inbound phases. Non-square AES-like permutations seem to be more vulnerable than square ones. We illustrate this new technique by mounting the first distinguishing attack on a $11$-round version of Gr\o{}stl-$512$ internal permutation $P_{1024}$ with $\mathit{O}(2^{72})$ computational complexity and $\mathit{O}(2^{56})$ memory complexity, to be compared with the $\mathit{O} (2^{96})$ required computations of the corresponding generic attack. Previous best results on this permutation reached $10$ rounds with a computational complexity of $\mathit{O}(2^{392})$, to be compared with $\mathit{O}(2^{448})$ required by the corresponding generic attack.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisHash functionRebound attacksAES-likeGroestl
Contact author(s)
victor cauchois @ m4x org
History
2017-06-02: received
Short URL
https://ia.cr/2017/508
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/508,
      author = {Victor Cauchois and Clément Gomez and Reynald Lercier},
      title = {Generalized Distinguishing Attack: A New Cryptanalysis of AES-like Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/508},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/508}},
      url = {https://eprint.iacr.org/2017/508}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.