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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Refined Linear Approximations for ARX Ciphers and Their Application to ChaCha

  • Yurie Okada,
  • Atsuki Nagai,
  • Atsuko Miyaji

摘要

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.