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
-
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}
}
