Zero correlation linear cryptanalysis with reduced data complexity

Andrey Bogdanov, Meiqin Wang

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


Zero correlation linear cryptanalysis is a novel key recovery technique for block ciphers proposed in [5]. 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. © 2012 Springer-Verlag.
Original languageEnglish
Title of host publicationFast Software Encryption : Revised Selected Papers
PublisherSpringer Verlag
Publication date2012
ISBN (Print)978-3-642-34046-8
ISBN (Electronic)978-3-642-34047-5
Publication statusPublished - 2012
Externally publishedYes
Event19th International Workshop on Fast Software Encryption (FSE 2012) - Washington, United States
Duration: 19 Mar 201221 Mar 2012
Conference number: 19


Workshop19th International Workshop on Fast Software Encryption (FSE 2012)
Country/TerritoryUnited States
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Zero correlation linear cryptanalysis with reduced data complexity'. Together they form a unique fingerprint.

Cite this