The number of impossible additive differentials for the composition of XOR and bit rotation

N. A. Kolomeec

Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 58-89

Résumé

Additive differentials of the function $(x \oplus y) \lll r$ whose probability is $0$ are considered, where $x, y \in \mathbb{Z}_2^n$ and $1 \leq r < n.$ They are called impossible differentials and 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$). The number of all such differentials is calculated for all possible $r$ and $n.$ It is also shown that this number is greater than $\frac{38}{245} 8^n.$ Moreover, the estimate is asymptotically tight for $r, n-r \to \infty.$ For any fixed $n$ the number of all impossible differentials decreases as $r$ goes from $1$ to $\lceil n/2 \rceil$ (to $n/2 + 1$ in the case of $n \in \{4, 6, 8, 10, 12\}$) and then increases monotonically as $r$ goes to $n-1.$ A simplified description of all impossible differentials is obtained up to known symmetries. Tab. 10, bibliogr. 25.

Détail

Mots-clés : ARX, XOR, bit rotation
Keywords: differential probability, modular addition, impossible differential.

Bibliographie

[1] Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L., The SIMON and SPECK families of lightweight block ciphers, Cryptol. ePrint Archive, Paper ID 2013/404, Univ. California, San Diego, 2013, 45 pp. (accessed: Dec. 9, 2024) http://eprint.iacr.org/2013/404

[2] Roh D., Koo B., Jung Y., Jeong I. W., Lee D.-G., Kwon D., Kim W.-H., “Revised version of block cipher CHAM”, Information security and cryptology — ICISC 2019, Rev. Sel. Pap. 22th Int. Conf. (Seoul, South Korea, Dec. 4–6, 2019), Lect. Notes Comput. Sci., 11975, Springer, Cham, 2020, 1–19 | DOI | MR

[3] Bernstein D. J., The Salsa20 family of stream ciphers, Univ. Ill. Chic., Chicago, 2007, 15 pp. (accessed: Dec. 9, 2024) http://cr.yp.to/snuffle/salsafamily-20071225.pdf

[4] Bernstein D. J., ChaCha, a variant of Salsa20, Univ. Ill. Chic., Chicago, 2008, 6 pp. (accessed: Dec. 9, 2024) http://cr.yp.to/chacha/chacha-20080128.pdf

[5] Beierle C., Biryukov A., Cardoso dos Santos L. et al., “Lightweight AEAD and hashing using the sparkle permutation family”, IACR Trans. Symmetric Cryptol., 2020, Suppl. 1 (2020), 208–261 | DOI

[6] Mouha N., Mennink B., Van Herrewege A., Watanabe D., Preneel B., Verbauwhede I., “Chaskey: An efficient MAC algorithm for 32-bit microcontrollers”, Selected areas in cryptography — SAC 2014, Rev. Sel. Pap. 21th Int. Conf. (Montreal, Canada, Aug. 14–15, 2014), Lect. Notes Comput. Sci., 8781, Springer, Cham, 2014, 306–323 | DOI | MR

[7] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptol., 4 (1991), 3–72 | DOI | MR

[8] Biryukov A., Velichkov V., “Automatic search for differential trails in ARX ciphers”, Topics in cryptology — CT-RSA 2014, Proc. Cryptographer's Track at the RSA Conf. (San Francisco, USA, Feb. 25–28, 2014), Lect. Notes Comput. Sci., 8366, Springer, Cham, 2014, 227–250 | DOI | MR

[9] Leurent G., “Analysis of differential attacks in ARX constructions”, Advances in cryptology — ASIACRYPT 2012, Proc. 18th Int. Conf. Theory and Application of Cryptology and Information Security (Beijing, China, Dec. 2–6, 2012), Lect. Notes Comput. Sci., 7658, Springer, Heidelberg, 2012, 226–243 | DOI | MR

[10] Leurent G., “Construction of differential characteristics in ARX designs application to Skein”, Advances in cryptology — CRYPTO 2013, Proc. 33rd Annu. Cryptology Conf. (Santa Barbara, USA, Aug. 18–22, 2013), Lect. Notes Comput. Sci., 8042, Springer, Heidelberg, 2013, 241–258 | DOI

[11] F. M. Malyshev, “Probabilistic characteristics of differential and linear relations for nonhomogeneous linear medium”, Mat. Vopr. Kriptogr., 10:1 (2019), 41–72 (In Russian) | DOI

[12] F. M. Malyshev, “Differential characteristics of base operations in ARX-ciphers”, Mat. Vopr. Kriptogr., 11:4 (2020), 97–105 (In Russian) | DOI

[13] Berson T. A., “Differential cryptanalysis mod $2^{32}$ with applications to MD5”, Advances in cryptology — EUROCRYPT'92, Proc. Workshop Theory and Application of Cryptographic Techniques (Balatonfüred, Hungary, May 24–28, 1992), Lect. Notes Comput. Sci., 658, Springer, Heidelberg, 1992, 71–80 | DOI | MR

[14] Daum M. A., Cryptanalysis of hash functions of the MD4-family, PhD Thesis, Ruhr-Univ. Bochum, Bochum, 2005

[15] Lipmaa H., Wallén J., Dumas P., “On the additive differential probability of exclusive-or”, Fast software encryption, Rev. Pap. 11th Int. Workshop (Delhi, India, Feb. 5–7, 2004), Lect. Notes Comput. Sci., 3017, Springer, Heidelberg, 2004, 317–331 | DOI

[16] Mouha N., Velichkov V., De Canniére C., Preneel B., “The differential analysis of S-functions”, Selected areas in cryptography, Rev. Sel. Pap. 17th Int. Workshop (Waterloo, Canada, Aug. 12–13, 2010), Lect. Notes Comput. Sci., 6544, Springer, Heidelberg, 2011, 36–56 | DOI | MR

[17] Mouha N., Kolomeec N. A., Akhtiamov D. et al., “Maximums of the additive differential probability of exclusive-or”, IACR Trans. Symmetric Cryptol., 2021:2 (2021), 292–313 | DOI | MR

[18] Velichkov V., Mouha N., De Canniére C., Preneel B., “The additive differential probability of ARX”, Fast software encryption, Rev. Sel. Pap. 18th Int. Workshop (Lyngby, Denmark, Feb. 13–16, 2011), Lect. Notes Comput. Sci., 6733, Springer, Heidelberg, 2011, 342–358 | DOI

[19] Kolomeec N. A., Sutormin I. A., Bykov D. A., Panferov M. A., Bonich T. A., On additive differential probabilities of the composition of bitwise exclusive-or and a bit rotation, Cornell Univ., Ithaca, NY, 2023, 35 pp., arXiv: 2303.04097 | DOI | MR

[20] A. S. Mokrousov and N. A. Kolomeec, “Additive differentials for ARX mappings with probability exceeding $1/4$”, J. Appl. Ind. Math., 18:2 (2024), 294–311 | DOI | DOI | MR

[21] I. A. Sutormin and N. A. Kolomeec, “On additive differential probabilities of a composition of bitwise XORs”, Prikl. Diskretn. Mat., 2023, no. 60, 59–75 | DOI | MR

[22] Knudsen L., DEAL — A 128-bit block cipher, Tech. Rep. No151, Univ. Bergen, Bergen, 1998, 9 pp. | MR

[23] Biham E., Biryukov A., Shamir A., “Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials”, Advances in cryptology — EUROCRYPT'99, Proc. Int. Conf. Theory and Application of Cryptographic Techniques (Prague, Czech Republic, May 2–6, 1999), Lect. Notes Comput. Sci., 1592, Springer, Heidelberg, 1999, 12–23 | DOI | MR

[24] S. V. Agievich, A. A. Gorodilova, N. A. Kolomeec et al., “Problems, solutions, and experience of the First International Student's Olympiad in Cryptography”, Prikl. Diskretn. Mat., 2015, no. 3, 41–62 | DOI

[25] A. A. Gorodilova, N. N. Tokareva, S. V. Agievich [et al.]., “An overview of the Eight International Olympiad in Cryptography “Non-Stop University Crypto””, Sib. Elektron. Mat. Izv., 19:1 (2022), A9–A37 | DOI | MR