Welcome to the resource topic for 2024/1743
Title:
The Window Heuristic: Automating Differential Trail Search in ARX Ciphers with Partial Linearization Trade-offs
Authors: Emanuele Bellini, David GERAULT, Juan Grados, Thomas Peyrin
Abstract:The search for optimal differential trails for ARX ciphers is known to be difficult and scale poorly as the word size (and the branching through the carries of modular additions) increases.To overcome this problem, one may approximate the modular addition with the XOR operation, a process called linearization. The immediate drawback of this approach is that many valid and good trails are discarded. In this work, we explore different partial linearization trade-offs to model the modular addition through the \emph{window heuristic}, which restricts carry propagation to windows of w_s consecutive positions. This strategy
enables the exploration of full linearization (w_s = 0), normal modelling (w_s = n), and all the different trade-offs between completeness and speed in between.
We give the corresponding SAT and MILP model and their parallel versions, and apply them to \chachacore, \speckfamily, \leafamily, and \hightfamily. Our method greatly outperforms all previous modeling of modular addition.
In particular, we find the first differential path for 4 rounds of \chachacore with a probability greater than 2^{-256}, and a corresponding 6 rounds boomerang distinguisher.
This indicates that purely differential-based attacks have the potential to become competitive with differential-linear attacks,
currently, the best-known attacks against \chachacore and other ARX ciphers.
Finally, we exhibit an improved key recovery attack on reduced \leafamily.
ePrint: https://eprint.iacr.org/2024/1743
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 .