Paper 2025/550
Exact Formula for RX-Differential Probability through Modular Addition for All Rotations
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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in TOSC 2025
- DOI
- 10.46586/tosc.v2025.i1.542-591
- Keywords
- Differential cryptanalysisRotational cryptanalysisRX-differentials
- Contact author(s)
-
alex biryukov @ uni lu
baptiste lambin @ protonmail com
aleksei @ affine group - History
- 2025-03-26: revised
- 2025-03-25: received
- See all versions
- Short URL
- https://ia.cr/2025/550
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/550, author = {Alex Biryukov and Baptiste Lambin and Aleksei Udovenko}, title = {Exact Formula for {RX}-Differential Probability through Modular Addition for All Rotations}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/550}, year = {2025}, doi = {10.46586/tosc.v2025.i1.542-591}, url = {https://eprint.iacr.org/2025/550} }