August  2018, 12(3): 515-524. doi: 10.3934/amc.2018030

A note on some algebraic trapdoors for block ciphers

Department of Informatics, University of Bergen, Norway

Received  June 2017 Revised  March 2018 Published  July 2018

We provide sufficient conditions to guarantee that a translation based cipher is not vulnerable with respect to the partition-based trapdoor. This trapdoor has been introduced, recently, by Bannier et al. (2016) and it generalizes that introduced by Paterson in 1999. Moreover, we discuss the fact that studying the group generated by the round functions of a block cipher may not be sufficient to guarantee security against these trapdoors for the cipher.

Citation: Marco Calderini. A note on some algebraic trapdoors for block ciphers. Advances in Mathematics of Communications, 2018, 12 (3) : 515-524. doi: 10.3934/amc.2018030
References:
[1]

R. Anderson, E. Biham and L. Knudsen, SERPENT: A new block cipher proposal, in: Fast Software Encryption, LNCS, Springer, Berlin, 1372 (1998), 222–238. Google Scholar

[2]

R. Aragona, M. Calderini, A. Tortora and M. Tota, Primitivity of PRESENT and other lightweight ciphers, Journal of Algebra and Its Applications, 17 (2018), 1850115, 16pp. doi: 10.1142/S0219498818501153.  Google Scholar

[3]

R. AragonaM. CalderiniD. Maccauro and M. Sala, On weak differential uniformity of vectorial Boolean functions as a cryptographic criterion, Appl. Algebra Engrg. Comm. Comput., 27 (2016), 359-372.  doi: 10.1007/s00200-016-0285-8.  Google Scholar

[4]

R. AragonaA. 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

[5]

A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, preprint, https://eprint.iacr.org/2016/493.pdf. Google Scholar

[6]

A. Bannier and E. Filiol, Partition-based Trapdoor Ciphers, Partition-Based Trapdoor Ciphers. InTech, 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. Andrey Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin and C. Vikkelsoe, PRESENT: An ultra-lightweight block cipher, in: Proc. of CHES 2007, LNCS, Springer, 4727 (2007), 450–466. doi: 10.1007/978-3-540-74735-2_31.  Google Scholar

[9]

A. CarantiF. Dalla Volta and M. Sala, On some block ciphers and imprimitive groups, Appl. Algebra Engrg. Comm. Comput., 20 (2009), 229-350.  doi: 10.1007/s00200-009-0100-x.  Google Scholar

[10]

A. CarantiF. 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, Designs, Codes and Cryptography, 52 (2009), 293-301.  doi: 10.1007/s10623-009-9283-1.  Google Scholar

[11]

D. Coppersmith and E. Grossman, Generators for certain alternating groups with applications to cryptography, SIAM Journal on Applied Mathematics, 29 (1975), 624-627.  doi: 10.1137/0129051.  Google Scholar

[12]

J. Daemen and V. Rijmen, The Design of Rijndael: AES-the Advanced Encryption Standard, Springer Science & Business Media, 2002. doi: 10.1007/978-3-662-04722-4.  Google Scholar

[13]

S. Even and O. Goldreich, DES-Like functions can generate the alternating group, IEEE Trans. Inform. Theory, 29 (1983), 863-865.  doi: 10.1109/TIT.1983.1056752.  Google Scholar

[14]

C. Harpes and J. L. Massey, Partitioning cryptanalysis, Fast Software Encryption, LNCS, Springer, Berlin, 1267 (1997), 13-27.  doi: 10.1007/BFb0052331.  Google Scholar

[15]

B. S. KaliskiR. L. Rivest and A. T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), Journal of Cryptology, 1 (1988), 3-36.  doi: 10.1007/BF00206323.  Google Scholar

[16]

M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology – EUROCRYPT '93, LNCS, Springer, Berlin, 765 (1994), 386–397. doi: 10.1007/3-540-48285-7_33.  Google Scholar

[17]

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

[18]

M. SeanK. Paterson and P. Wild, A weak cipher that generates the symmetric group, Journal of Cryptology, 7 (1994), 61-65.  doi: 10.1007/BF00195210.  Google Scholar

[19]

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

[20]

R. Wernsdorf, The round functions of SERPENT generate the alternating group, 2000; available at http://csrc.nist.gov/archive/aes/round2/comments/20000512-rwernsdorf.pdf. Google Scholar

[21]

R. Wernsdorf, The round functions of RIJNDAEL generate the alternating group, Fast Software Encryption, LNCS, Springer, Berlin, 2365 (2002), 143–148. doi: 10.1007/3-540-45661-9_11.  Google Scholar

show all references

References:
[1]

R. Anderson, E. Biham and L. Knudsen, SERPENT: A new block cipher proposal, in: Fast Software Encryption, LNCS, Springer, Berlin, 1372 (1998), 222–238. Google Scholar

[2]

R. Aragona, M. Calderini, A. Tortora and M. Tota, Primitivity of PRESENT and other lightweight ciphers, Journal of Algebra and Its Applications, 17 (2018), 1850115, 16pp. doi: 10.1142/S0219498818501153.  Google Scholar

[3]

R. AragonaM. CalderiniD. Maccauro and M. Sala, On weak differential uniformity of vectorial Boolean functions as a cryptographic criterion, Appl. Algebra Engrg. Comm. Comput., 27 (2016), 359-372.  doi: 10.1007/s00200-016-0285-8.  Google Scholar

[4]

R. AragonaA. 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

[5]

A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, preprint, https://eprint.iacr.org/2016/493.pdf. Google Scholar

[6]

A. Bannier and E. Filiol, Partition-based Trapdoor Ciphers, Partition-Based Trapdoor Ciphers. InTech, 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. Andrey Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin and C. Vikkelsoe, PRESENT: An ultra-lightweight block cipher, in: Proc. of CHES 2007, LNCS, Springer, 4727 (2007), 450–466. doi: 10.1007/978-3-540-74735-2_31.  Google Scholar

[9]

A. CarantiF. Dalla Volta and M. Sala, On some block ciphers and imprimitive groups, Appl. Algebra Engrg. Comm. Comput., 20 (2009), 229-350.  doi: 10.1007/s00200-009-0100-x.  Google Scholar

[10]

A. CarantiF. 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, Designs, Codes and Cryptography, 52 (2009), 293-301.  doi: 10.1007/s10623-009-9283-1.  Google Scholar

[11]

D. Coppersmith and E. Grossman, Generators for certain alternating groups with applications to cryptography, SIAM Journal on Applied Mathematics, 29 (1975), 624-627.  doi: 10.1137/0129051.  Google Scholar

[12]

J. Daemen and V. Rijmen, The Design of Rijndael: AES-the Advanced Encryption Standard, Springer Science & Business Media, 2002. doi: 10.1007/978-3-662-04722-4.  Google Scholar

[13]

S. Even and O. Goldreich, DES-Like functions can generate the alternating group, IEEE Trans. Inform. Theory, 29 (1983), 863-865.  doi: 10.1109/TIT.1983.1056752.  Google Scholar

[14]

C. Harpes and J. L. Massey, Partitioning cryptanalysis, Fast Software Encryption, LNCS, Springer, Berlin, 1267 (1997), 13-27.  doi: 10.1007/BFb0052331.  Google Scholar

[15]

B. S. KaliskiR. L. Rivest and A. T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), Journal of Cryptology, 1 (1988), 3-36.  doi: 10.1007/BF00206323.  Google Scholar

[16]

M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology – EUROCRYPT '93, LNCS, Springer, Berlin, 765 (1994), 386–397. doi: 10.1007/3-540-48285-7_33.  Google Scholar

[17]

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

[18]

M. SeanK. Paterson and P. Wild, A weak cipher that generates the symmetric group, Journal of Cryptology, 7 (1994), 61-65.  doi: 10.1007/BF00195210.  Google Scholar

[19]

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

[20]

R. Wernsdorf, The round functions of SERPENT generate the alternating group, 2000; available at http://csrc.nist.gov/archive/aes/round2/comments/20000512-rwernsdorf.pdf. Google Scholar

[21]

R. Wernsdorf, The round functions of RIJNDAEL generate the alternating group, Fast Software Encryption, LNCS, Springer, Berlin, 2365 (2002), 143–148. doi: 10.1007/3-540-45661-9_11.  Google Scholar

Table 1.  AES state
$V_1$$V_2$$V_3$$V_4$
$V_5$$V_6$$V_7$$V_8$
$V_9$$V_{10}$$V_{11}$$V_{12}$
$V_{13}$$V_{14}$$V_{15}$$V_{16}$
$V_1$$V_2$$V_3$$V_4$
$V_5$$V_6$$V_7$$V_8$
$V_9$$V_{10}$$V_{11}$$V_{12}$
$V_{13}$$V_{14}$$V_{15}$$V_{16}$
Table 2.  AES wall
$ \color{orange}{V_1}$$V_2$$V_3$$V_4$ $\color{orange}{V_1}$$V_2$$V_3$$V_4$ $\color{orange}{V_1}$$V_2$$V_3$$V_4$
$V_5$$\color{orange}{V_6}$$V_7$$V_8$$\mathop {SR}\limits_ \mapsto $ $\color{orange}{V_5}$$V_6$$V_7$$V_8$ $\mathop {MC}\limits_ \mapsto $ $\color{orange}{V_5}$$V_6$$V_7$$V_8$
$V_9$$V_{10}$$\color{orange}{V_{11}}$$V_{12}$ $\color{orange}{V_9}$$V_{10}$$V_{11}$$V_{12}$ $\color{orange}{V_9}$$V_{10}$$V_{11}$$V_{12}$
$V_{13}$$V_{14}$$V_{15}$$\color{orange}{V_{16}}$ $\color{orange}{V_{13}}$$V_{14}$$V_{15}$$V_{16}$ $\color{orange}{V_{13}}$$V_{14}$$V_{15}$$V_{16}$
$ \color{orange}{V_1}$$V_2$$V_3$$V_4$ $\color{orange}{V_1}$$V_2$$V_3$$V_4$ $\color{orange}{V_1}$$V_2$$V_3$$V_4$
$V_5$$\color{orange}{V_6}$$V_7$$V_8$$\mathop {SR}\limits_ \mapsto $ $\color{orange}{V_5}$$V_6$$V_7$$V_8$ $\mathop {MC}\limits_ \mapsto $ $\color{orange}{V_5}$$V_6$$V_7$$V_8$
$V_9$$V_{10}$$\color{orange}{V_{11}}$$V_{12}$ $\color{orange}{V_9}$$V_{10}$$V_{11}$$V_{12}$ $\color{orange}{V_9}$$V_{10}$$V_{11}$$V_{12}$
$V_{13}$$V_{14}$$V_{15}$$\color{orange}{V_{16}}$ $\color{orange}{V_{13}}$$V_{14}$$V_{15}$$V_{16}$ $\color{orange}{V_{13}}$$V_{14}$$V_{15}$$V_{16}$
[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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83

[10]

Stefan Haller, Tomasz Rybicki, Josef Teichmann. Smooth perfectness for the group of diffeomorphisms. Journal of Geometric Mechanics, 2013, 5 (3) : 281-294. doi: 10.3934/jgm.2013.5.281

[11]

Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015

[12]

Woochul Jung, Keonhee Lee, Carlos Morales, Jumi Oh. Rigidity of random group actions. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6845-6854. doi: 10.3934/dcds.2020130

[13]

Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167

[14]

Kesong Yan, Qian Liu, Fanping Zeng. Classification of transitive group actions. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021089

[15]

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

[16]

Dongmei Zheng, Ercai Chen, Jiahong Yang. On large deviations for amenable group actions. Discrete & Continuous Dynamical Systems, 2016, 36 (12) : 7191-7206. doi: 10.3934/dcds.2016113

[17]

Yves Guivarc'h. On the spectrum of a large subgroup of a semisimple group. Journal of Modern Dynamics, 2008, 2 (1) : 15-42. doi: 10.3934/jmd.2008.2.15

[18]

Marcelo Sobottka. Topological quasi-group shifts. Discrete & Continuous Dynamical Systems, 2007, 17 (1) : 77-93. doi: 10.3934/dcds.2007.17.77

[19]

Dandan Cheng, Qian Hao, Zhiming Li. Scale pressure for amenable group actions. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1091-1102. doi: 10.3934/cpaa.2021008

[20]

Jean-Francois Bertazzon. Symbolic approach and induction in the Heisenberg group. Discrete & Continuous Dynamical Systems, 2012, 32 (4) : 1209-1229. doi: 10.3934/dcds.2012.32.1209

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (249)
  • HTML views (220)
  • Cited by (1)

Other articles
by authors

[Back to Top]