Abstract:
We consider the additive differential probabilities of functions $x \oplus y$ and $(x \oplus y) \lll r,$ where $x, y \in \mathbb{Z}_2^n$ and $1 \leq r < n.$ The probabilities are used for the differential cryptanalysis of ARX ciphers that operate only with addition modulo $2^n,$ bitwise XOR ($\oplus$) and bit rotations ($\lll r$). A complete characterization of differentials whose probability exceeds $1/4$ is obtained. All possible values of their probabilities are $1/3 + 4^{2 - i} / 6$ for $i \in \{1, \dots, n\}.$ We describe differentials with each of these probabilities and calculate the number of these values. We also calculate the number of all considered differentials. It is $48n - 68$ for $x \oplus y$ and $24n - 30$ for $(x \oplus y) \lll r,$ where $n \geq 2.$ We compare differentials of both mappings under the given constraint. Tab. 6, bibliogr. 23.
Keywords:ARX scheme, differential probabilities, modulo addition, XOR, bit rotation.