Estimating Differential-Linear Distinguishers and Applications to CTC2

At FSE 2014, Blondeau

et al.

proposed an exact expression of the bias of differential-linear approximation and a multidimensional generalization of differential-linear distinguisher. In this paper, we study the application of the theory to concrete designs. We first propose a meet-in-the-middle style searching-and-estimating process. Then, we show that the capacity of a multiple differential distinguisher using

χ

2

statistical test can be written as the summation of squared correlations of several differential-linear distinguishers. This link provides us with another approach to estimating the theoretical capacity of multiple differential distinguisher.

We apply the above methods to CTC2. CTC2 was designed by Courtois to show the strength of algebraic cryptanalysis on block ciphers. For CTC2 with a 255-bit block size and key, we give a multiple differential attack against 11-round version, which to our knowledge is the best with respect to the number of attacked rounds. Experimental results firmly verify the correctness of the proposed method. The attack itself, and its potential to be further extended, reveals that the resistance of CTC2 against statistical attacks may be much weaker than expected before.