Date Added: Mar 2011
Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This paper 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 2n?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. 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.