x2y1

⊕

x1y4

⊕

x1y2=0

y2y1

⊕

x4y4

⊕

x3y2

⊕

x1y3=0

x4y4

⊕

x3y4

⊕

x3y3

⊕

x3y2

⊕

x2y3

⊕

x2y2

⊕

x1y4

⊕

x1y3

⊕

x1y2

⊕

x1y1=0

x4y3

⊕

x4y2

⊕

x4y1

⊕

x3y4

⊕

x3y1

⊕

x2y4

⊕

x2y2

⊕

x2y1

⊕

x1y4

⊕

x1y3

⊕

x1y2=0

For two GOST rounds showed in Figure 2, the initial system depicting encryption transformation includes

336 equations, 128 unknowns and 576 various monomials. Using linearization method without additional re-

ducing will not allow finding the solution as the number of equations is less than the number of monomials. Us-

ing GOST structure one can substitute output bits of substitution boxes for evaluated values by formulas:

Y1 = (PL

⊕

CR)>>>11, for the first round,

Y2 = (PR

⊕

CL)>>>11, for the second round.

After substitution the system will obtain 64 unknowns instead of 128 and the number of monomials in the

equations will be reduced to 160. The requirement of linearization applicability will be fulfilled, thus, we will

apply linearization method to find encryption key for two GOST rounds in the second attack stage. As it was

mentioned above, the attack complexity defines the complexity of linear system solution, so the cryptanalysis

L. Babenko, E. Maro

15

Figure 2. Two GOST rounds in ordinary substitution

mode.

complexity of two GOST rounds is 1603 ≈ 222, which is in 242 times less than the complexity of brute force at-

tack (264).

The attack on two rounds of GOST algorithm was similar to the attack on two rounds of GOST encryption

algorithm. The system of equations remains the same for GOST algorithm but round key calculation with the

obtained input values of substitution boxes was affected. Being aware that addition is performed according to

modulo 232, translation between digits was verified when sum calculation. For example, let us take original at-

tack data as following:

Plain text 58b7e5e8a13a

Cipher text c3a09d847e1aa55e

The input value of substitution boxes was calculated:

X1 = 95771861

X2 = 2DA91C85

If we know substitution box inputs, we can calculate round encryption keys by formulas:

K = PR + X, if X > PR

K = 232 − PR + X, if X ≤ PR

We have found the following keys for two rounds:

K1 = AF8E7727

K2 = AF8E7727

When passing to the analysis of three GOST encryption rounds illustrated in Figure 3, the system with 504

equations, 192 unknowns and 864 various monomials.

Reduction of the number of the system unknowns for three rounds was not successful and searching of the

solution was executed with XL method. When applying eXtended Linearization method the authors consider

every substitution box individually. In this case D parameter of XL method is equal to 3, i.e. each of 21 equa-

tions for substitution box is multiplied by the unknown to 1 extent. Then we obtain 189 equations for one subs-

titution box, the majority of these equations are linearly independent. For three encryption rounds after resulting

in additional equations, the system includes 4536 equations with 192 unknowns and 2208 various monomials.

The system can be solved by linearization. Attack complexity for GOST encryption rounds will be 22083 ≈

234 that is in 262 times less than complexity of finding round keys with brute force method.

For 32-round GOST encryption algorithm the system will contain 48,384 equations with 2048 unknowns and

23,552 various monomials. Attack complexity will be 23,5523 ≈ 244.

Note that implementation of GOST attack algorithms mentioned above with GOST

⊕

cipher attack is com-

plicated by translation between digits when addition modulo 232 with round key. Implementation of unfixed

L. Babenko, E. Maro

16

Figure 3. Three rounds of GOST encryption algorithm.

substitution tables is the difference between attack on GOST algorithms and GOST in comparison with other

box ciphers, that every time provokes the necessity to restore substitution tables and generate system of equa-

tions. It is noteworthy that there is a possibility of efficient parallelization of equation system generation for

substitution boxes and solution of simultaneous linear equations.

Nowadays the implementation of eXtended Linearization algorithms for GOST full-function 32-round algo-

rithm is still under investigation.

This research was supported by Russian Foundation for Basic Research (RFBR), projects No. 12-07-31032

and 12-07-33007.

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 (Cor-

rected 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). Pro-

ceedings 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., Mei er, 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.

L. Babenko, E. Maro

17

http://dx.doi.org/10.1007/3-540-48405-1_2

[9] Courtois, N., Klimov, A., Patarin, J. and Sha mir, 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 Piep rzy k, 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

Se- lected Areas in Cryptography, Springer-Verlag, New York, 103-111. http://dx.doi.org/10.1007/3-540-45537-X_8

[12] Courtois, N. a nd 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 10 th 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 PRINTCi-

pher-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 Ma ro, 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