eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2022/1335

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

Kai Hu, Nanyang Technological University
Thomas Peyrin, Nanyang Technological University
Quan Quan Tan, Nanyang Technological University
Trevor Yap, Nanyang Technological University
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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2023
Keywords
Higher-Order DifferentialHigher-Order Differential-LinearAsconXoodyak
Contact author(s)
kai hu sdu @ gmail com
thomas peyrin @ ntu edu sg
quanquan001 @ e ntu edu sg
trevor yap @ ntu edu sg
History
2023-09-20: last of 7 revisions
2022-10-07: received
See all versions
Short URL
https://ia.cr/2022/1335
License
Creative Commons Attribution
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.