Paper 2025/550

Exact Formula for RX-Differential Probability through Modular Addition for All Rotations

Alex Biryukov, DCS and SnT, University of Luxembourg
Baptiste Lambin, SnT, University of Luxembourg
Aleksei Udovenko, SnT, University of Luxembourg
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.