Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers

Andrey Bogdanov; Vincent Rijmen

Paper 2011/123

Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers

Andrey Bogdanov and Vincent Rijmen

Abstract

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on $n$ bits, an algorithm of complexity $2^{n - 1}$ is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. A version of this paper to appear in Designs, Codes and Cryptography
Keywords: block cipher linear cryptanalysis linear approximation linear hull correlation evaluation of correlation substitution-permutation network Feistel cipher AES CLEFIA
Contact author(s): andrey bogdanov @ esat kuleuven be
History: 2012-05-11: last of 2 revisions; 2011-03-14: received; See all versions
Short URL: https://ia.cr/2011/123
License: CC BY

BibTeX

@misc{cryptoeprint:2011/123,
      author = {Andrey Bogdanov and Vincent Rijmen},
      title = {Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/123},
      year = {2011},
      url = {https://eprint.iacr.org/2011/123}
}