American Institute of Mathematical Sciences

Advanced
November  2020, 14(4): 727-743. doi: 10.3934/amc.2020093

Some group-theoretical results on Feistel Networks in a long-key scenario

Riccardo Aragona 1,, , Marco Calderini 2, and  Roberto Civino 1,

1. 

DISIM, University of L'Aquila, Via Vetoio, 67100 Coppito (AQ), Italy
2. 

Department of Informatics, University of Bergen, Postboks 7803, N-5020 Bergen, Norway

* Corresponding author: Riccardo Aragona

Received  December 2019 Revised  May 2020 Published  November 2020 Early access  July 2020

Fund Project: All the authors are members of INdAM-GNSAGA (Italy). Part of this work was carried out during Marco Calderini's visit at University of L'Aquila, supported by the Meltzer Research Fund and Trond Mohn Foundation

The study of the trapdoors that can be hidden in a block cipher is and has always been a high-interest topic in symmetric cryptography. In this paper we focus on Feistel-network-like ciphers in a classical long-key scenario and we investigate some conditions which make such a construction immune to the partition-based attack introduced recently by Bannier et al.

Keywords: Symmetric Cryptography, Block Cipher, Trapdoor, Group Generated by Round Functions, Partitions.
Mathematics Subject Classification: Primary: 94A60, 20B05; Secondary: 20B35.
Citation: Riccardo Aragona, Marco Calderini, Roberto Civino. Some group-theoretical results on Feistel Networks in a long-key scenario. Advances in Mathematics of Communications, 2020, 14 (4) : 727-743. doi: 10.3934/amc.2020093
References:
[1]

R. Aragona, M. Calderini, R. Civino, M. Sala and I. Zappatore, Wave-shaped round functions and primitive groups, Advances in Mathematics of Communications, 13 (2019), 67-88.  doi: 10.3934/amc.2019004.  Google Scholar

[2]

R. Aragona, M. Calderini, A. Tortora and M. Tota, On the primitivity of PRESENT and other lightweight ciphers, J. Algebra Appl., 17 (2018), 1850115 (16 pages). doi: 10.1142/S0219498818501153.  Google Scholar

[3]

R. Aragona, A. Caranti and M. Sala, The group generated by the round functions of a GOST-like cipher, Ann. Mat. Pura Appl., 196 (2017), 1-17.  doi: 10.1007/s10231-016-0559-6.  Google Scholar

[4]

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

[5]

A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, Cryptology ePrint Archive, Report 2016/493, 2016. Google Scholar

[6]

A. Bannier and E. Filiol, Partition-based Trapdoor Ciphers, IntechOpen, London, 2017. Google Scholar

[7]

E. Biham and A. Shamir, Differential cryptanalysis of {DES-like} cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  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]

M. Calderini, A note on some algebraic trapdoors for block ciphers, Advances in Mathematics of Communications, 12 (2018), 515-524.  doi: 10.3934/amc.2018030.  Google Scholar

[10]

M. Calderini, R. Civino and M. Sala, On properties of translation groups in the affine general linear group with applications to cryptography, preprint, arXiv: math.GR/1702.00581, 2017. Google Scholar

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Federal information processing standards publication, Data Encryption Standard and Others, National Bureau of Standards, US Department of Commerce, 1977. Google Scholar

[16]

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

[17]

C. Harpes and J. L. Massey, Partitioning cryptanalysis,, Fast Software Encryption, Lecture Notes in Comput. Sci., 1267 (1997), 13–27. doi: 10.1007/BFb0052331.  Google Scholar

[18]

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

[19]

K. G. Paterson, Imprimitive permutation groups and trapdoors in iterated block ciphers,, Fast Software Encryption, Lecture Notes in Comput. Sci., 1636 (1999), 201–214. doi: 10.1007/3-540-48519-8_15.  Google Scholar

[20]

J. Petrillo, Goursat's other theorem, The College Mathematics Journal, 40 (2009), 119-124.   Google Scholar

[21]

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

[22]

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

[23]

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

[24]

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

[25]

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

show all references

References:
[1]

R. Aragona, M. Calderini, R. Civino, M. Sala and I. Zappatore, Wave-shaped round functions and primitive groups, Advances in Mathematics of Communications, 13 (2019), 67-88.  doi: 10.3934/amc.2019004.  Google Scholar

[2]

R. Aragona, M. Calderini, A. Tortora and M. Tota, On the primitivity of PRESENT and other lightweight ciphers, J. Algebra Appl., 17 (2018), 1850115 (16 pages). doi: 10.1142/S0219498818501153.  Google Scholar

[3]

R. Aragona, A. Caranti and M. Sala, The group generated by the round functions of a GOST-like cipher, Ann. Mat. Pura Appl., 196 (2017), 1-17.  doi: 10.1007/s10231-016-0559-6.  Google Scholar

[4]

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

[5]

A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, Cryptology ePrint Archive, Report 2016/493, 2016. Google Scholar

[6]

A. Bannier and E. Filiol, Partition-based Trapdoor Ciphers, IntechOpen, London, 2017. Google Scholar

[7]

E. Biham and A. Shamir, Differential cryptanalysis of {DES-like} cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  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]

M. Calderini, A note on some algebraic trapdoors for block ciphers, Advances in Mathematics of Communications, 12 (2018), 515-524.  doi: 10.3934/amc.2018030.  Google Scholar

[10]

M. Calderini, R. Civino and M. Sala, On properties of translation groups in the affine general linear group with applications to cryptography, preprint, arXiv: math.GR/1702.00581, 2017. Google Scholar

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Federal information processing standards publication, Data Encryption Standard and Others, National Bureau of Standards, US Department of Commerce, 1977. Google Scholar

[16]

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

[17]

C. Harpes and J. L. Massey, Partitioning cryptanalysis,, Fast Software Encryption, Lecture Notes in Comput. Sci., 1267 (1997), 13–27. doi: 10.1007/BFb0052331.  Google Scholar

[18]

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

[19]

K. G. Paterson, Imprimitive permutation groups and trapdoors in iterated block ciphers,, Fast Software Encryption, Lecture Notes in Comput. Sci., 1636 (1999), 201–214. doi: 10.1007/3-540-48519-8_15.  Google Scholar

[20]

J. Petrillo, Goursat's other theorem, The College Mathematics Journal, 40 (2009), 119-124.   Google Scholar

[21]

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

[22]

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

[23]

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

[24]

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

[25]

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

Figure 1.  Round function of an SPN and of a Feistel network
Figure Options

Download full-size image

Download as PowerPoint slide

[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]

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
[3]

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
[4]

Sihem Mesnager, Fengrong Zhang, Yong Zhou. On construction of bent functions involving symmetric functions and their duals. Advances in Mathematics of Communications, 2017, 11 (2) : 347-352. doi: 10.3934/amc.2017027
[5]

Elena Celledoni, Brynjulf Owren. Preserving first integrals with symmetric Lie group methods. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 977-990. doi: 10.3934/dcds.2014.34.977
[6]

Maria Bortos, Joe Gildea, Abidin Kaya, Adrian Korban, Alexander Tylyshchak. New self-dual codes of length 68 from a $ 2 \times 2 $ block matrix construction and group rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020111
[7]

Joe Gildea, Abidin Kaya, Adam Michael Roberts, Rhian Taylor, Alexander Tylyshchak. New self-dual codes from $ 2 \times 2 $ block circulant matrices, group rings and neighbours of neighbours. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021039
[8]

Xiao-Hong Liu, Wei Wu. Coerciveness of some merit functions over symmetric cones. Journal of Industrial & Management Optimization, 2009, 5 (3) : 603-613. doi: 10.3934/jimo.2009.5.603
[9]

Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2021, 15 (4) : 721-736. doi: 10.3934/amc.2020092
[10]

Carlos Matheus, Jean-Christophe Yoccoz. The action of the affine diffeomorphisms on the relative homology group of certain exceptionally symmetric origamis. Journal of Modern Dynamics, 2010, 4 (3) : 453-486. doi: 10.3934/jmd.2010.4.453
[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, 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]

Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017
[14]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
[15]

Thomas W. Cusick, Younhwan Cheon. The weight recursions for the 2-rotation symmetric quartic Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021011
[16]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[17]

Virginie Bonnaillie-Noël, Corentin Léna. Spectral minimal partitions of a sector. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 27-53. doi: 10.3934/dcdsb.2014.19.27
[18]

Tomasz Cieślak. Trudinger-Moser type inequality for radially symmetric functions in a ring and applications to Keller-Segel in a ring. Discrete & Continuous Dynamical Systems - B, 2013, 18 (10) : 2505-2512. doi: 10.3934/dcdsb.2013.18.2505
[19]

Shay Kels, Nira Dyn. Bernstein-type approximation of set-valued functions in the symmetric difference metric. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 1041-1060. doi: 10.3934/dcds.2014.34.1041
[20]

Bingxin Wang, Sihong Su. A New Construction of odd-variable Rotation symmetric Boolean functions with good cryptographic properties. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020115

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (115)
  • HTML views (210)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences