Welcome to the resource topic for 2025/2128
Title:
Refined Linear Approximations for ARX Ciphers and Their Application to ChaCha
Authors: Yurie Okada, Atsuki Nagai, Atsuko Miyaji
Abstract:ARX-based ciphers such as Salsa20 and ChaCha achieve high performance using only modular addition, rotation, and XOR.
While ARX constructions are widely deployed in practice,
linear and differential-linear cryptanalysis often reveal non-negligible biases in their reduced-round variants.
Previous work has shown that a 7-round distinguisher on ChaCha is feasible, requiring about (2^{214}) operations and relying on a linear approximation with a theoretical bias of (2^{-53}).
However, such theoretical approximations significantly deviate from experimental observations.
In this work, we resolve these discrepancies by introducing
new fundamental linear approximations for two consecutive additions over three independent variables.
We rigorously derive the exact probabilities of these approximations, demonstrating that the conventional independence assumption leads to systematic errors in bias estimation.
Applying our theorem to ChaCha, we refine the probabilities of key approximations used in previous attacks.
Our refined estimates closely match experimentally observed biases, reducing the gap between theory and practice.
These results provide a more accurate foundation for future differential-linear cryptanalysis of ChaCha and other ARX-based designs.
ePrint: https://eprint.iacr.org/2025/2128
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 .