Разности по модулю 2n для ARX-преобразований, вероятность которых больше 1/4

Разности по модулю $2^n$ для ARX-преобразований, вероятность которых больше $1/4$

Мокроусов А. С., Коломеец Н. А.
Дискретный анализ и исследование операций, 31, 2, 108–135 (2024)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2024.31.769

Аннотация:

Рассматриваются разностные характеристики по модулю $2^n$ для преобразований $x \oplus y$ и $(x \oplus y) \lll r$, где $x, y \in \mathbb {Z}_2^n$ и $1 \le r < n$. Эти характеристики применяются при разностном криптоанализе шифров архитектуры ARX, использующих в качестве операций только сложение по модулю $2^n$, побитовое исключающее «или» (XOR, $\oplus$) и циклический сдвиг битов на $r$ позиций $(\lll r)$. Получена полная характеризация разностей, вероятность которых больше $1/4$. Возможными значениями вероятности при этом условии являются $1/3 + 4^{2−i}/6$ для обоих преобразований, где $i \in$ {$1, \dots , n$}. Описаны разности, на которых достигается каждое из значений, и подсчитано их число. Найдено общее число разностей с приведёнными вероятностями: $48n − 68$ для $x \oplus y$ и $24n − 30$ для $(x \oplus y) \lll r$, где $n \ge 2$. Также дано сравнение разностных характеристик в контексте рассматриваемого ограничения на вероятность. 
Табл. 6, библиогр. 23.

Литература:
  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). Heidelberg: Springer, 1988. P. 267–278. (Lect. Notes Comput. Sci.; V. 304). DOI: 10.1007/3-540-39118-5_24.
     
  2. Ferguson N., Lucks S., Schneier B. [et al.]. The Skein hash function family. Santa Barbara, CA: Univ. Calif., 2008. 100 p. URL: www.schneier.com/wp-content/uploads/2015/01/skein.pdf (accessed Apr. 3, 2024).
     
  3. 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 June 1, 2024).
     
  4. Bernstein D. J. Salsa20 specification. Chicago: Univ. Ill. Chic., 2007. 9 p. URL: cr.yp.to/snuffle/spec.pdf (accessed June 1, 2024).
     
  5. Bernstein D. J. ChaCha, a variant of Salsa20. Chicago: Univ. Ill. Chic., 2008. 6 p. URL: cr.yp.to/chacha/chacha-20080128.pdf (accessed June 1, 2024).
     
  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). Cham: Springer, 2017. P. 3–25. (Lect. Notes Comput. Sci.; V. 10779). DOI: 10.1007/978-3-319-78556-1_1.
     
  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). Cham: Springer, 2020. P. 1–19. (Lect. Notes Comput. Sci.; V. 11975). DOI: 10.1007/978-3-030-40921-0_1.
     
  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). Cham: Springer, 2014. P. 306–323. (Lect. Notes Comput. Sci.; V. 8781).
     
  9. Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptol. 1991. V. 4. P. 3–72.
     
  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). Cham: Springer, 2014. P. 227–250. (Lect. Notes Comput. Sci.; V. 8366). DOI: 10.1007/ 978-3-319-04852-9_12.
     
  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). Heidelberg: Springer, 2012. P. 226–243. (Lect. Notes Comput. Sci.; V. 7658). DOI: 10.1007/978-3-642-34961-4_15.
     
  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). Pt. I. Heidelberg: Springer, 2013. P. 241–258. (Lect. Notes Comput. Sci.; V. 8042). DOI: 10.1007/978-3-642-40041-4_14.
     
  13. Малышев Ф. М. Вероятностные характеристики разностных и линейных соотношений для неоднородной линейной среды // Мат. вопросы криптографии. 2019. Т. 10, № 1. С. 41–72.
     
  14. Малышев Ф. М. Разностные характеристики основных операций ARXшифров // Мат. вопросы криптографии. 2020. Т. 11, № 4. С. 97–105.
     
  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). Heidelberg: Springer, 1992. P. 71–80. (Lect. Notes Comput. Sci.; V. 658).
     
  16. Daum M. A. Cryptanalysis of hash functions of the MD4-family: PhD Thes. Bochum: Ruhr-Univ. Bochum, 2005. 178 p.
     
  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). Heidelberg: Springer, 2004. P. 317–331. (Lect. Notes Comput. Sci.; V. 3017).
     
  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). Heidelberg: Springer, 2011. P. 36–56. (Lect. Notes Comput. Sci.; V. 6544).
     
  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). Heidelberg: Springer, 2011. P. 342–358. (Lect. Notes Comput. Sci.; V. 6733).
     
  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. Ithaca, NY: Cornell Univ., 2023. 35 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2303.04097).
     
  21. 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.
     
  22. Gorodilova A. A., Tokareva N. N., Agievich S. V. [et al.]. An overview of the Eighth International Olympiad in Cryptography «Non-Stop University Crypto» // Сиб. электрон. мат. изв. 2022. Т. 19, № 1. C. А.9–А.37.
     
  23. 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. C. 41–62.

Исследование выполнено при поддержке Математического центра в Академгородке в рамках соглашения с Министерством науки и высшего образования Российской Федерации (соглашение № 075–15–2022–282).

Мокроусов Антон Сергеевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: settingx@mail.ru

Коломеец Николай Александрович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: kolomeec@math.nsc.ru

Статья поступила 3 мая 2023 г. 
После доработки — 16 октября 2023 г. 
Принята к публикации 22 декабря 2023 г.

Abstract:

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 \le 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 \ge 2$. We compare differentials of both mappings under the given constraint. 
Tab. 6, bibliogr. 23.

References:
  1. A. Shimizu and S. Miyaguch, Fast data encipherment algorithm FEAL, in Advances in Cryptology — EUROCRYPT’87 (Proc. Workshop Theory and Application of Cryptographic Techniques, Amsterdam, The Netherlands, Apr. 13–15, 1987) (Springer, Heidelberg, 1988), pp. 267–278 (Lect. Notes Comput. Sci., Vol. 304), DOI: 10.1007/3-540-39118-5_24.
     
  2. N. Ferguson, S. Lucks, B. Schneier, [et al.], The Skein Hash Function Family (Univ. California, Santa Barbara, CA, 2008), URL: www.schneier.com/wp-content/uploads/2015/01/skein.pdf (accessed Apr. 3, 2024).
     
  3. 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, Paper ID 2013/404), URL: eprint.iacr.org/2013/404 (accessed June 1, 2024).
     
  4. D. J. Bernstein, Salsa20 specification (Univ. Ill. Chic., Chicago, 2007), URL: cr.yp.to/snuffle/spec.pdf (accessed June 1, 2024).
     
  5. D. J. Bernstein, ChaCha, a variant of Salsa20 (Univ. Ill. Chic., Chicago, 2008), URL: https://cr.yp.to/chacha/chacha-20080128.pdf (accessed June 1, 2024).
     
  6. B. Koo, D. Roh, H. Kim, Y. Jung, D. Lee, and D. Kwon, CHAM: A family of lightweight block ciphers for resource-constrained devices, in Information Security and Cryptology — ICISC 2017 (Rev. Sel. Pap. 20th Int. Conf., Seoul, South Korea, Nov. 29 – Dec. 1, 2017) (Springer, Cham, 2017), pp. 3–25 (Lect. Notes Comput. Sci., Vol. 10779), DOI: 10.1007/978-3-319-78556-1_1.
     
  7. D. Roh, B. Koo, Y. Jung, I. Jeong, D. Lee, D. Kwon, and W. 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.
     
  8. N. Mouha, B. Mennink, A. 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. Workshop, Montreal, Canada, Aug. 14–15, 2014) (Springer, Cham, 2014), pp. 306–323 (Lect. Notes Comput. Sci., Vol. 8781).
     
  9. E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptol. 4, 3–72 (1991).
     
  10. 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.
     
  11. 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), DOI: 10.1007/978-3-642-34961-4_15.
     
  12. 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, CA, USA, Aug. 18–22, 2013), Pt. I (Springer, Heidelberg, 2013), pp. 241–258 (Lect. Notes Comput. Sci., Vol. 8042), DOI: 10.1007/978-3-642-40041-4_14.
     
  13. F. M. Malyshev, Probabilistic characteristics of differential and linear relations for nonhomogeneous linear medium, Mat. Vopr. Kriptogr. 10 (1), 41–72 (2019) [Russian].
     
  14. F. M. Malyshev, Differential characteristics of base operations in ARXciphers, Mat. Vopr. Kriptogr. 11 (4), 97–105 (2020) [Russian].
     
  15. 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).
     
  16. M. A. Daum, Cryptanalysis of hash functions of the MD4-family, PhD Thesis (Ruhr-Univ. Bochum, Bochum, 2005).
     
  17. 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).
     
  18. 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).
     
  19. 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).
     
  20. 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).
     
  21. 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).
     
  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), A.9–A.37 (2022).
     
  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., No. 3, 41–62 (2015).