Grøstl Distinguishing Attack: A New Rebound Attack of an AES-like Permutation

Abstract

We consider highly structured truncated differential paths to mount a new rebound attack on Grøstl-512, a hash functions based on two AES-like permutations, P₁₀₂₄ and Q₁₀₂₄, with non-square input and output registers. We explain how such differential paths can be computed using a Mixed-Integer Linear Programming approach. Together with a 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. This yields the first distinguishing attack on a 11-round version of P₁₀₂₄ and Q₁₀₂₄ with about 2⁷² computations and a memory complexity of about 2⁵⁶ bytes, to be compared with the 2⁹⁶ computations required by the corresponding generic attack. Previous best results on this permutation reached 10 rounds with a computational complexity of about 2³⁹² operations, to be compared with the 2⁴⁴⁸ computations required by the corresponding generic attack.