Invariant subspaces in SPN block cipher

D. I. Trifonov ; D. B. Fomin

Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 58-76.

Résumé

Let there exist subsets of $\mathbb{F}_2^n$ that the non-linear layer of an SP-network maps to some other subset of $\mathbb{F}_2^n$. We study the possibility of existence of subsets of $\mathbb{F}_2^n$ that are invariant under the SP-layer. It is shown that subspaces invariant under nonlinear transformations from some classes are not preserved by any matrix without nonzero elements of the field extension $\mathbb{F}_2$. The paper also studies the question of the existence of invariant subsets of the form $A_{i_1} \times \ldots \times A_{i_m}$, where $n = m \cdot n’$, $A_{i_j} \subseteq \mathbb{F}_2^{n’}$, $j = 1, \ldots, m$. Some properties of such invariant sets of the round function of the SP-layer are proved on the basis of the graph-theoretic and group-theoretic approaches. We study the capacity of these sets and, using additional assumptions, show that $A_{i_j}$, $j = 1, \ldots,m$, should be cosets of some subspaces of $\left(\mathbb{F}_2^{n’}, +\right)$ of equal size. A constructive way of constructing such sets is proposed.

Détail

Keywords: SP-network, SPN, invariant subspaces.

Bibliographie

[1] Malyshev F. M., “The duality of differential and linear methods in cryptography”, Matem. Vopr. Kriptogr., 5:3 (2014), 35–48

[2] Matsui M., “Linear cryptanalysis method for DES Cipher”, LNCS, 765, 1994, 386–397 | Zbl

[3] Malyshev F. M., Trifonov D. I., “Diffusion properties of XSLP-ciphers”, Matem. Vopr. Kriptogr., 7:3 (2016), 47–60 (in Russian) | MR | Zbl

[4] Daemon J., Rijmen V., The Design of Rijndael: AES — The Advanced Encryption Standard, Springer, Berlin–Heidelberg, 2002, 238 pp. | MR

[5] Sidel'nikov V. M., “Cross-correlation of sequences”, Problemy Kibernetiki, 1971, no. 24, 15–42 (in Russian) | Zbl

[6] Nyberg K., “Differentially uniform mappings for cryptography”, LNCS, 765, 1994, 55–64 | MR | Zbl

[7] Bilgin B., Nikova S., Nikov V., et al., Threshold Implementations of all $3\times 3$ and $4\times 4$ S-boxes, IACR Cryptology ePrint Archive, , 2012 http://eprint.iacr.org/2012/300

[8] Bora A., Tolga M. S., Ercan B., “Classifying 8-bit to 8-bit S-boxes based on power mappings from the point of DDT and LAT distributions”, LNCS, 5130, 2008, 123–133 | MR | Zbl

[9] Biryukov A., De Cannière C., Braeken A., Preneel B., “A toolbox for cryptanalysis: Linear and affine equivalence algorithms”, LNCS, 2656, 2003, 33–50 | MR | Zbl

[10] Leander G., Poschmann A., “On the classification of 4 bit S-boxes”, LNCS, 4547, 2007, 159–176 | MR | Zbl

[11] Saarinen M. J. O., “Cryptographic analysis of all $4\times 4$-bit S-boxes”, LNCS, 7118, 2012, 118–133 | MR

[12] Menyachikhin A. V., “Spectral-linear and spectral-differential methods for generating S-boxes having almost optimal cryptographic parameters”, Matem. Vopr. Kriptogr., 8:2 (2017), 97–116 | MR | Zbl

[13] Fomin D. B., “New classes of 8-bit permutations based on a butterfly structure”, Matem. Vopr. Kriptogr., 10:2 (2019), 169–180 | MR | Zbl

[14] Fomin D. B., “Construction of permutations on the space $V_{2m}$ by means of $(2m, m)$-functions”, Matem. Vopr. Kriptogr., 11:3 (2020), 121–138 (in Russian) | Zbl

[15] Fomin D. B., “On the algebraic degree and differential uniformity of permutations on the space $V_{2m}$ constructed via $(2m,m)$-functions”, Matem. Vopr. Kriptogr., 11:4 (2020), 133–149 (in Russian) | MR | Zbl

[16] Feistel H., “Cryptography and computer privacy”, Scientific American, 225:5 (1973), 15–23 | DOI

[17] Feistel N., Notz W. A., Smith J. L., “Some cryptographic techniques for machine to machine data communications”, Proc. IEEE, 63:11 (1975), 1554 | DOI

[18] Webster A. F., Tavares S. E., “On the design of S-boxes”, LNCS, 218, 1986, 523–534

[19] Augot D., Finiasz M., Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes, IACR Cryptology ePrint Archive, , 2014 http://eprint.iacr.org/2014/566

[20] Augot D., Finiasz M., “Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions”, IEEE Intern. Symp. Inform. Theory, 2013, 1551–1555

[21] Barreto P., Rijmen V., The KHAZAD Legacy-Level Block Cipher, Submission to NESSIE, 2000 https://www.researchgate.net/publication/228924670_The_Khazad_legacy-level_block_cipher

[22] Gupta K. C., Ray I. G., “On constructions of involutory MDS matrices”, LNCS, 7918, 2013, 43–60 | MR | Zbl

[23] Junod P., Vaudenay S., “Perfect diffusion primitives for block ciphers building efficient MDS matrices”, LNCS, 3357, 2004, 84–99 | MR

[24] Nakahara J. Jr., Abrahao E., “A new involutory MDS matrix for the AES”, Intern. J. Network Security, 9:2 (2009), 109–116

[25] Poschmann A., Lightweight Cryptography — Cryptographic Engineering for a Pervasive World, IACR Cryptology ePrint Archive, , 2009 http://eprint.iacr.org/2009/516

[26] Anashkin A. V., “Complete description of a class of MDS-matrices over finite field of characteristic 2”, Matem. Vopr. Kriptogr., 8:4 (2017), 5–28 (in Russian) | Zbl

[27] GOST R 34.12-2015. Information Technology. Cryptographic Data Security. Block Ciphers, Standartinform, M., 2015 (in Russian)

[28] “D.STVL.9 — Ongoing Research Areas in Symmetric Cryptography”, ECRYPT, 2008, 108 pp.

[29] Pogorelov B. A., Pudovkina M. A., “Combinatorial characterization of $XL$-layers”, Matem. Vopr. Kriptogr., 4:3 (2013), 99–129 (in Russian) | Zbl

[30] Pogorelov B. A., Pudovkina M. A., “On the distance from permutations to imprimitive groups for a fixed system of imprimitivity”, Discr. Math. Appl., 4:2 (2013), 95–108 | MR

[31] Pogorelov B. A., Pudovkina M. A., “On the distance from permutations to the union of all imprimitive groups with identical parameters of imprimitivity systems”, Discr. Math. Appl., 24:3 (2014), 163–173 | MR | MR | Zbl

[32] Pudovkina M. A., “On probabilities of $r$-round differences of a Markov XSL block cipher with a reducible linear transformation”, Prikladnaya Diskretnaya Matematika. Prilozheniye, 2014, no. 7, 52–54 (in Russian)

[33] Standaert F. X., Piret G., Rouvroy G., et al., “ICEBERG : An involutional cipher efficient for block encryption in reconfigurable hardware”, LNCS, 3017, 2004, 279–299 | Zbl

[34] Burov D. A., Pogorelov B. A., “An attack on 6 rounds of KHAZAD”, Matem. Vopr. Kriptogr., 7:2 (2016), 35–46 | MR | Zbl

[35] Burov D. A., Pogorelov B. A., “The permutation group insight on the diffusion property of linear mappings”, Matem. Vopr. Kriptogr., 9:2 (2018), 47–58 | MR | Zbl

[36] Burov D. A., “Subgroups of Cartesian Product of Groups that are Invariant on Nonlinear Layer”, Diskretnaya Matematika, 31:4 (2019), 3–19 (in Russian)

[37] Lidl R., Niederreiter H., Finite Fields, Cambridge University Press, Cambridge, 1984 | MR | MR

[38] Gluhov M. M., Elizarov V. P., Nechaev A. A., Algebra, Study Book, Gelous ARV, M., 2003 (in Russian)

[39] Sim S. M., Khoo K., Oggier F. E., Peyrin T., “Lightweight MDS involution matrices”, FSE, 2015, 471–493 | Zbl

[40] Coy Puente O., de la Cruz Jiménez R. A., “Construction of orthomorphic MDS matrices with primitive characteristic polynomial”, CTCrypt'20, 2020 https://ctcrypt.ru/files/files/Oliver | MR

[41] Khan A. A., Murtaza G., Efficient Implementation of Grand Cru with TI C6x+ Processor, , 2011 http://eprint.iacr.org/2011/385

[42] Watanabe D., Furuya S., Yoshida H., et al., “A new keystream generator MUGI”, LNCS, 2365, 2002, 179–194 | Zbl

[43] Halevi S., Coppersmith D., Jutla C. S., Scream: A Software-Efficient Stream Cipher, IACR Cryptology ePrint Archive, , 2002 http://eprint.iacr.org/2002/019

[44] The New European Schemes for Signatures, Integrity and Encryption (NESSIE), , 2003 http://www.cryptonessie.org

[45] Daeman J., Knudsen L. R., Rijmen V., “The block cipher SQUARE”, FSE'97, Lecture Notes in Computer Science, 1267, 1997, 149–156 | DOI

[46] Agievich S. V., Galinskiy V. A., Mikulich N. D., Kharin Yu. S., BelT Block Cipher (in Russian)

[47] GOST R 34.11-2012. Information Technology. Cryptographic Data Security. Hash Function, Standartinform, M., 2012 (in Russian)

[48] Biryukov A., Perrin L., Udovenko A., “Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1”, LNCS, 9665, 2016, 372–402 | MR | Zbl

[49] Perrin L., Partitions in the S-Box of Streebog and Kuznyechik, Cryptology ePrint Archive, , 2019 https://eprint.iacr.org/2019/092

[50] Gorchinskiy Yu. N., “On homomorphisms of multibase universal algebras in connection with cryptographic applications”, Trudy po Diskretnoy Matematike, 1 (1997), 67–84 (in Russian) | MR | Zbl

[51] Todo Y., Leander G., Sasaki Y., Nonlinear Invariant Attack — Practical Attack on Full SCREAM, iSCREAM, and Midori64, Cryptology ePrint Archive, , 2016 https://eprint.iacr.org/2016/732 | MR

[52] Burov D. A., “About existence of the special nonlinear invariants for round functions of XSL-ciphers”, Diskretnaya Matematika, 33:2 (2021), 31–45 (in Russian) | MR