On Linear Cryptanalysis with Many Linear Approximations

Benoit Gérard; Jean-Pierre Tillich

Paper 2009/463

On Linear Cryptanalysis with Many Linear Approximations

Benoit Gérard and Jean-Pierre Tillich

Abstract

In this paper we present a theoretical framework to quantify the information brought by several linear approximations of a block-cipher without putting any restriction on these approximations. We quantify here the entropy of the key given the plaintext-ciphertext pairs statistics which is a much more accurate measure than the ones studied earlier. The techniques which are developed here apply to various ways of performing the linear attack and can also been used to measure the entropy of the key for other statistical attacks. Moreover, we present a realistic attack on the full DES with a time complexity of $2^{48}$ for $2^{41}$ pairs what is a big improvement comparing to Matsui's algorithm 2 ($2^{51.9}$).

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. full version of the paper with same title which is going to be published in the proceedings of the 12th IMA Conference on Cryptography and Coding
Contact author(s): jean-pierre tillich @ inria fr
History: 2009-09-20: received
Short URL: https://ia.cr/2009/463
License: CC BY

BibTeX

@misc{cryptoeprint:2009/463,
      author = {Benoit Gérard and Jean-Pierre Tillich},
      title = {On Linear Cryptanalysis with Many Linear Approximations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/463},
      year = {2009},
      url = {https://eprint.iacr.org/2009/463}
}