An algorithm for computing the upper bound for non-minimum weight differentials in 2-round LSX-ciphers

V. A. Kiryukhin

Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 93-109

Résumé

We describe some approaches to upper bounding the non-minimum weight differentials (EDP) and linear hulls (ELP) in 2-round LSX-cipher. We propose a dynamic programming algorithm to solve this problem. For 2-round Kuznyechik the nontrivial upper bounds on all differentials (linear hulls) with 18 and 19 active S-boxes are obtained. These estimates are also holds for other differentials (linear hulls) with a larger number of active S-boxes.

Bibliographie

[1] GOST R 34.12-2018 – National standard of the Russian Federation – Information technology – Cryptographic data security – Block ciphers, 2018

[2] Biham, E., Shamir, A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 1991, 3–72

[3] Matsui M., “Linear cryptanalysis method for DES cipher”, EUROCRYPT'93, Lect. Notes Comput. Sci., 765, 1994, 386–397

[4] Biham E., “On Matsui's linear cryptanalysis”, EUROCRYPT'94, Lect. Notes Comput. Sci., 950, 341–355

[5] Keliher L., Sui. J., “Exact maximum expected differential and linear probability for 2-round Advanced Encryption Standard (AES)”, IET Inf. Security, 1:2 (2007), 53–57

[6] Keliher L., Linear Cryptanalysis of Substitution-Permutation Networks, PhD Thesis, Queen's Univ., Kingston, Canada, 2003

[7] Keliher L., “Refined analysis of bounds related to linear and differential cryptanalysis for the AES”, Lect. Notes Comput. Sci., 3373, 2005, 42–57

[8] Lai X., Massey J.L., Murphy S., “Markov ciphers and differential cryptanalysis”, EUROCRYPT'91, Lect. Notes Comput. Sci., 547, 1991, 17–38

[9] Hardy G.H., Littlewood J.E., Polya G., Inequalities, Cambridge Univ. Press, Cambridge, 1952

[10] Sano F., Ohkuma K., Shimizu H., Kawamura S., “On the security of nested SPN cipher against the differential and linear cryptanalysis”, IEICE Trans. on Fundam. Electronics, Communic. and Comput. Sci., E86-A:1 (2003), 37–46

[11] Daemen J., Rijmen V., The Design of Rijndael: AES – The Advanced Encryption Standard, Springer, Heidelberg etc., 2002, x+238 pp.

[12] Barreto P., Rijmen V., “The Khazad legacy-level block cipher”, First open NESSIE Workshop (Leuven, November 2000)

[13] Kang J.-S., Hong S., Lee S., Yi O., Park C., Lim J., “Practical and provable security against differential and linear cryptanalysis for substitution-permutation networks”, ETRI J., 23:4 (2001)

[14] Park S., Sung S.H., Lee S., Lim J., “Improving the upper bound on the maximum differential and the maximum linear hull probability for SPN structures and AES”, FSE 2003, Lect. Notes Comput. Sci., 2887, 2003, 247–260

[15] Canteaut A., Roue J., “On the behaviors of affine equivalent S-boxes regarding differential and linear attacks”, EUROCRYPT 2015, Lect. Notes Comput. Sci., 9056, 2015, 45–74

[16] Canteaut A., Roue J., “Differential attacks against SPN: A thorough analysis”, C2SI 2015, Lect. Notes Comput. Sci., 9084, 2015, 45–62

[17] Malyshev F.M., Trifonov D.I., “Diffusion properties of XSLP-ciphers”, Matematicheskie Voprosy Kriptografii, 7:3 (2016), 47–60

[18] Malyshev F.M., Trishin A.E., “Linear and differential cryptanalysis: Another viewpoint”, Matematicheskie Voprosy Kriptografii, 11:2 (2020), 83–98

[19] Kiryukhin V.A., “Exact maximum expected differential and linear probability for 2-round Kuznyechik”, Matematicheskie Voprosy Kriptografii, 10:2 (2019), 107–116

[20] Shishkin V., Marshalko G., A memo on Kuznyechik S-box, ISO/IEC JTC 1/SC 27/WG 2 Officer's Contribution N1804, September 2018, 5 pp.

[21] Kiryukhin V., An algorithm for bounding non-minimum weight differentials in 2-round LSX-ciphers, Report 2020/1208, , 2020 https://eprint.iacr.org/2020/1208.pdf