2 y57 ff7 fsf fc0 sc0 ls0">⊕
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 CryptologyEUROCRYPT, 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