Algebraic Cryptanalysis of GOST Encryption Algorithm

Ludmila Babenko, Ekaterina Maro

Department of Information Security, Southern Federal University, Taganrog, Russia.

DOI: 10.4236/jcc.2014.24002                

Abstract

This paper observes approaches to algebraic analysis of GOST 28147-89 encryption algorithm (also known as simply GOST), which is the basis of most secure information systems in Russia. The general idea of algebraic analysis is based on the representation of initial encryption algorithm as a system of multivariate quadratic equations, which define relations between a secret key and a cipher text. Extended linearization method is evaluated as a method for solving the nonlinear sys- tem of equations.

Keywords

Encryption Algorithm GOST; GOST; S-Box; Systems of Multivariate Quadratic Equations; Algebraic Cryptanalysis; Extended Linearization Method; Gaussian Elimination

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Courtois, N. (2011) Algebraic Complexity Reduction and Cryptanalysis of GOST. http://eprint.iacr.org/2011/626
[2]	Shannon, C.E. (1949) Communication Theory of Secrecy Systems. Bell Systems Technical Journal, 28, 656-715. http://dx.doi.org/10.1002/j.1538-7305.1949.tb00928.x
[3]	Becker, T. and Weispfenning, V. (1993) Gröbner Bases: A Computational Approach to Commutative Algebra (Corrected Edition). Springer-Verlag, New York.
[4]	Cox, D.A., Little, J.B. and O’Shea, D. (1996) Ideals, Varieties, and Algorithms. 2nd Edition, Springer-Verlag, New York.
[5]	Kalkbrener, M. (1999) On the Complexity of Gröbner Bases Conversion. Journal of Symbolic Computation, 28, 265-273.
[6]	Faugère, J.-C. (2002) A New Efficient Algorithm for Computing Gr?bner Bases without Reduction to Zero (F5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC’02), Association for Computing Machinery, Inc., New York, 75-83.
[7]	Courtois, N., Goubin, L., Meier, W. and Tacier, J.-D. (2002) Solving Underdefined Systems of Multivariate Quadratic Equations. In: Public Key Cryptography, Lecture Notes in Computer Science, Vol. 2274, Springer, New York, 211- 227. http://dx.doi.org/10.1007/3-540-45664-3_15
[8]	Kipnis, A. and Shamir, A. (1999) Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. Advances in Cryptology-Crypto’99, Lecture Notes in Computer Science, Vol. 1666, Springer, New York, 19-30. http://dx.doi.org/10.1007/3-540-48405-1_2
[9]	Courtois, N., Klimov, A., Patarin, J. and Shamir, A. (2000) Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. Advances in Cryptology—EUROCRYPT, Lecture Notes in Computer Science, Vol. 1807, New York, Springer, 392-407.
[10]	Courtois, N. and Pieprzyk, J. (2002) Cryptanalysis of block ciphers with overdefined systems of equations. Asiacrypt, Lecture Notes in Computer Science, Vol. 2501, Springer, New York, 267-287.
[11]	Ferguson, N., Schroeppel, R. and Whiting, D. (2001) A Simple Algebraic Representation of Rijndael. Proceedings of Selected Areas in Cryptography, Springer-Verlag, New York, 103-111. http://dx.doi.org/10.1007/3-540-45537-X_8
[12]	Courtois, N. and Debraize, B. (2008) Specific S-Box Criteria in Algebraic Attacks on Block Ciphers with Several Known Plaintexts. Research in Cryptology, Lecture Notes in Computer Science, Vol. 4945, Springer, New York, 100- 113. http://dx.doi.org/10.1007/978-3-540-88353-1_9
[13]	Weinmann, R.-P. (2009) Algebraic Methods in Block Cipher Cryptanalysis. Ph.D. Thesis, Technische Universit?t, Darmstadt.
[14]	Courtois, N. and Debraize, B. (2008) Algebraic Description and Simultaneous Linear Approximations of Addition in Snow 2.0. The 10th International Conference on Information and Communications Security (ICICS), Lecture Notes in Computer Science, Vol. 5308, Springer, New York, 328-344.
[15]	Courtois, N. and Bard, G.V. (2007) Algebraic Cryptanalysis of the Data Encryption Standard. In Cryptography and Coding, 11th IMA Conference, Springer, New York, 152-169.
[16]	Bard, G.V. (2009) Algebraic Cryptanalysis. Springer, New York. http://dx.doi.org/10.1007/978-0-387-88757-9
[17]	Bulygin, S. (2011) Algebraic Cryptanalysis of the Round-Reduced and Side Channel Analysis of the Full PRINTCipher-48. http://eprint.iacr.org/2011/287.pdf
[18]	Saarinen, M.-J. (1998) A Chosen Key Attack against the Secret S-boxes of GOST. http://www.researchgate.net/publication/2598060_A_chosen_key_attack_against_the_secret_S-boxes_of_GOST
[19]	Babenko, L.K., Ishchukova, E.A. and Maro, E.A. (2011) Algebraic Analysis of GOST Encryption Algorithm. Pro- ceedings of the 4th International Conference of Security of Information and Networks, Association for Computing Machinery Inc., New York, 57-62.
[20]	Popov, V., Kurepkin, I. and Leontiev, S. (2006) Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms. http://www.ietf.org/rfc/rfc4357