Paper 2010/025

New Methodologies for Differential-Linear Cryptanalysis and Its Extensions

Jiqiang Lu

Abstract

In 1994 Langford and Hellman introduced differential-linear cryptanalysis, which involves building a differential-linear distinguisher by concatenating a linear approximation with such a (truncated) differential that with probability 1 does not affect the bit(s) concerned by the input mask of the linear approximation. In 2002 Biham, Dunkelman and Keller presented an enhanced approach to include the case when the differential has a probability smaller than 1; and in 2005 they proposed several extensions of differential-linear cryptanalysis, including the high-order differential-linear analysis, the differential-bilinear analysis and the differential-bilinear-boomerang analysis. In this paper, we show that Biham et al.'s methodologies for computing the probabilities of a differential-linear distinguisher, a high-order differential-linear distinguisher, a differential-bilinear distinguisher and a differential-bilinear-boomerang distinguisher do not have the generality to describe the analytic techniques. Thus the previous cryptanalytic results obtained by using these techniques of Biham et al. are questionable. Finally, from a mathematical point we give general methodologies for computing the probabilities. The new methodologies lead to some better cryptanalytic results, for example, differential-linear attacks on 13-round DES and 10-round CTC2 with a 255-bit block size and key.