Cryptology ePrint Archive: Report 2019/256

DLCT: A New Tool for Differential-Linear Cryptanalysis

Achiya Bar-On and Orr Dunkelman and 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.

Category / Keywords: Differential-Linear Cryptanalysis, ICEPOLE, Serpent, ASCON, DES

Original Publication (in the same form): IACR-EUROCRYPT-2019

Date: received 28 Feb 2019, last revised 6 Mar 2019

Contact author: orrd at cs haifa ac il, nkeller at math biu ac il, abo1000 at gmail com, relweiz at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190306:212414 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]