Paper 2011/123

Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers

Andrey Bogdanov and Vincent Rijmen


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. A version of this paper to appear in Designs, Codes and Cryptography
block cipherlinear cryptanalysislinear approximationlinear hullcorrelationevaluation of correlationsubstitution-permutation networkFeistel cipherAESCLEFIA
Contact author(s)
andrey bogdanov @ esat kuleuven be
2012-05-11: last of 2 revisions
2011-03-14: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.