Paper 2019/256

DLCT: A New Tool for Differential-Linear Cryptanalysis

Achiya Bar-On, Orr Dunkelman, Nathan Keller, and Ariel Weizman

Abstract

Differential cryptanalysis and linear cryptanalysis are the two best-known techniques for cryptanalysis of block ciphers. In 1994, Langford and Hellman introduced the differential-linear (DL) attack based on dividing the attacked cipher $E$ into two subciphers $E_0$ and $E_1$ and combining a differential characteristic for $E_0$ with a linear approximation for $E_1$ into an attack on the entire cipher $E$. The DL technique was used to mount the best known attacks against numerous ciphers, including the AES finalist Serpent, ICEPOLE, COCONUT98, Chaskey, CTC2, and 8-round DES. Several papers aimed at formalizing the DL attack, and formulating assumptions under which its complexity can be estimated accurately. These culminated in a recent work of Blondeau, Leander, and Nyberg (Journal of Cryptology, 2017) which obtained an accurate expression under the sole assumption that the two subciphers $E_0$ and $E_1$ are independent. In this paper we show that in many cases, dependency between the two subcipher s significantly affects the complexity of the DL attack, and in particular, can be exploited by the adversary to make the attack more efficient. We present the Differential-Linear Connectivity Table (DLCT) which allows us to take into account the dependency between the two subciphers, and to choose the differential characteristic in $E_0$ and the linear approximation in $E_1$ in a way that takes advantage of this dependency. We then show that the DLCT can be constructed efficiently using the Fast Fourier Transform. Finally, we demonstrate the strength of the DLCT by using it to improve differential-linear attacks on ICEPOLE and on 8-round DES, and to explain published experimental results on Serpent and on the CAESAR finalist Ascon which did not comply with the standard differential-linear framework.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2019
Keywords
Differential-Linear CryptanalysisICEPOLESerpentASCONDES
Contact author(s)
orrd @ cs haifa ac il
nkeller @ math biu ac il
abo1000 @ gmail com
relweiz @ gmail com
History
2019-03-06: revised
2019-03-01: received
See all versions
Short URL
https://ia.cr/2019/256
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/256,
      author = {Achiya Bar-On and Orr Dunkelman and Nathan Keller and Ariel Weizman},
      title = {{DLCT}: A New Tool for Differential-Linear Cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/256},
      year = {2019},
      url = {https://eprint.iacr.org/2019/256}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.