Type-preserving matrices and security of block ciphers

Riccardo Aragona; Alessio Meneghetti

doi:10.3934/amc.2019016

Article Contents

2019, Volume 13, Issue 2: 235-251. Doi: 10.3934/amc.2019016

This issue Previous Article Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants Next Article A new construction of rotation symmetric bent functions with maximal algebraic degree

Type-preserving matrices and security of block ciphers

Riccardo Aragona^1, , and
Alessio Meneghetti^2,

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
^* Corresponding author: Riccardo Aragona

Received: February 28, 2018

Revised: October 31, 2018

Published: January 2019

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

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 20B15, 20B35, 94A60.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[7]	A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, IACR Cryptology ePrint Archive, 2016.
[8]	A. Bogdanov et al., PRESENT: An ultra-lightweight block cipher, CHES '07, Lecture Notes in Comput. Sci., 4727 (2007), 450–466.
[9]	C. Burwick, et al., MARS-a candidate cipher for AES, NIST AES Proposal, 268 (1998).
[10]	M. Calderini, A note on some algebraic trapdoors for block ciphers, Adv. Math. Commun., 12 (2018), 515-524. doi: 10.3934/amc.2018030.
[11]	M. Calderini and M. Sala, Elementary abelian regular subgroups as hidden sums for cryptographic trapdoors, preprint, arXiv: 1702.00581, [math.GR], 2017.
[12]	P. J. Cameron, Permutation Groups, London Mathematical Society Student Texts, 45, Cambridge University Press, Cambridge, 1999. doi: 10.1017/CBO9780511623677.
[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.
[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.
[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.
[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.
[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.
[18]	V. Dolmatov, GOST 2814789: Encryption, decryption, and message authentication code (MAC) algorithms, Technical report, 2010. Available from http://tools.ietf.org/html/rfc5830.
[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.
[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.
[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.
[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.
[23]	D. Mukhopadhyay and D. RoyChowdhury, Key Mixing in Block Ciphers through Addition modulo $2^n$, IACR Cryptology ePrint Archive, 2005.
[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.
[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).
[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.
[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.
[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.
[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.
[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.
[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.