Paper 2015/935

Joint Data and Key Distribution of Simple, Multiple, and Multidimensional Linear Cryptanalysis Test Statistic and Its Impact to Data Complexity

Céline Blondeau and Kaisa Nyberg

Abstract

The power of a statistical attack is inversely proportional to the number of plaintexts needed to recover information on the encryption key. By analyzing the distribution of the random variables involved in the attack, cryptographers aim to provide a good estimate of the data complexity of the attack. In this paper, we analyze the hypotheses made in simple, multiple, and multidimensional linear attacks that use either non-zero or zero correlations, and provide more accurate estimates of the data complexity of these attacks. This is achieved by taking, for the first time, into consideration the key variance of the statistic for both the right and wrong keys. For the family of linear attacks considered in this paper, we differentiate between the attacks which are performed in the known-plaintext and those in the distinct-known-plaintext model.

Note: In this revised version, the content has been largely modified. -The key-variance of the statistics for the simple linear cryptanalysis is now described before presenting the models for the multiple and multidimensional linear attacks. In particular, we detail separately the case of linear approximation with single dominant characteristic and the case of several characteristic. This new result was not part of the previous version. -While zero-correlation linear cryptanalysis was before presented as a motivation for this work, we now see it as an application of the general multiple/multidimensional linear case. -In this new version, we only focus on attacks in the linear context. In particular the truncated differential case is not anymore covered. From the link between multidimensional linear attacks and truncated differential attacks, we can still derive an expression of the data complexity of such attack. -The discussion regarding the validity of the attacks on PRESENT has also been removed since we are now working on a better understanding of these attacks.