CryptoDB
Differential-Linear Cryptanalysis from an Algebraic Perspective
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | CRYPTO 2021 |
| Abstract: | The differential-linear cryptanalysis is an important cryptanalytic tool in cryptography, and has been extensively researched since its discovery by Langford and Hellman in 1994. There are nevertheless very few methods to study the middle part where the differential and linear trail connect, besides the Differential-Linear Connectivity Table (Bar-On et al., EUROCRYPT 2019) and the experimental approach. In this paper, we study differential-linear cryptanalysis from an algebraic perspective. We first introduce a technique called Differential Algebraic Transitional Form (DATF) for differential-linear cryptanalysis, then develop a new theory of estimation of the differential-linear bias and techniques for key recovery in differential-linear cryptanalysis. The techniques are applied to the CAESAR finalist ASCON, the AES finalist SERPENT, and the eSTREAM finalist Grain v1. The bias of the differential-linear approximation is estimated for ASCON and SERPENT. The theoretical estimates of the bias are more accurate than that obtained by the DLCT, and the techniques can be applied with more rounds. Our general techniques can also be used to estimate the bias of Grain v1 in differential cryptanalysis, and have a markedly better performance than the Differential Engine tool tailor-made for the cipher. The improved key recovery attacks on round-reduced variants of these ciphers are then proposed. To the best of our knowledge, they are thus far the best known cryptanalysis of SERPENT, as well as the best differential-linear cryptanalysis of ASCON and the best initialization analysis of Grain v1. The results have been fully verified by experiments. Notably, security analysis of SERPENT is one of the most important applications of differential-linear cryptanalysis in the last two decades. The results in this paper update the differential-linear cryptanalysis of SERPENT-128 and SERPENT-256 with one more round after the work of Biham, Dunkelman and Keller in 2003. |
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31188,
title={Differential-Linear Cryptanalysis from an Algebraic Perspective},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84252-9_9},
author={Meicheng Liu and Xiaojuan Lu and Dongdai Lin},
year=2021
}