Welcome to the resource topic for 2022/1335
Title:
Revisiting Higher-Order Differential(-Linear) Attacks from an Algebraic Perspective – Applications to Ascon, Grain v1, Xoodoo, and ChaCha
Authors: Kai Hu, Thomas Peyrin
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.
ePrint: https://eprint.iacr.org/2022/1335
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .