Zero correlation linear cryptanalysis with reduced data complexity. (English) Zbl 1282.94035

Canteaut, Anne (ed.), Fast software encryption. 19th international workshop, FSE 2012, Washington, DC, USA, March 19–21, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34046-8/pbk). Lecture Notes in Computer Science 7549, 29-48 (2012).
Summary: Zero correlation linear cryptanalysis is a novel key recovery technique for block ciphers proposed in [A. Bogdanov and V. Rijmen, Zero correlation linear cryptanalysis of block ciphers. IACR Eprint Archive Report 2011/123 (March 2011) https://eprint.iacr.org/2011/123]. It is based on linear approximations with probability of exactly 1/2 (which corresponds to the zero correlation). Some block ciphers turn out to have multiple linear approximations with correlation zero for each key over a considerable number of rounds. Zero correlation linear cryptanalysis is the counterpart of impossible differential cryptanalysis in the domain of linear cryptanalysis, though having many technical distinctions and sometimes resulting in stronger attacks.
In this paper, we propose a statistical technique to significantly reduce the data complexity using the high number of zero correlation linear approximations available. We also identify zero correlation linear approximations for 14 and 15 rounds of TEA and XTEA. Those result in key-recovery attacks for 21-round TEA and 25-round XTEA, while requiring less data than the full code book. In the single secret key setting, these are structural attacks breaking the highest number of rounds for both ciphers.
The findings of this paper demonstrate that the prohibitive data complexity requirements are not inherent in the zero correlation linear cryptanalysis and can be overcome. Moreover, our results suggest that zero correlation linear cryptanalysis can actually break more rounds than the best known impossible differential cryptanalysis does for relevant block ciphers. This might make a security re-evaluation of some ciphers necessary in the view of the new attack.
For the entire collection see [Zbl 1251.68005].


94A60 Cryptography


Full Text: DOI