Paper 2022/1335

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

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 $\ell^{th}$-order HDL approximations with complexity $\mathcal{O}(2^{\ell+d2^\ell})$ where $d$ is the algebraic degree of the function studied. If the function is quadratic, the complexity can be further reduced to $\mathcal{O}(2^{3.8\ell})$. 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 2$^{nd}$-order/4$^{th}$-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 8$^{th}$ order, which improves the complexity of the distinguishing attack on 5-round \ascon from $2^{16}$ to $2^{12}$ 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 (1$^{st}$-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 $2^{48}$. Also, we provide a new zero-sum distinguisher for the full 12-round \ascon permutation with $2^{55}$ time/data complexity. We highlight that our cryptanalyses do not threaten the security of \ascon or \xoodyak.