Paper 2018/182

New Rigorous Analysis of Truncated Differentials for 5-round AES

Lorenzo Grassi and Christian Rechberger

Abstract

Since the development of cryptanalysis of AES and AES-like constructions in the late 1990s, the set of inputs (or a subset of it) which differ only in one diagonal has special importance. It appears in various (truncated) differential, integral, and impossible differential attacks, among others. In this paper we present new techniques to analyze this special set of inputs that is so versatile, and report on new properties. Classically, in differential cryptanalysis, statements about the probability distribution of output differences, like mean or variance, are of interest. So far such statements where only possible for up to 4 rounds of AES. In this paper we consider the probabilistic distribution of the number of different pairs of corresponding ciphertexts that lie in certain subspaces after 5 rounds. We rigorously prove that the following two properties (independent of any key or constant additions) hold for 5 rounds of the AES permutation: – the mean value is bigger for AES than for a random permutation; – the variance is approximately by a factor 36 higher for AES than for a random permutation. While the distinguisher based on the variance is (almost) independent of the details of the S-Box and of the MixColumns matrix, the mean value distinguisher does depend on the details of the S-Box and may give rise to a new design criterion for S-Boxes. Of independent interest is the technique that we developed for this rigorous analysis. To the best of our knowledge this seems to be the first time that such a precise differential analysis was performed. Practical implementations and verification confirm our analysis.