On the number of impossible differentials of some ARX transformation

N. A. Kolomeec

Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 47-50.

Résumé

The additive differential probabilities of the function $(x \oplus y) \lll r$ are considered, where $x, y \in \mathbb{Z}_2^{n}$ and $1 \leq r n$. They are interesting in the context of differential cryptanalysis of ciphers whose schemes consist of additions modulo $2^n$, bitwise XORs ($\oplus$) and bit rotations ($\lll r$). We calculate the number of all impossible differentials, i.e. differentials with probability $0$, for all possible $r$ and $n$. The limit of the ratio of this number to the number of all differentials as $r$ and $n-r$ tend to $\infty$ equals $38/245$. We also compare the given numbers and the number of impossible differentials for the function $x \oplus y$.

Détail

Mots-clés : ARX, XOR, bit rotations
Keywords: differential probabilities, modular addition, impossible differentials.

Bibliographie

[1] Roh D., Koo B., Jung Y., et al., “Revised version of block cipher CHAM”, LNCS, 11975, 2020, 1–19 | MR | Zbl

[2] Beierle C., Biryukov A., dos Santos L. C., et al., “Lightweight AEAD and hashing using the Sparkle permutation family”, IACR Trans. Symmetric Cryptology, 2020, no. S1, 208–261 | DOI

[3] Beaulieu R., Shors D., Smith J., et al., The SIMON and SPECK Families of Lightweight Block Ciphers, Cryptology Eprint Archive, , 2013 https://eprint.iacr.org/2013/404

[4] Bernstein D. J., Salsa20 Specification, eSTREAM Project Algorithm Description, 2005 http://www.ecrypt.eu.org/stream/salsa20pf.html

[5] Bernstein D. J., “ChaCha, a variant of Salsa20”, Workshop Record of SASC, 8:1 (2008), 3–5

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

[7] Knudsen L., DEAL —- A 128-bit Block Cipher, Tech. Rep., Department of Informatics, University of Bergen, Bergen, Norway, February 1998 | MR

[8] Biham E., Biryukov A., and Shamir A., “Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials”, LNCS, 1592, 1999, 12–23 | Zbl

[9] Biryukov A. and Velichkov V., “Automatic search for differential trails in ARX ciphers”, LNCS, 8366, 2014, 227–250 | MR | Zbl

[10] Leurent G., “Analysis of differential attacks in ARX constructions”, LNCS, 7658, 2012, 226–243 | Zbl

[11] Malyshev F. M., “Veroyatnostnye kharakteristiki raznostnykh i lineinykh sootnoshenii dlya neodnorodnoi lineinoi sredy”, Matematicheskie voprosy kriptografii, 10:1 (2019), 41–72 | DOI | Zbl

[12] Malyshev F. M., “Raznostnye kharakteristiki osnovnykh operatsii ARX-shifrov”, Matematicheskie voprosy kriptografii, 11:4 (2020), 97–105 | DOI | Zbl

[13] Daum M., Cryptanalysis of Hash Functions of the MD4-Family, PhD Thesis, Ruhr-Universitat Bochum, May 2005

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

[15] Mouha N., Velichkov V., De Cannière C., and Preneel B., “The differential analysis of S-functions”, LNCS, 6544, 2010, 36–56 | MR

[16] 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

[17] Velichkov V., Mouha N., De Cannière C., and Preneel B., “The additive differential probability of ARX”, LNCS, 6733, 2011, 342–358 | Zbl

[18] Kolomeec N., Sutormin I., Bykov D., et al., On Additive Differential Probabilities of the Composition of Bitwise Exclusive-OR and a Bit Rotation, 2023, arXiv: 2303.04097