The additive differential probability of $k$ successive exclusive-OR

I. A. Sutormin

Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 67-70.

Résumé

We study the additive differential probability of a composition of bitwise XOR — $\mathrm{adp}^{\oplus}_k$. For a set of vectors $\alpha^1 \ldots \alpha^{k + 1} \in \mathbb{Z}_2^{n}$, it is defined as $$ \textstyle\mathrm{adp}^{\oplus}_k(\alpha^{1}, \ldots, \alpha^{k} \to \alpha^{k + 1}) = \dfrac{1}{2^{kn}} \big|\lbrace x^1, \ldots, x^{k}\in \mathbb{Z}_{2}^{n} : {\bigoplus\limits_{i = 1}^{k}(x^i \boxplus \alpha^i)} = \alpha^{k + 1} \boxplus \bigoplus\limits_{i = 1}^{k} x^i \rbrace\big|.$$ It is used when analyzing symmetric key primitives, such as Addition-Rotation-XOR constructions. It is proven that: 1) $\mathrm{adp}^{\oplus}_k$ is a symmetric function; 2) the value of $\mathrm{adp}^{\oplus}_k$ does not change if $2^{n - 1}$ is added to any two arguments; 3) the value of $\mathrm{adp}^{\oplus}_k$ does not change if any two arguments are replaced by the opposite element of $\mathbb{Z}_{2}^{n}$, and if $k$ is even, then the value of $\mathrm{adp}^{ \oplus}_k$ does not change if any argument is replaced. Recurrence formulas are obtained allowing to calculate the value $\mathrm{adp}^{\oplus}_k$ for arguments of dimension $n + 1$ using the set of values $\mathrm{adp}^{\oplus}_k$ for arguments of dimension $n$. Using recurrent formulas we prove that $\mathrm{adp}^{\oplus}_k$ is equal to zero if and only if there exists a position $i$ such that $(\alpha^1_i, \ldots, \alpha^{ k + 1}_i) \neq (0, \ldots, 0)$; $(\alpha^1_j, \ldots, \alpha^{k + 1}_j ) = (0, \ldots, 0)$ for any $j$, $n \geq j > i$, and either Hamming weight of the vector $(\alpha^1_i, \ldots, \alpha^{k + 1}_i)$ is odd, or $k$ is odd, $i > 1$, vector $(\alpha^1_i, \ldots, \alpha^{k + 1}_i)$ is equal to the $(1, \ldots, 1)$ and Hamming weight of the vector $(\alpha^1_{i - 1}, \ldots, \alpha^{k + 1}_{i - 1})$ is odd. In the case of even $k$, it is proved that $\mathrm{adp}^{\oplus}_k(0, \ldots, 0, \gamma \to \gamma)$ is maximal when the last argument is fixed. In the case of odd $k$, it is conjectured that $\mathrm{adp}^{\oplus}_k(\gamma, \ldots, \gamma \to \gamma)$ is maximum when the last argument is fixed.

Détail

Keywords: differential cryptanalysis, modular addition.
Mots-clés : ARX, XOR

Bibliographie

[1] Shimizu A. and Miyaguchi S., “Fast data encipherment algorithm FEAL”, LNCS, 304, 1988, 267–278 | Zbl

[2] Ferguson N., Lucks S., Schneier B., et al., The Skein Hash Function Family, , 2009 http://www.skein-hash.info

[3] Bernstein D. J., Salsa20 Specification, , 2005 https://cr.yp.to/snuffle/spec.pdf

[4] Bernstein D. J., ChaCha, a Variant of Salsa20, , 2008 https://cr.yp.to/chacha/chacha-20080128.pdf

[5] Aumasson J.-P., Meier W., Phan R. C.-W., and Henzen L., The Hash Function BLAKE, , 2014 https://www.researchgate.net/publication/316806226_The_Hash_Function_BLAKE

[6] Biham E. and Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 1991, no. 4, 3–72 | DOI | MR | Zbl

[7] Lipmaa H., Wallen J., and Dumas P., “On the additive differential probability of exclusive-or”, LNCS, 3017, 2004, 317–331 | Zbl

[8] Mouha N., Kolomeec N., Akhtiamov D., et al., “Maximums of the additive differential probability of Exclusive-Or”, IACR Trans. Symmetric Cryptology, 2021, no. 2, 292–313 | DOI | MR

[9] Gligoroski D., Odegard R. S., Mihova M., et al., “Cryptographic hash function Edon-R”, Proc. IWSCN, 2009, 1–9