CryptoDB
Exact Formula for RX-Differential Probability Through Modular Addition for All Rotations
| Authors: | |
|---|---|
| Download: | |
| Abstract: | This work presents an exact and compact formula for the probability of rotation-xor differentials (RX-differentials) through modular addition, for arbitrary rotation amounts, which has been a long-standing open problem. The formula comes with a rigorous proof and is also verified by extensive experiments.Our formula uncovers error in a recent work from 2022 proposing a formula for rotation amounts bigger than 1. Surprisingly, it also affects correctness of the more studied and used formula for the rotation amount equal to 1 (from TOSC 2016). Specifically, it uncovers rare cases where the assumptions of this formula do not hold. Correct formula for arbitrary rotations now opens up a larger search space where one can often find better trails.For applications, we propose automated mixed integer linear programming (MILP) modeling techniques for searching optimal RX-trails based on our exact formula. They are consequently applied to several ARX designs, including Salsa, Alzette and a small-key variant of Speck, and yield many new RX-differential distinguishers, some of them based on provably optimal trails. In order to showcase the relevance of the RX-differential analysis, we also design Malzette, a 12-round Alzette-based permutation with maliciously chosen constants, which has a practical RX-differential distinguisher, while standard differential/linear security arguments suggest sufficient security. |
BibTeX
@article{tosc-2025-35404,
title={Exact Formula for RX-Differential Probability Through Modular Addition for All Rotations},
journal={IACR Transactions on Symmetric Cryptology},
publisher={Ruhr-Universität Bochum},
volume={2025},
pages={542-591},
url={https://tosc.iacr.org/index.php/ToSC/article/view/12087},
doi={10.46586/tosc.v2025.i1.542-591},
author={Alex Biryukov and Baptiste Lambin and Aleksei Udovenko},
year=2025
}