### Revisiting Higher-Order Differential(-Linear) Attacks from an Algebraic Perspective -- Applications to Ascon, Grain v1, Xoodoo, and ChaCha

##### Abstract

The higher-order differential-linear (HDL) attack was studied for the first time by Biham, Dunkelman, and Keller at FSE 2005, where a linear approximation is appended to a higher-order differential (HD) transition. It is a natural generalization of the differential-linear (DL) attack. Due to some restrictions in practical usage, unfortunately, the HDL cryptanalysis has attracted much less attention compared to its DL counterpart since its proposal. Inspired by the algebraic perspective on DL attacks recently proposed at CRYPTO 2021, in this paper we show that the HDL attack can be made much more practical with an algebraic treatment, turning this 17-year-old attack into another go-to tool for cryptanalysts. Unsurprisingly, HD/HDL attacks have the potential to be more effective than their simpler differential/DL counterpart. We provide three novel methods to detect possible HD/HDL distinguishers, including: (a) an estimation of the algebraic degree of the differential supporting function (DSF); (b) the higher-order algebraic transitional form (HATF); (c) experimental methods based on cube testers. With these methods, we greatly improve the distinguishing attacks on the 8-round Ascon permutation under the black-box model from $2^{130}$ to $2^{46}$. Also, we give a new zero-sum distinguisher for a full 12-round Ascon permutation with only $2^{55}$ time/data complexity, improving over the previous best one that requires $2^{130}$ calls (we make clear that this does not impact the full Ascon AEAD scheme). For the 4-round Ascon initialization, a deterministic 2nd order HDL distinguisher is proposed with only four nonces. Besides the distinguishers, the HATF technique allows us to handle the probabilistic HD/HDL properties of cryptographic primitives. This leads to a conditional HDL attack on 5-round Ascon initialization that can recover all the key bits, and performing 8 times faster than the conditional DL attack. To the best of our knowledge, this is the first theoretical work to propose a probabilistic HDL attack since it was first published.All our attacks in this paper apply to both Ascon-128 and Ascon-128a. We also give a conditional HD approximation for 130-round Grain v1 (reaching 5 more rounds than the previous best conditional differential approximation) and new 4-round deterministic HDL distinguishers for the Xoodoo permutation with only four chosen plaintexts. Finally, we applied our strategy to the ARX-based cipher ChaCha, obtaining 3.5-, 4- and 4.5-round distinguishers and again improving over the state-of-the-art. Our cryptanalyses do not threaten the security of the ciphers mentioned in this paper.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Higher-Order Differential Higher-Order Differential-Linear Ascon Xoodoo Grainv v1 ChaCha
Contact author(s)
kai hu @ ntu edu sg
thomas peyrin @ ntu edu sg
History
2022-10-10: approved
See all versions
Short URL
https://ia.cr/2022/1335

CC BY

BibTeX

@misc{cryptoeprint:2022/1335,
author = {Kai Hu and Thomas Peyrin},
title = {Revisiting Higher-Order Differential(-Linear) Attacks from an Algebraic Perspective -- Applications to Ascon, Grain v1,  Xoodoo, and ChaCha},
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.