### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2011/123

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.