# American Institute of Mathematical Sciences

May  2019, 13(2): 235-251. doi: 10.3934/amc.2019016

## Type-preserving matrices and security of block ciphers

 1 DISIM, Università degli Studi dell'Aquila, Via Vetoio, 67100 Coppito (AQ), Italy 2 Dipartimento di Matematica, Università degli Studi di Trento, Via Sommarive 14, 38123 Povo (TN), Italy

* Corresponding author: Riccardo Aragona

Received  March 2018 Revised  November 2018 Published  February 2019

Fund Project: The first author is member of of INdAM-GNSAGA (Italy) and he thankfully acknowledges support by DISIM of the University of L'Aquila and by MIUR-Italy via PRIN 2015TW9LSR "Group theory and applications". The authors are grateful to the anonymous referees for their insightful comments and suggestions

We introduce a new property for mixing layers which guarantees protection against algebraic attacks based on the imprimitivity of the group generated by the round functions. Mixing layers satisfying this property are called non-type-preserving. Our main result is to characterize such mixing layers by providing a list of necessary and sufficient conditions on the structure of their underlying binary matrices. Then we show how several families of linear maps are non-type-preserving, including the mixing layers of AES, GOST and PRESENT. Finally we prove that the group generated by the round functions of an SPN cipher with addition modulo $2^n$ as key mixing function is primitive if its mixing layer satisfies this property.

Citation: Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016
##### References:
 [1] R. J. Anderson, E. Biham and L. R. Knudsen, SERPENT: A new block cipher proposal, Fast Software Encryption, Lecture Notes in Comput. Sci. 1372 (1998), 222–238.Google Scholar [2] K. Aoki, et al., Camellia: A 128-bit block cipher suitable for multiple platforms-design and analysis, Selected Areas in Cryptography, Lecture Notes in Comput. Sci., 2012 (2000), 39–56. doi: 10.1007/3-540-44983-3_4. Google Scholar [3] R. Aragona, M. Calderini, R. Civino, M. Sala and I. Zappatore, Wave-shaped round functions and primitive groups, Adv. Math. Commun., 13 (2019), 67-88. doi: 10.3934/amc.2019004. Google Scholar [4] R. Aragona, M. Calderini, A. Tortora and M. Tota, On the primitivity of PRESENT and other lightweight ciphers, Journal of Algebra and Its Applications, 17 (2018), 1850115 (16 pages). doi: 10.1142/S0219498818501153. Google Scholar [5] R. Aragona, A. Caranti, F. Dalla Volta and M. Sala, On the group generated by the round functions of translation based ciphers over arbitrary fields, Finite Fields Appl., 25 (2014), 293-305. doi: 10.1016/j.ffa.2013.10.005. Google Scholar [6] R. Aragona, A. Caranti and M. Sala, The group generated by the round functions of a GOST-like cipher, Ann. Mat. Pura Appl., 196 (2016), 1-17. doi: 10.1007/s10231-016-0559-6. Google Scholar [7] A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, IACR Cryptology ePrint Archive, 2016.Google Scholar [8] A. Bogdanov et al., PRESENT: An ultra-lightweight block cipher, CHES '07, Lecture Notes in Comput. Sci., 4727 (2007), 450–466.Google Scholar [9] C. Burwick, et al., MARS-a candidate cipher for AES, NIST AES Proposal, 268 (1998).Google Scholar [10] M. Calderini, A note on some algebraic trapdoors for block ciphers, Adv. Math. Commun., 12 (2018), 515-524. doi: 10.3934/amc.2018030. Google Scholar [11] M. Calderini and M. Sala, Elementary abelian regular subgroups as hidden sums for cryptographic trapdoors, preprint, arXiv: 1702.00581, [math.GR], 2017.Google Scholar [12] P. J. Cameron, Permutation Groups, London Mathematical Society Student Texts, 45, Cambridge University Press, Cambridge, 1999. doi: 10.1017/CBO9780511623677. Google Scholar [13] A. Caranti, F. Dalla Volta and M. Sala, An application of the O'Nan-Scott theorem to the group generated by the round functions of an AES-like cipher, Des. Codes Cryptogr., 52 (2009), 293-301. doi: 10.1007/s10623-009-9283-1. Google Scholar [14] A. Caranti, F. Dalla Volta and M. Sala, On some block ciphers and imprimitive groups, Appl. Algebra Engrg. Comm. Comput., 20 (2009), 339-350. doi: 10.1007/s00200-009-0100-x. Google Scholar [15] D. Coppersmith and E. Grossman, Generators for certain alternating groups with applications to cryptography, SIAM J. Appl. Math., 29 (1975), 624-627. doi: 10.1137/0129051. Google Scholar [16] J. Daemen and V. Rijmen, The design of Rijndael: AES – the Advanced Encryption Standard, Information Security and Cryptography, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-04722-4. Google Scholar [17] S. M. Dehnavi, A. M. Rishakani, M. M. Shamsabad, H. Maimani and E. Pasha, Cryptographic Properties of Addition Modulo $2^n$, IACR Cryptology ePrint Archive, 2016.Google Scholar [18] V. Dolmatov, GOST 2814789: Encryption, decryption, and message authentication code (MAC) algorithms, Technical report, 2010. Available from http://tools.ietf.org/html/rfc5830.Google Scholar [19] E. Goursat, Sur les substitutions orthogonales et les divisions régulières de l'espace, Ann. Sci. École Norm. Sup., 6 (1889), 9-102. doi: 10.24033/asens.317. Google Scholar [20] Jr. B. S. Kaliski, R. L. Rivest and A. T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), J. Cryptology, 1 (1988), 3-36. doi: 10.1007/BF00206323. Google Scholar [21] O. Kazymyrov, R. Oliynykov and H. Raddum, Influence of addition modulo $2^n$ on algebraic attacks, Cryptogr. Commun., 8 (2016), 277-289. doi: 10.1007/s12095-015-0136-7. Google Scholar [22] X. Lai and J. L. Massey, A proposal for a new block encryption standard, Advances in Cryptology – EUROCRYPT '90, Lecture Notes in Comput. Sci., 473 (1990), 389–404. doi: 10.1007/3-540-46877-3_35. Google Scholar [23] D. Mukhopadhyay and D. RoyChowdhury, Key Mixing in Block Ciphers through Addition modulo $2^n$, IACR Cryptology ePrint Archive, 2005.Google Scholar [24] K. G. Paterson, Imprimitive permutation groups and trapdoors in iterated block ciphers, Fast Software Encryption, Lecture Notes in Comput. Sci., 1636 (1999), 201–214.Google Scholar [25] R. L. Rivest, M. J. W. Robshaw, R. Sidney and Y. L. Yin, The RC6$^{TM}$ block cipher, In First Advanced Encryption Standard (AES) Conference, (1998).Google Scholar [26] C. E. Shannon, Communication theory of secrecy systems, Bell System Tech., 28 (1949), 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x. Google Scholar [27] R. Sparr and R. Wernsdorf, Group theoretic properties of Rijndael-like ciphers, Discrete Appl. Math., 156 (2008), 3139-3149. doi: 10.1016/j.dam.2007.12.011. Google Scholar [28] F. X. Standaert, G. Piret, N. Gershenfeld and J. J. Quisquater, SEA: A scalable encryption algorithm for small embedded applications, Smart Card Research and Advanced Applications – CARDIS '06, Lecture Notes in Comput. Sci. 3928 (2006), 222–236.Google Scholar [29] R. Wernsdorf, The round functions of RIJNDAEL generate the alternating group, Fast Software Encryption, Lecture Notes in Comput. Sci. 2365 (2002), 143–148. doi: 10.1007/3-540-45661-9_11. Google Scholar [30] R. Wernsdorf, The one-round functions of the DES generate the alternating group, Advances in cryptology-EUROCRYPT '92, Lecture Notes in Comput. Sci., 658 (1993), 99–112. doi: 10.1007/3-540-47555-9_9. Google Scholar [31] R. Wernsdorf, The round functions of SERPENT generate the alternating group, 2000, Available from http://csrc.nist.gov/archive/aes/round2/comments/20000512-rwernsdorf.pdf.Google Scholar

show all references

##### References:
 [1] R. J. Anderson, E. Biham and L. R. Knudsen, SERPENT: A new block cipher proposal, Fast Software Encryption, Lecture Notes in Comput. Sci. 1372 (1998), 222–238.Google Scholar [2] K. Aoki, et al., Camellia: A 128-bit block cipher suitable for multiple platforms-design and analysis, Selected Areas in Cryptography, Lecture Notes in Comput. Sci., 2012 (2000), 39–56. doi: 10.1007/3-540-44983-3_4. Google Scholar [3] R. Aragona, M. Calderini, R. Civino, M. Sala and I. Zappatore, Wave-shaped round functions and primitive groups, Adv. Math. Commun., 13 (2019), 67-88. doi: 10.3934/amc.2019004. Google Scholar [4] R. Aragona, M. Calderini, A. Tortora and M. Tota, On the primitivity of PRESENT and other lightweight ciphers, Journal of Algebra and Its Applications, 17 (2018), 1850115 (16 pages). doi: 10.1142/S0219498818501153. Google Scholar [5] R. Aragona, A. Caranti, F. Dalla Volta and M. Sala, On the group generated by the round functions of translation based ciphers over arbitrary fields, Finite Fields Appl., 25 (2014), 293-305. doi: 10.1016/j.ffa.2013.10.005. Google Scholar [6] R. Aragona, A. Caranti and M. Sala, The group generated by the round functions of a GOST-like cipher, Ann. Mat. Pura Appl., 196 (2016), 1-17. doi: 10.1007/s10231-016-0559-6. Google Scholar [7] A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, IACR Cryptology ePrint Archive, 2016.Google Scholar [8] A. Bogdanov et al., PRESENT: An ultra-lightweight block cipher, CHES '07, Lecture Notes in Comput. Sci., 4727 (2007), 450–466.Google Scholar [9] C. Burwick, et al., MARS-a candidate cipher for AES, NIST AES Proposal, 268 (1998).Google Scholar [10] M. Calderini, A note on some algebraic trapdoors for block ciphers, Adv. Math. Commun., 12 (2018), 515-524. doi: 10.3934/amc.2018030. Google Scholar [11] M. Calderini and M. Sala, Elementary abelian regular subgroups as hidden sums for cryptographic trapdoors, preprint, arXiv: 1702.00581, [math.GR], 2017.Google Scholar [12] P. J. Cameron, Permutation Groups, London Mathematical Society Student Texts, 45, Cambridge University Press, Cambridge, 1999. doi: 10.1017/CBO9780511623677. Google Scholar [13] A. Caranti, F. Dalla Volta and M. Sala, An application of the O'Nan-Scott theorem to the group generated by the round functions of an AES-like cipher, Des. Codes Cryptogr., 52 (2009), 293-301. doi: 10.1007/s10623-009-9283-1. Google Scholar [14] A. Caranti, F. Dalla Volta and M. Sala, On some block ciphers and imprimitive groups, Appl. Algebra Engrg. Comm. Comput., 20 (2009), 339-350. doi: 10.1007/s00200-009-0100-x. Google Scholar [15] D. Coppersmith and E. Grossman, Generators for certain alternating groups with applications to cryptography, SIAM J. Appl. Math., 29 (1975), 624-627. doi: 10.1137/0129051. Google Scholar [16] J. Daemen and V. Rijmen, The design of Rijndael: AES – the Advanced Encryption Standard, Information Security and Cryptography, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-04722-4. Google Scholar [17] S. M. Dehnavi, A. M. Rishakani, M. M. Shamsabad, H. Maimani and E. Pasha, Cryptographic Properties of Addition Modulo $2^n$, IACR Cryptology ePrint Archive, 2016.Google Scholar [18] V. Dolmatov, GOST 2814789: Encryption, decryption, and message authentication code (MAC) algorithms, Technical report, 2010. Available from http://tools.ietf.org/html/rfc5830.Google Scholar [19] E. Goursat, Sur les substitutions orthogonales et les divisions régulières de l'espace, Ann. Sci. École Norm. Sup., 6 (1889), 9-102. doi: 10.24033/asens.317. Google Scholar [20] Jr. B. S. Kaliski, R. L. Rivest and A. T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), J. Cryptology, 1 (1988), 3-36. doi: 10.1007/BF00206323. Google Scholar [21] O. Kazymyrov, R. Oliynykov and H. Raddum, Influence of addition modulo $2^n$ on algebraic attacks, Cryptogr. Commun., 8 (2016), 277-289. doi: 10.1007/s12095-015-0136-7. Google Scholar [22] X. Lai and J. L. Massey, A proposal for a new block encryption standard, Advances in Cryptology – EUROCRYPT '90, Lecture Notes in Comput. Sci., 473 (1990), 389–404. doi: 10.1007/3-540-46877-3_35. Google Scholar [23] D. Mukhopadhyay and D. RoyChowdhury, Key Mixing in Block Ciphers through Addition modulo $2^n$, IACR Cryptology ePrint Archive, 2005.Google Scholar [24] K. G. Paterson, Imprimitive permutation groups and trapdoors in iterated block ciphers, Fast Software Encryption, Lecture Notes in Comput. Sci., 1636 (1999), 201–214.Google Scholar [25] R. L. Rivest, M. J. W. Robshaw, R. Sidney and Y. L. Yin, The RC6$^{TM}$ block cipher, In First Advanced Encryption Standard (AES) Conference, (1998).Google Scholar [26] C. E. Shannon, Communication theory of secrecy systems, Bell System Tech., 28 (1949), 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x. Google Scholar [27] R. Sparr and R. Wernsdorf, Group theoretic properties of Rijndael-like ciphers, Discrete Appl. Math., 156 (2008), 3139-3149. doi: 10.1016/j.dam.2007.12.011. Google Scholar [28] F. X. Standaert, G. Piret, N. Gershenfeld and J. J. Quisquater, SEA: A scalable encryption algorithm for small embedded applications, Smart Card Research and Advanced Applications – CARDIS '06, Lecture Notes in Comput. Sci. 3928 (2006), 222–236.Google Scholar [29] R. Wernsdorf, The round functions of RIJNDAEL generate the alternating group, Fast Software Encryption, Lecture Notes in Comput. Sci. 2365 (2002), 143–148. doi: 10.1007/3-540-45661-9_11. Google Scholar [30] R. Wernsdorf, The one-round functions of the DES generate the alternating group, Advances in cryptology-EUROCRYPT '92, Lecture Notes in Comput. Sci., 658 (1993), 99–112. doi: 10.1007/3-540-47555-9_9. Google Scholar [31] R. Wernsdorf, The round functions of SERPENT generate the alternating group, 2000, Available from http://csrc.nist.gov/archive/aes/round2/comments/20000512-rwernsdorf.pdf.Google Scholar
 [1] Riccardo Aragona, Marco Calderini, Roberto Civino, Massimiliano Sala, Ilaria Zappatore. Wave-shaped round functions and primitive groups. Advances in Mathematics of Communications, 2019, 13 (1) : 67-88. doi: 10.3934/amc.2019004 [2] Fabrizio Colombo, Irene Sabadini, Frank Sommen. The Fueter primitive of biaxially monogenic functions. Communications on Pure & Applied Analysis, 2014, 13 (2) : 657-672. doi: 10.3934/cpaa.2014.13.657 [3] Pascal Hubert, Gabriela Schmithüsen. Infinite translation surfaces with infinitely generated Veech groups. Journal of Modern Dynamics, 2010, 4 (4) : 715-732. doi: 10.3934/jmd.2010.4.715 [4] Nir Avni. Spectral and mixing properties of actions of amenable groups. Electronic Research Announcements, 2005, 11: 57-63. [5] Heping Liu, Yu Liu. Refinable functions on the Heisenberg group. Communications on Pure & Applied Analysis, 2007, 6 (3) : 775-787. doi: 10.3934/cpaa.2007.6.775 [6] Eldho K. Thomas, Nadya Markin, Frédérique Oggier. On Abelian group representability of finite groups. Advances in Mathematics of Communications, 2014, 8 (2) : 139-152. doi: 10.3934/amc.2014.8.139 [7] Tómas Chacón-Rebollo, Macarena Gómez-Mármol, Samuele Rubino. On the existence and asymptotic stability of solutions for unsteady mixing-layer models. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 421-436. doi: 10.3934/dcds.2014.34.421 [8] Krzysztof Frączek, M. Lemańczyk, E. Lesigne. Mild mixing property for special flows under piecewise constant functions. Discrete & Continuous Dynamical Systems - A, 2007, 19 (4) : 691-710. doi: 10.3934/dcds.2007.19.691 [9] Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413 [10] Alexander Moreto. Complex group algebras of finite groups: Brauer's Problem 1. Electronic Research Announcements, 2005, 11: 34-39. [11] Fausto Ferrari, Qing Liu, Juan Manfredi. On the characterization of $p$-harmonic functions on the Heisenberg group by mean value properties. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2779-2793. doi: 10.3934/dcds.2014.34.2779 [12] Yury Neretin. The group of diffeomorphisms of the circle: Reproducing kernels and analogs of spherical functions. Journal of Geometric Mechanics, 2017, 9 (2) : 207-225. doi: 10.3934/jgm.2017009 [13] Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003 [14] Raf Cluckers, Julia Gordon, Immanuel Halupczok. Motivic functions, integrability, and applications to harmonic analysis on $p$-adic groups. Electronic Research Announcements, 2014, 21: 137-152. doi: 10.3934/era.2014.21.137 [15] François Gay-Balmaz, Cesare Tronci, Cornelia Vizman. Geometric dynamics on the automorphism group of principal bundles: Geodesic flows, dual pairs and chromomorphism groups. Journal of Geometric Mechanics, 2013, 5 (1) : 39-84. doi: 10.3934/jgm.2013.5.39 [16] Kengo Matsumoto. K-groups of the full group actions on one-sided topological Markov shifts. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3753-3765. doi: 10.3934/dcds.2013.33.3753 [17] Krzysztof Frączek, Leonid Polterovich. Growth and mixing. Journal of Modern Dynamics, 2008, 2 (2) : 315-338. doi: 10.3934/jmd.2008.2.315 [18] Koray Karabina, Berkant Ustaoglu. Invalid-curve attacks on (hyper)elliptic curve cryptosystems. Advances in Mathematics of Communications, 2010, 4 (3) : 307-321. doi: 10.3934/amc.2010.4.307 [19] Cheng Wang. The primitive equations formulated in mean vorticity. Conference Publications, 2003, 2003 (Special) : 880-887. doi: 10.3934/proc.2003.2003.880 [20] Roger Temam, D. Wirosoetisno. Exponential approximations for the primitive equations of the ocean. Discrete & Continuous Dynamical Systems - B, 2007, 7 (2) : 425-440. doi: 10.3934/dcdsb.2007.7.425

2018 Impact Factor: 0.879