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

##### Abstract

The Higher-order Differential-Linear (HDL) attack was introduced by Biham 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, 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}$. 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 improved the distinguishing attacks on 8-round \ascon permutation, with a complexity reduced from $2^{130}$ to $2^{46}$. Also, we provide a new zero-sum distinguisher for the full 12-round Ascon permutation with $2^{55}$ time/data complexity, improving over the previous best one that required $2^{130}$ calls. We highlight that our cryptanalyses do not threaten the security of Ascon or Xoodyak.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Higher-Order DifferentialHigher-Order Differential-LinearAsconXoodyak
Contact author(s)
kai hu @ ntu edu sg
thomas peyrin @ ntu edu sg
quanquan001 @ e ntu edu sg
trevor yap @ ntu edu sg
History
2023-02-17: last of 4 revisions
See all versions
Short URL
https://ia.cr/2022/1335

CC BY

BibTeX

@misc{cryptoeprint:2022/1335,
author = {Kai Hu and Thomas Peyrin and Quan Quan Tan and Trevor Yap},
title = {Revisiting Higher-Order Differential-Linear Attacks from an Algebraic Perspective},
howpublished = {Cryptology ePrint Archive, Paper 2022/1335},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1335}},
url = {https://eprint.iacr.org/2022/1335}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.