Число невозможных разностей по модулю 2 n композиции XOR и циклического сдвига битов

Число невозможных разностей по модулю $2^n$ композиции XOR и циклического сдвига битов

Коломеец Н. А.
Дискретный анализ и исследование операций, 31, 4, 58-89 (2024)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2024.31.800

Аннотация:

Для преобразования ($x \oplus y$) $\lll r, x, y \in \mathbb{Z}_2^n$ , $1 \le r < n$, исследуются невозможные разности по модулю $2^n$. Они представляют интерес в контексте разностных атак на шифры, схемы которых состоят из сложений по модулю $2^n$, побитовых XOR ($\oplus$) и циклических сдвигов битов на $r$ позиций ($\lll r$). В работе найдено число всех невозможных разностей при всех возможных значениях $n$ и $r$. В качестве следствия показано, что оно больше $\frac{38} {245} 8^n$, причём эта оценка асимптотически точна при $r, n − r \to \infty$. При фиксированном $n$ число невозможных разностей монотонно убывает с ростом $r$ от $1$ до $\left \lceil n/2 \right \rceil$ ($n/2 + 1$ при $n \in$ {4, 6, 8, 10, 12}), а далее — монотонно возрастает. Приведено более компактное описание всех невозможных разностей с точностью до известных симметрий. 
Табл. 10, библиогр. 25.

Литература:
  1. Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L. The SIMON and SPECK families of lightweight block ciphers. San Diego: Univ. California, 2013. 45 p. (Cryptol. ePrint Archive; Paper ID 2013/404). URL: eprint.iacr.org/2013/404 (accessed: Dec. 9, 2024). 
     
  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). Cham: Springer, 2020. P. 1–19. (Lect. Notes Comput. Sci.; V. 11975). DOI: 10.1007/978-3-030-40921-0_1. 
     
  3. Bernstein D. J. The Salsa20 family of stream ciphers. Chicago: Univ. Ill. Chic., 2007. 15 p. URL: cr.yp.to/snuffle/salsafamily-20071225.pdf (accessed: Dec. 9, 2024).
     
  4. Bernstein D. J. ChaCha, a variant of Salsa20. Chicago: Univ. Ill. Chic., 2008. 6 p. URL: cr.yp.to/chacha/chacha-20080128.pdf (accessed: Dec. 9, 2024).
     
  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. V. 2020, Suppl. 1. P. 208–261. DOI: 10.13154/tosc. v2020.iS1.208-261.
     
  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). Cham: Springer, 2014. P. 306–323. (Lect. Notes Comput. Sci.; V. 8781). DOI: 10.1007/978-3-319-13051-4_19.
     
  7. Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptol. 1991. V. 4. P. 3–72.
     
  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). Cham: Springer, 2014. P. 227–250. (Lect. Notes Comput. Sci.; V. 8366). DOI: 10.1007/ 978-3-319-04852-9_12.
     
  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). Heidelberg: Springer, 2012. P. 226–243. (Lect. Notes Comput. Sci.; V. 7658).
     
  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). Heidelberg: Springer, 2013. P. 241–258. (Lect. Notes Comput. Sci.; V. 8042). DOI: 10.1007/978-3-642-40041-4_14.
     
  11. Малышев Ф. М. Вероятностные характеристики разностных и линейных соотношений для неоднородной линейной среды // Мат. вопр. криптографии. 2019. Т. 10, № 1. С. 41–72. DOI: 10.4213/mvk276.
     
  12. Малышев Ф. М. Разностные характеристики основных операций ARXшифров // Мат. вопр. криптографии. 2020. Т. 11, № 4. С. 97–105. DOI: 10.4213/mvk342.
     
  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). Heidelberg: Springer, 1992. P. 71–80. (Lect. Notes Comput. Sci.; V. 658). DOI: 10.1007/3-540-47555-9_6.
     
  14. Daum M. A. Cryptanalysis of hash functions of the MD4-family: PhD Thesis. Bochum: Ruhr-Univ. 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). Heidelberg: Springer, 2004. P. 317–331. (Lect. Notes Comput. Sci.; V. 3017). DOI: 10.1007/978-3-540-25937-4_20.
     
  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). Heidelberg: Springer, 2011. P. 36–56. (Lect. Notes Comput. Sci.; V. 6544). DOI: 10.1007/978-3-642-19574-7_3.
     
  17. Mouha N., Kolomeec N. A., Akhtiamov D. [et al.]. Maximums of the additive differential probability of exclusive-or // IACR Trans. Symmetric Cryptol. 2021. V. 2021, No. 2. P. 292–313. DOI: 10.46586/tosc.v2021.i2. 292-313.
     
  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). Heidelberg: Springer, 2011. P. 342–358. (Lect. Notes Comput. Sci.; V. 6733). DOI: 10.1007/ 978-3-642-21702-9_20.
     
  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. Ithaca, NY: Cornell Univ., 2023. 35 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2303.04097). DOI: 10.48550/arXiv.2303. 04097.
     
  20. Мокроусов А. С., Коломеец Н. А. Разности по модулю $2^n$ для ARX-преобразований, вероятность которых больше 1/4 // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 2. С. 108–135. DOI: 10.33048/daio.2024.31. 769.
     
  21. Sutormin I. A., Kolomeec N. A. On additive differential probabilities of a composition of bitwise XORs // Прикл. дискрет. математика. 2023. № 60. С. 59–75. DOI: 10.17223/20710410/60/5.
     
  22. Knudsen L. DEAL — A 128-bit block cipher. Tech. Rep. No. 151. Bergen: Univ. Bergen, 1998. 9 p.
     
  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). Heidelberg: Springer, 1999. P. 12–23. (Lect. Notes Comput. Sci.; V. 1592). DOI: 10.1007/ 3-540-48910-X_2.
     
  24. Agievich S. V., Gorodilova A. A., Kolomeec N. A. [et al.]. Problems, solutions and experience of the First International Student’s Olympiad in Cryptography // Прикл. дискрет. математика. 2015. № 3. С. 41–62. DOI: 10.17223/20710410/29/4.
     
  25. Gorodilova A. A., Tokareva N. N., Agievich S. V. [et al.]. An overview of the Eight International Olympiad in Cryptography «Non-Stop University Crypto» // Сиб. электрон. мат. изв. 2022. Т. 19, № 1. С. A9–A37. DOI: 10.33048/semi.2022.19.023.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Коломеец Николай Александрович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: nkolomeec@gmail.com

Статья поступила 9 апреля 2024 г.
После доработки — 10 мая 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

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 \le 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 $\left \lceil n/2 \right \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.

References:
  1. R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, and L. Wingers, The SIMON and SPECK families of lightweight block ciphers (Univ. California, San Diego, 2013) (Cryptol. ePrint Archive; ID 2013/404), URL: eprint.iacr.org/2013/404 (accessed: Dec. 9, 2024).
     
  2. D. Roh, B. Koo, Y. Jung, I. W. Jeong, D.-G. Lee, D. Kwon, and W.-H. Kim, Revised version of block cipher CHAM, in Information Security and Cryptology — ICISC 2019 (Rev. Sel. Pap. 22th Int. Conf., Seoul, South Korea, Dec. 4–6, 2019) (Springer, Cham, 2020), pp. 1–19 (Lect. Notes Comput. Sci., Vol. 11975), DOI: 10.1007/978-3-030-40921-0_1.
     
  3. D. J. Bernstein, The Salsa20 family of stream ciphers (Univ. Ill. Chic., Chicago, 2007), URL: cr.yp.to/snuffle/salsafamily-20071225.pdf (accessed: Dec. 9, 2024).
     
  4. D. J. Bernstein, ChaCha, a variant of Salsa20 (Univ. Ill. Chic., Chicago, 2008), URL: cr.yp.to/chacha/chacha-20080128.pdf (accessed: Dec. 9, 2024).
     
  5. C. Beierle, A. Biryukov, L. Cardoso dos Santos, [et al.]. Lightweight AEAD and hashing using the sparkle permutation family, IACR Trans. Symmetric Cryptol. 2020 (Suppl. 1), 208–261 (2020), DOI: 10.13154/tosc.v2020. iS1.208-261.
     
  6. N. Mouha, B. Mennink, A. Van Herrewege, D. Watanabe, B. Preneel, and I. Verbauwhede, Chaskey: An efficient MAC algorithm for 32-bit microcontrollers, in Selected Areas in Cryptography — SAC 2014 (Rev. Sel. Pap. 21th Int. Conf., Montreal, Canada, Aug. 14–15, 2014) (Springer, Cham, 2014), pp. 306–323 (Lect. Notes Comput. Sci., Vol. 8781), DOI: 10.1007/ 978-3-319-13051-4_19.
     
  7. E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptol. 4, 3–72 (1991).
     
  8. A. Biryukov and V. Velichkov, Automatic search for differential trails in ARX ciphers, in Topics in Cryptology — CT-RSA 2014 (Proc. Cryptographer’s Track at the RSA Conf., San Francisco, USA, Feb. 25–28, 2014) (Springer, Cham, 2014), pp. 227–250 (Lect. Notes Comput. Sci., Vol. 8366), DOI: 10.1007/978-3-319-04852-9_12.
     
  9. G. Leurent, Analysis of differential attacks in ARX constructions, in Advances in Cryptology — ASIACRYPT 2012 (Proc. 18th Int. Conf. Theory and Application of Cryptology and Information Security, Beijing, China, Dec. 2–6, 2012) (Springer, Heidelberg, 2012), pp. 226–243 (Lect. Notes Comput. Sci., Vol. 7658).
     
  10. G. Leurent, Construction of differential characteristics in ARX designs application to Skein, in Advances in Cryptology — CRYPTO 2013 (Proc. 33rd Annu. Cryptology Conf., Santa Barbara, USA, Aug. 18–22, 2013) (Springer, Heidelberg, 2013), pp. 241–258 (Lect. Notes Comput. Sci., Vol. 8042), DOI: 10.1007/978-3-642-40041-4_14.
     
  11. F. M. Malyshev, Probabilistic characteristics of differential and linear relations for nonhomogeneous linear medium, Mat. Vopr. Kriptogr. 10 (1), 41–72 (2019), DOI: 10.4213/mvk276 [Russian].
     
  12. F. M. Malyshev, Differential characteristics of base operations in ARXciphers, Mat. Vopr. Kriptogr. 11 (4), 97–105 (2020), DOI: 10.4213/mvk342 [Russian].
     
  13. T. A. Berson, Differential cryptanalysis mod $2^{32}$ with applications to MD5, in Advances in Cryptology — EUROCRYPT’92 (Proc. Workshop Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, May 24–28, 1992) (Springer, Heidelberg, 1992), pp. 71–80 (Lect. Notes Comput. Sci., Vol. 658), DOI: 10.1007/3-540-47555-9_6.
     
  14. M. A. Daum, Cryptanalysis of hash functions of the MD4-family, PhD Thesis (Ruhr-Univ. Bochum, Bochum, 2005).
     
  15. H. Lipmaa, J. Wallén and P. Dumas, On the additive differential probability of exclusive-or, in Fast Software Encryption (Rev. Pap. 11th Int. Workshop, Delhi, India, Feb. 5–7, 2004) (Springer, Heidelberg, 2004), pp. 317–331 (Lect. Notes Comput. Sci., Vol. 3017), DOI: 10.1007/978-3-540-25937-4_20.
     
  16. N. Mouha, V. Velichkov, C. De Canniére and B. Preneel, The differential analysis of S-functions, in Selected Areas in Cryptography (Rev. Sel. Pap. 17th Int. Workshop, Waterloo, Canada, Aug. 12–13, 2010) (Springer, Heidelberg, 2011), pp. 36–56 (Lect. Notes Comput. Sci., Vol. 6544), DOI: 10.1007/978-3-642-19574-7_3.
     
  17. N. Mouha, N. A. Kolomeec, D. Akhtiamov, [et al.]. Maximums of the additive differential probability of exclusive-or, IACR Trans. Symmetric Cryptol. 2021 (2), 292–313 (2021), DOI: 10.46586/tosc.v2021.i2.292-313. 
     
  18. V. Velichkov, N. Mouha, C. De Canniére and B. Preneel, The additive differential probability of ARX, in Fast Software Encryption (Rev. Sel. Pap. 18th Int. Workshop, Lyngby, Denmark, Feb. 13–16, 2011) (Springer, Heidelberg, 2011), pp. 342–358 (Lect. Notes Comput. Sci., Vol. 6733), DOI: 10.1007/978-3-642-21702-9_20.
     
  19. N. A. Kolomeec, I. A. Sutormin, D. A. Bykov, M. A. Panferov, and T. A. Bonich, On additive differential probabilities of the composition of bitwise exclusive-or and a bit rotation (Cornell Univ., Ithaca, NY, 2023) (Cornell Univ. Libr. e-Print Archive, arXiv:2303.04097), DOI: 10.48550/arXiv.2303. 04097.
     
  20. A. S. Mokrousov and N. A. Kolomeec, Additive differentials for ARX mappings with probability exceeding 1/4, Diskretn. Anal. Issled. Oper. 31 (2), 108–135 (2024), DOI: 10.33048/daio.2024.31.769 [Russian] [J. Appl. Ind. Math. 18 (2), 294–311 (2024), DOI: 10.1134/S199047892402011X].
     
  21. I. A. Sutormin and N. A. Kolomeec, On additive differential probabilities of a composition of bitwise XORs, Prikl. Diskretn. Mat., No. 60, 59–75 (2023), DOI: 10.17223/20710410/60/5.
     
  22. L. Knudsen, DEAL — A 128-bit block cipher, Tech. Rep. No. 151 (Univ. Bergen, Bergen, 1998).
     
  23. E. Biham, A. Biryukov, and A. Shamir, Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials, in Advances in Cryptology — EUROCRYPT’99 (Proc. Int. Conf. Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2–6, 1999) (Springer, Heidelberg, 1999), pp. 12–23 (Lect. Notes Comput. Sci., Vol. 1592), DOI: 10.1007/3-540-48910-X_2.
     
  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., No. 3, 41–62 (2015), DOI: 10.17223/ 20710410/29/4.
     
  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), A9–A37 (2022), DOI: 10.33048/semi. 2022.19.023.