Cryptology ePrint Archive: Report 2017/508

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

Victor Cauchois and 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ø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.

Category / Keywords: Cryptanalysis, Hash function, Rebound attacks, AES-like, Groestl

Date: received 1 Jun 2017

Contact author: victor cauchois at m4x org

Available format(s): PDF | BibTeX Citation

Version: 20170602:163939 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]