Paper 2015/279

Improved Cryptanalysis of AES-like Permutations

Jérémy Jean, Maria Naya-Plasencia, and Thomas Peyrin

Abstract

AES-based functions have attracted of a lot of analysis in the recent years, mainly due to the SHA-3 hash function competition. In particular, the rebound attack allowed to break several proposals and many improvements/variants of this method have been published. Yet, it remained an open question whether it was possible to reach one more round with this type of technique compared to the state-of-the-art. In this article, we close this open problem by providing a further improvement over the original rebound attack and its variants, that allows the attacker to control one more round in the middle of a differential path for an AES-like permutation. Our algorithm is based on lists merging as defined by Naya-Plasencia at CRYPTO 2011, and we generalized the concept to non-full active truncated differential paths proposed by Sasaki et al. at ASIACRYPT 2010. As an illustration, we applied our method to the internal permutations used in Grostl, one of the five finalist hash functions of the SHA-3 competition. When entering this final phase, the designers tweaked the function so as to thwart attacks proposed by Peyrin at CRYPTO 2010 that exploited relations between the internal permutations. Until our results, no analysis was published on Grostl and the best results reached 8 and 7 rounds for the 256-bit and 512-bit version respectively. By applying our algorithm, we present new internal permutation distinguishers on 9 and 10 rounds respectively.