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.

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

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

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

[5]

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

[6]

A. Bannier and E. Filiol, Partition-based Trapdoor Ciphers, Partition-Based Trapdoor Ciphers. InTech, 2017.

[7]

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72. doi: 10.1007/BF00630563.

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

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

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

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

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

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

[14]

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

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

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

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

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

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

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

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

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.

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

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

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

[5]

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

[6]

A. Bannier and E. Filiol, Partition-based Trapdoor Ciphers, Partition-Based Trapdoor Ciphers. InTech, 2017.

[7]

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72. doi: 10.1007/BF00630563.

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

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

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

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

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

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

[14]

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

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

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

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

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

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

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

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

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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Nadya Markin, Eldho K. Thomas, Frédérique Oggier. On group violations of inequalities in five subgroups. Advances in Mathematics of Communications, 2016, 10 (4) : 871-893. doi: 10.3934/amc.2016047

[14]

Katarzyna Grabowska, Marcin Zając. The Tulczyjew triple in mechanics on a Lie group. Journal of Geometric Mechanics, 2016, 8 (4) : 413-435. doi: 10.3934/jgm.2016014

[15]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637

[16]

Yuri Berest, Alimjon Eshmatov, Farkhod Eshmatov. On subgroups of the Dixmier group and Calogero-Moser spaces. Electronic Research Announcements, 2011, 18: 12-21. doi: 10.3934/era.2011.18.12

[17]

Sze-Bi Hsu, Bernold Fiedler, Hsiu-Hau Lin. Classification of potential flows under renormalization group transformation. Discrete & Continuous Dynamical Systems - B, 2016, 21 (2) : 437-446. doi: 10.3934/dcdsb.2016.21.437

[18]

S. A. Krat. On pairs of metrics invariant under a cocompact action of a group. Electronic Research Announcements, 2001, 7: 79-86.

[19]

Franz W. Kamber and Peter W. Michor. Completing Lie algebra actions to Lie group actions. Electronic Research Announcements, 2004, 10: 1-10.

[20]

Van Cyr, Bryna Kra. The automorphism group of a minimal shift of stretched exponential growth. Journal of Modern Dynamics, 2016, 10: 483-495. doi: 10.3934/jmd.2016.10.483

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (44)
  • HTML views (87)
  • Cited by (0)

Other articles
by authors

[Back to Top]