Differential-Linear Cryptanalysis Revisited

The two main classes of statistical cryptanalysis are the linear and differential attacks. They have many variants and enhancements such as the multidimensional linear attacks and the truncated differential attacks. The idea of differential-linear cryptanalysis is to apply first a truncated differential attack and then a linear attack on different parts of the cipher and then combine them to a single distinguisher over the cipher. This method is known since 1994 when Langford and Hellman presented the first differential-linear cryptanalysis of the DES. Recently, in 2014, Blondeau and Nyberg presented a general link between differential and linear attacks. In this paper, we apply this link to develop a concise theory of the differential-linear cryptanalysis. The differential-linear attack can be, in the theoretical sense, considered either as a multidimensional linear or a truncated differential attack, but is for both types an extreme case, which is best measured by the differential-linear bias. We give an exact expression of the bias in a closed form under the sole assumption that the two parts of the cipher are independent. Unlike in the case of ordinary differentials and linear approximations, it is not granted that restricting to a subset of characteristics of a differential-linear hull will give a lower bound on the absolute value of the bias. Given this, we revisit the previous treatments of differential-linear bias by Biham et al. in 2002–2003, Liu et al. in 2009, and Lu in 2012, and formulate assumptions under which a single differential-linear characteristic gives a close estimate of the bias. These results are then generalized by considering a subspace of linear approximations over the second part of the cipher. To verify the assumptions made, we present several experiments on a toy-cipher.