research-article

Algebraic analysis of GOST encryption algorithm

Authors:

Ludmila Babenko,

Evgeniya Ishchukova,

Ekaterina MaroAuthors Info & Claims

SIN '11: Proceedings of the 4th international conference on Security of information and networks

Pages 57 - 62

https://doi.org/10.1145/2070425.2070437

Published: 14 November 2011 Publication History

Get Access

Abstract

This paper is devoted to the investigation of GOST algorithm with regard to its resistance against algebraic cryptanalysis. GOST algorithm is a state standard of Russian Federation. Its characteristic feature is the use of variable S-blocks and simple mathematical operations. It is considered that any initial values of S-blocks provide enough strength to resist any attacks. 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 system of equations.

The most challenging problem of the analysis is caused by addition modulo 2n in GOST. In order to make the analysis simpler we have considered a simplified scheme for GOST, in which the operation of addition modulo 2n is replaced by the addition modulo 2 (denoted as GOST+). We have proposed an analysis algorithm of GOST according to experimental data.

The research has shown that 32-round GOST is described by a system 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. Generation of the system for a single-round GOST demands circa 14 hours (with AMD Athlon X2DualCore processor 3800+, 1Gb RAM).

References

[1]

Shannon C.E. Communication theory of secret systems. Bell System Technical Journal 28, 704 (1949)

Crossref

Google Scholar

[2]

Nicolas Courtois, Gregory V. Bard: Algebraic Cryptanalysis of the Data Encryption Standard, In 11-th IMA Conference, Cirencester, UK, 18--20 December 2007, Springer LNCS 4887.

Digital Library

Google Scholar

[3]

Patarin J. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms; in Eurocrypt'96, Springer Verlag, pp. 33--48.

Digital Library

Google Scholar

[4]

Nicolas Courtois and Josef Pieprzyk, Cryptanalysis of Block Ciphers with Overdefined Systems of Equations In Yuliang Zheng, editor, ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 267--287. Springer, 2002.

Digital Library

Google Scholar

[5]

Bruno Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhDthesis, 1965.

Google Scholar

[6]

Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra 139 (1999) pp. 61--88.

Crossref

Google Scholar

[7]

Jean-Charles Faugère, A new efficient algorithm for computing Gröbner basis without reduction to 0 F5, In T. Mora, editor, Proceeding of ISSAC, pages 75--83, ACM Press, July 2002.

Digital Library

Google Scholar

[8]

A.Kipnis, A. Shamir. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. Crypto99, LNCS 142,144. Springer-Verlag, pp.19--31.

Digital Library

Google Scholar

[9]

L. Babenko, E. Ishchukova, Differential Analysis GOST Encryption Algorithm // Proceedings of the 3rd International Conference of Security of Information and Networks (SIN 2010), p.149--157. ACM, New York, 2010.

Digital Library

Google Scholar

[10]

A. Biryukov and D. Wagner. Advanced Slide Attacks. In Proc. EUROCRYPT 2000, LNCS 1807, pp.589--606, Springer, 2000.

Digital Library

Google Scholar

[11]

Orhun Kara. Reflection Attacks on Product Ciphers. Cryptology ePrint Archive, Report 2007/043, 2007. http://eprint.iacr.org/

Google Scholar

[12]

Nicolas Courtois and Blandine Debraize: Algebraic Description and Simultaneous Linear Approximations of Addition in Snow 2.0., In ICICS 2008, 10th International Conference on Information and Communications Security, 20 - 22 October, 2008, Birmingham, UK. In LNCS 5308, pp. 328--344, Springer, 2008.

Digital Library

Google Scholar

[13]

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

Digital Library

Google Scholar

Cited By

View all

Babenko LMaro E(2014)Algebraic Cryptanalysis of GOST Encryption AlgorithmJournal of Computer and Communications10.4236/jcc.2014.2400202:04(10-17)Online publication date: 2014
https://doi.org/10.4236/jcc.2014.24002
Babenko LIshchukova EMaro E(2013)GOST Encryption Algorithm and Approaches to its AnalysisTheory and Practice of Cryptography Solutions for Secure Information Systems10.4018/978-1-4666-4030-6.ch002(34-61)Online publication date: 2013
https://doi.org/10.4018/978-1-4666-4030-6.ch002
Babenko LIshchukova EMaro EGaur MElçi AMakarevich OOrgun MSingh V(2012)Research about strength of GOST 28147-89 encryption algorithmProceedings of the Fifth International Conference on Security of Information and Networks10.1145/2388576.2388595(138-142)Online publication date: 25-Oct-2012
https://dl.acm.org/doi/10.1145/2388576.2388595

Index Terms

Algebraic analysis of GOST encryption algorithm
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Differential analysis of GOST encryption algorithm
SIN '10: Proceedings of the 3rd international conference on Security of information and networks

In this article we explore the resistance of the GOST 28147-89 algorithm (commonly referred to as GOST) to the attack based on differential cryptanalysis. GOST algorithm is used as a national standard in the Russian Federation. GOST uses variable ...
Algebraic Fault Analysis on GOST for Key Recovery and Reverse Engineering
FDTC '14: Proceedings of the 2014 Workshop on Fault Diagnosis and Tolerance in Cryptography

GOST is a well-known block cipher as the official encryption standard for the Russian Federation. A special feature of GOST is that its eight S-boxes can be secret. However, most of the researches on GOST assume that the design of these S-boxes is known. ...
Cryptanalysis of the Round-Reduced GOST Hash Function
Information Security and Cryptology
Abstract
The GOST hash function, defined in GOST R 34.11-2012, was selected as the new Russian standard on August 7, 2012. It is designed to replace the old Russian standard GOST R 34.11-94. The GOST hash function is an AES-based primitive and is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIN '11: Proceedings of the 4th international conference on Security of information and networks

November 2011

276 pages

ISBN:9781450310208

DOI:10.1145/2070425

General Chairs:
Mehmet A. Orgun
Macquarie University, Australia
,
Atilla Elçi
Süleyman Demirel University, Turkey
,
Oleg Makarevich
Southern Federal University, Russia
,
Sorin Huss
Techniche Universitat Darmstadt, Germany
,
Program Chairs:
Josef Pieprzyk
Macquarie University, Australia
,
Lyudmila Babenko
Southern Federal University, Russia
,
Alexander Chefranov
Eastern Mediterranean University, North Cyprus
,
Rajan Shankaran
Macquarie University, Australia

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SDU: Suleyman Demirel University
AOARD: Asian Office of Aerospace Research and Development
RDECOM: U.S. Army Research, Development and Engineering Command
US Army ITC-PAC Asian Research Office
AFOSR: AFOSR
ONRGlobal: U.S. Office of Naval Research Global
Macquarie University-Sydney

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 November 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIN 2011

SIN 2011: The 4th International Conference on Security of Information and Networks

November 14 - 19, 2011

Sydney, Australia

Acceptance Rates

Overall Acceptance Rate 102 of 289 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
145
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Babenko LMaro E(2014)Algebraic Cryptanalysis of GOST Encryption AlgorithmJournal of Computer and Communications10.4236/jcc.2014.2400202:04(10-17)Online publication date: 2014
https://doi.org/10.4236/jcc.2014.24002
Babenko LIshchukova EMaro E(2013)GOST Encryption Algorithm and Approaches to its AnalysisTheory and Practice of Cryptography Solutions for Secure Information Systems10.4018/978-1-4666-4030-6.ch002(34-61)Online publication date: 2013
https://doi.org/10.4018/978-1-4666-4030-6.ch002
Babenko LIshchukova EMaro EGaur MElçi AMakarevich OOrgun MSingh V(2012)Research about strength of GOST 28147-89 encryption algorithmProceedings of the Fifth International Conference on Security of Information and Networks10.1145/2388576.2388595(138-142)Online publication date: 25-Oct-2012
https://dl.acm.org/doi/10.1145/2388576.2388595

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Differential analysis of GOST encryption algorithm

Algebraic Fault Analysis on GOST for Key Recovery and Reverse Engineering

Cryptanalysis of the Round-Reduced GOST Hash Function