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 cipherlinear cryptanalysislinear approximationlinear hullcorrelationevaluation of correlationsubstitution-permutation networkFeistel cipherAESCLEFIA
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2011/123}},
      url = {https://eprint.iacr.org/2011/123}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.