Paper 2025/1632

Enhancing the DATF Technique in Differential-Linear Cryptanalysis

Abstract

Differential-linear cryptanalysis was introduced by Langford and Hellman at CRYPTO'94 and has been an important cryptanalysis method against symmetric-key primitives. The current primary framework for constructing differential-linear distinguishers involves dividing the cipher into three parts: the differential part $E_0$, the middle connection part $E_m$, and the linear part $E_1$. This framework was first proposed at EUROCRYPT 2019, where DLCT was introduced to evaluate the differential-linear bias of $E_m$ over a single round. Recently, the TDT method and the generalized DLCT method were proposed at CRYPTO 2024 to evaluate the differential-linear bias of $E_m$ covering multiple rounds. Unlike the DLCT framework, the DATF technique could also handle $E_m$ covering more rounds. In this paper, we enhance the DATF technique in differential-linear cryptanalysis from three perspectives. First, we improve the precision of differential-linear bias estimation by introducing new transitional rules, a backtracking strategy, and a partitioning technique to DATF. Second, we present a general bias computation method for Boolean functions that significantly reduces computational complexity compared to the exhaustive search used by Liu et al. in the previous DATF technique. Third, we propose an effective method for searching for differential-linear distinguishers with good biases based on DATF. Additionally, the bias computation method has independent interests with a wide application in other cryptanalysis methods, such as differential cryptanalysis and cube attacks. Notably, all these enhancements to DATF are equally applicable to HATF. To show the validity and versatility of our new techniques, we apply the enhanced DATF to the NIST standard Ascon, the AES finalist Serpent, the NIST LWC finalist Xoodyak, and the eSTREAM finalist Grain v1. In all applications, we either present the first differential-linear distinguishers for more rounds or update the best-known ones.