Geodesic
Additive differentials for ARX mappings with probability exceeding $1/4$
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 108-135 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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
Mots-clés : XOR, bit rotation. 
@article{DA_2024_31_2_a6,
     author = {A. S. Mokrousov and N. A. Kolomeec},
     title = {Additive differentials for {ARX} mappings with~probability exceeding~$1/4$},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {108--135},
     year = {2024},
     volume = {31},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_2_a6/}
}
TY  - JOUR
AU  - A. S. Mokrousov
AU  - N. A. Kolomeec
TI  - Additive differentials for ARX mappings with probability exceeding $1/4$
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 108
EP  - 135
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_2_a6/
LA  - ru
ID  - DA_2024_31_2_a6
ER  - 
%0 Journal Article
%A A. S. Mokrousov
%A N. A. Kolomeec
%T Additive differentials for ARX mappings with probability exceeding $1/4$
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 108-135
%V 31
%N 2
%U http://geodesic.mathdoc.fr/item/DA_2024_31_2_a6/
%G ru
%F DA_2024_31_2_a6
A. S. Mokrousov; N. A. Kolomeec. Additive differentials for ARX mappings with probability exceeding $1/4$. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 108-135. http://geodesic.mathdoc.fr/item/DA_2024_31_2_a6/

[1] Shimizu A., Miyaguch S., “Fast data encipherment algorithm FEAL”, Advances in cryptology — EUROCRYPT'87, Proc. Workshop Theory and Application of Cryptographic Techniques (Amsterdam, The Netherlands, Apr. 13–15, 1987), Lect. Notes Comput. Sci., 304, Springer, Heidelberg, 1988, 267–278 | DOI | MR | Zbl

[2] Ferguson N., Lucks S., Schneier B. et al., The Skein hash function family, Univ. Calif., Santa Barbara, CA, 2008, 100 pp. (accessed Apr. 3, 2024) www.schneier.com/wp-content/uploads/2015/01/skein.pdf

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

[4] Bernstein D. J., Salsa20 specification, Univ. Ill. Chic., Chicago, 2007, 9 pp. (accessed June 1, 2024) cr.yp.to/snuffle/spec.pdf

[5] Bernstein D. J., ChaCha, a variant of Salsa20, Univ. Ill. Chic., Chicago, 2008, 6 pp. (accessed June 1, 2024) cr.yp.to/chacha/chacha-20080128.pdf

[6] Koo B., Roh D., Kim H., Jung Y., Lee D., Kwon D., “CHAM: A family of lightweight block ciphers for resource-constrained devices”, Information security and cryptology — ICISC 2017, Rev. Sel. Pap. 20th Int. Conf. (Seoul, South Korea, Nov. 29 – Dec. 1, 2017), Lect. Notes Comput. Sci., 10779, Springer, Cham, 2017, 3–25 | DOI | MR

[7] Roh D., Koo B., Jung Y., Jeong I., Lee D., Kwon D., Kim W., “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 | Zbl

[8] Mouha N., Mennink B., 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. Workshop (Montreal, Canada, Aug. 14–15, 2014), Lect. Notes Comput. Sci., 8781, Springer, Cham, 2014, 306–323 | DOI | MR | Zbl

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

[10] 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 | Zbl

[11] 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 | Zbl

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

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

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

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

[16] Daum M. A., Cryptanalysis of hash functions of the MD4-family, PhD Thes., Ruhr-Univ. Bochum, Bochum, 2005, 178 pp.

[17] 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 | Zbl

[18] 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 | Zbl

[19] 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 | Zbl

[20] 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. Libr. e-Print Archive, Cornell Univ., Ithaca, NY, 2023, 35 pp., arXiv: 2303.04097 | MR

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

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

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