Open Access Open Access  Restricted Access Subscription or Fee Access

Strength Assessment of Modern Cryptosystems Using Methods of the Analysis Based on the Solutions of Combined Equations

(*) Corresponding author

Authors' affiliations



Encryption algorithm GOST 28147-89 (hereinafter GOST) is Russian national standard of symmetric encryption. Many systems of information security are based on computation complexity of algorithm GOST. Our research is about possibility of methods of the analysis based on the solutions of combined equations. 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 plain/cipher text. Extended linearization (XL) method is evaluated as a method for solving the nonlinear system of equations. We observe attack to three rounds of GOST using XL methods. The research has shown that for 32-round GOST system is consist of 5376 quadratic equations, which characterize dependencies between inputs and outputs of S-blocks. The total number of variables is 2048 and the system contains 9472 monomials. Algebraic attacks (and many others like linear, differential methods) are needed to know substitution tables of encryption algorithms. However S-boxes of GOST are additional secret element of encryption, therefore this work presents software implementation and complexity evaluation of computing secret S-boxes. Also the part of the work devoted to finding the influence of S-Boxes to resistance of GOST algorithm against linear cryptanalysis. The universal algorithm for searching particular layouts of S-Boxes, which are vulnerable to linear cryptanalysis is presented. The possibility of building of efficient linear statistical expressions for simplified GOST with weak S-Boxes has been shown. This research is aimed to ensuring that certain arbitrary S-Box layouts are not weak when they are not fixed. Applicability of the presented method was tested by analyzing S-Boxes used in GOST. Application of the designed method made it possible to discover a number of weak S-Boxes, which make the overall cryptographic strength of GOST much lower.
Copyright © 2015 Praise Worthy Prize - All rights reserved.


GOST; GOST⊕; S-Box; Systems of Multivariate Quadratic Equations; Algebraic Cryptanalysis; Extended Linearization (XL) Method; Secret Key; Linear Cryptanalysis; Probability

Full Text:



Saarinen M.-J. A Chosen Key Attack Against the Secret S-boxes of GOST. Retrieved from

Shannon C. E. Communication Theory of Secrecy Systems. Bell Systems Technical Journal, Vol. 28, pp. 656- 715, 1949.

Courtois N. Algebraic Complexity Reduction and Cryptanalysis of GOST. Preprint retrieved November 19, 2011 from

Matsui M. Linear Cryptanalysis Method for DES Cipher. Advances in Cryptology – EUROCRYPT’93, Springer-Verlag, p.386, 1998.

Popov V., Kurepkin I., Leontiev S. 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. Retrieved January 2006 from

Courtois N., Klimov A., Patarin J., Shamir A. Efficient Algorithms for solving Overdefined System of Multivariate Polynomial Equations. Eurocrypt'2000, LNCS 1807. Springer-Verlag, pp. 392-407, 2000.

Jayakumar M., Christopher T. Secure Key Based Key Scheduling for DES and TDES Algorithms, (2013) International Review on Computers and Software (IRECOS), 7 (8), pp. 1535-1540.

Schneier B. Applied Cryptography, Protocols, Algorithms and Source Code in C (Second Edition) (John Wiley and Sons, Inc. 1996).

Babenko L.K., Ishchukova E.A., Maro E.A. Theory and Practice of Cryptography Solutions for Secure Information Systems. GOST Encryption Algorithm and Approaches to its Analysis. IGI Global book series Advances in Information Security, Privacy, and Ethics (AISPE) Book Series, USA, 2013. pp. 34 – 62.

Babenko L.K., Ishchukova E.A., Maro E.A. Research about Strength of GOST 28147-89 Encryption Algorithm. Proceedings of the 5th international conference on Security of information and networks (SIN 2012). ACM, New York, NY, USA, 2012. pp. 138 – 142.

Babenko L.K., Ishchukova E.A. Differential Analysis of GOST Encryption Algorithm. Proceedings of the 3rd International Conference of Security of Information and Networks (SIN 2010). ACM, New York, NY, USA,2010. pp. 149 – 157.


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2023 Praise Worthy Prize