Cryptology ePrint Archive: Report 2015/935

Joint Data and Key Distribution of the Linear Cryptanalysis Test Statistic and Its Impact to Data Complexity Estimates of Multiple/Multidimensional Linear and Truncated Differential Attacks

Céline Blondeau and Kaisa Nyberg

Abstract: The power of a statistical attack is inversely proportional to the number of plaintexts necessary 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 such an 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 we differentiate between the attacks which are performed in the known-plaintext and those in the distinct-known-plaintext model. By this differentiation, we improve the data complexity of some attacks by applying the distinct-known-plaintext model. From the analysis provided in this paper, it follows that the number of attacked rounds in the multidimensional linear context is impacted by the fact that the expected capacity of a multidimensional linear approximation for a random permutation is not equal to zero as previously assumed. The impact of the result is relatively important, since it weakens most existing multidimensional linear attacks. From the link between differential and linear cryptanalysis we also derive a new estimate of the data complexity of a truncated differential attack. The theory developed in this paper is backed up by different experiments.

Category / Keywords: multidimensional linear attack, zero-correlation linear

Date: received 24 Sep 2015, last revised 24 Sep 2015

Contact author: kaisa nyberg at aalto fi

Available format(s): PDF | BibTeX Citation

Version: 20150928:172847 (All versions of this report)

Short URL: ia.cr/2015/935

Discussion forum: Show discussion | Start new discussion