International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Revisiting Higher-Order Differential-Linear Attacks from an Algebraic Perspective

Authors:
Kai Hu , Nanyang Technological University
Thomas Peyrin , Nanyang Technological University
Quan Quan Tan , Nanyang Technological University
Trevor Yap Hong Eng , Nanyang Technological University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: The Higher-order Differential-Linear (HDL) attack was introduced by Biham \textit{et al.} at FSE 2005, where a linear approximation was appended to a Higher-order Differential (HD) transition. It is a natural generalization of the Differential-Linear (DL) attack. Due to some practical restrictions, however, HDL cryptanalysis has unfortunately attracted much less attention compared to its DL counterpart since its proposal. In this paper, we revisit HD/HDL cryptanalysis from an algebraic perspective and provide two novel tools for detecting possible HD/HDL distinguishers, including: (a) Higher-order Algebraic Transitional Form (HATF) for probabilistic HD/HDL attacks; (b) Differential Supporting Function (\DSF) for deterministic HD attacks. In general, the HATF can estimate the biases of ℓth-order HDL approximations with complexity O(2ℓ+d2ℓ) where d is the algebraic degree of the function studied. If the function is quadratic, the complexity can be further reduced to O(23.8ℓ). HATF is therefore very useful in HDL cryptanalysis for ciphers with quadratic round functions, such as \ascon and \xoodyak. \DSF provides a convenient way to find good linearizations on the input of a permutation, which facilitates the search for HD distinguishers. Unsurprisingly, HD/HDL attacks have the potential to be more effective than their simpler differential/DL counterparts. Using HATF, we found many HDL approximations for round-reduced \ascon and \xoodyak initializations, with significantly larger biases than DL ones. For instance, there are deterministic 2nd-order/4th-order HDL approximations for \ascon/\xoodyak initializations, respectively (which is believed to be impossible in the simple DL case). We derived highly biased HDL approximations for 5-round \ascon up to 8th order, which improves the complexity of the distinguishing attack on 5-round \ascon from 216 to 212 calls. We also proposed HDL approximations for 6-round \ascon and 5-round \xoodyak (under the single-key model), which couldn't be reached with simple DL so far. For key recovery, HDL attacks are also more efficient than DL attacks, thanks to the larger biases of HDL approximations. Additionally, HATF works well for DL (1st-order HDL) attacks and some well-known DL biases of \ascon and \xoodyak that could only be obtained experimentally before can now be predicted theoretically. With \DSF, we propose a new distinguishing attack on 8-round \ascon permutation, with a complexity of 248. Also, we provide a new zero-sum distinguisher for the full 12-round \ascon permutation with 255 time/data complexity. We highlight that our cryptanalyses do not threaten the security of \ascon or \xoodyak.
BibTeX
@inproceedings{asiacrypt-2023-33478,
  title={Revisiting Higher-Order Differential-Linear Attacks from an Algebraic Perspective},
  publisher={Springer-Verlag},
  author={Kai Hu and Thomas Peyrin and Quan Quan Tan and Trevor Yap Hong Eng},
  year=2023
}