GOST (block cipher)

Last updated
GOST 28147-89 (Magma)
GOSTDiagram.png
Diagram of GOST
General
Designers USSR, KGB, 8th Department
First published1994-05-23 (declassified)
Successors GOST hash function, Kuznyechik
Certification GOST standard
Cipher detail
Key sizes 256 bits
Block sizes 64 bits
Structure Feistel network
Rounds 32
Best public cryptanalysis
In 2011 several authors discovered more significant flaws in GOST, being able to attack the full 32-round GOST with arbitrary keys for the first time. It has even been called "a deeply flawed cipher" by Nicolas Courtois. [1]

The GOST block cipher (Magma), defined in the standard GOST 28147-89 (RFC 5830), is a Soviet and Russian government standard symmetric key block cipher with a block size of 64 bits. The original standard, published in 1989, did not give the cipher any name, but the most recent revision of the standard, GOST R 34.12-2015 (RFC 7801, RFC 8891), specifies that it may be referred to as Magma. [2] The GOST hash function is based on this cipher. The new standard also specifies a new 128-bit block cipher called Kuznyechik.

Contents

Developed in the 1970s, the standard had been marked "Top Secret" and then downgraded to "Secret" in 1990. Shortly after the dissolution of the USSR, it was declassified and it was released to the public in 1994. GOST 28147 was a Soviet alternative to the United States standard algorithm, DES. [3] Thus, the two are very similar in structure.

The algorithm

GOST has a 64-bit block size and a key length of 256 bits. Its S-boxes can be secret, and they contain about 354 (log2(16!8)) bits of secret information, so the effective key size can be increased to 610 bits; however, a chosen-key attack can recover the contents of the S-boxes in approximately 232 encryptions. [4]

GOST is a Feistel network of 32 rounds. Its round function is very simple: add a 32-bit subkey modulo 232, put the result through a layer of S-boxes, and rotate that result left by 11 bits. The result of that is the output of the round function. In the adjacent diagram, one line represents 32 bits.

The subkeys are chosen in a pre-specified order. The key schedule is very simple: break the 256-bit key into eight 32-bit subkeys, and each subkey is used four times in the algorithm; the first 24 rounds use the key words in order, the last 8 rounds use them in reverse order.

The S-boxes accept a four-bit input and produce a four-bit output. The S-box substitution in the round function consists of eight 4 × 4 S-boxes. The S-boxes are implementation-dependent, thus parties that want to secure their communications using GOST must be using the same S-boxes. For extra security, the S-boxes can be kept secret. In the original standard where GOST was specified, no S-boxes were given, but they were to be supplied somehow. This led to speculation that organizations the government wished to spy on were given weak S-boxes. One GOST chip manufacturer reported that he generated S-boxes himself using a pseudorandom number generator. [5]

For example, the Central Bank of Russian Federation used the following S-boxes:

# S-box
1 4 A 9 2 D 8 0 E 6 B 1 C 7 F 5 3
2 E B 4 C 6 D F A 2 3 8 1 0 7 5 9
3 5 8 1 D A 3 4 2 E F C 7 6 0 9 B
4 7 D A 1 0 8 9 F E 4 6 C B 2 5 3
5 6 C 7 1 5 F D 8 4 A 9 E 0 3 B 2
6 4 B A 0 7 2 1 D 3 6 8 5 9 C F E
7 D B 4 1 3 F 5 9 0 A E 7 6 8 2 C
8 1 F D 0 5 7 A 4 9 2 3 E 6 B 8 C

However, the most recent revision of the standard, GOST R 34.12-2015, adds the missing S-box specification and defines it as follows. [2]

# GOST R 34.12-2015 S-box
1 C 4 6 2 A 5 B 9 E 8 D 7 0 3 F 1
2 6 8 2 3 9 A 5 C 1 E 4 7 B D 0 F
3 B 3 5 8 2 F A D E 1 7 4 C 9 6 0
4 C 8 2 1 D 4 F 6 7 0 A 5 3 E 9 B
5 7 F 5 A 8 1 6 D 0 9 3 E B 4 2 C
6 5 D F 6 9 2 C A B 7 8 1 4 3 E 0
7 8 E 2 5 6 9 1 C F 4 B 0 D A 3 7
8 1 7 E D 0 5 8 3 4 F A 6 9 C B 2

Cryptanalysis of GOST

The latest cryptanalysis of GOST shows that it is secure in a theoretical sense. In practice, the data and memory complexity of the best published attacks has reached the level of practical, while the time complexity of even the best attack is still 2192 when 264 data is available.

Since 2007, several attacks have been developed against reduced-round GOST implementations and/or weak keys. [6] [7]

In 2011 several authors discovered more significant flaws in GOST, being able to attack the full 32-round GOST with arbitrary keys for the first time. It has even been called "a deeply flawed cipher" by Nicolas Courtois. [8] Initial attacks were able to reduce time complexity from 2256 to 2228 at the cost of huge memory requirements, [9] and soon they were improved up to 2178 time complexity (at the cost of 270 memory and 264 data). [10] [11]

In December 2012, Courtois, Gawinecki, and Song improved attacks on GOST by computing only 2101 GOST rounds. [12] Isobe had already published a single key attack on the full GOST cipher, [13] which Dinur, Dunkelman, and Shamir improved upon, reaching 2224 time complexity for 232 data and 236 memory, and 2192 time complexity for 264 data. [14]

Since the attacks reduce the expected strength from 2256 (key length) to around 2178, the cipher can be considered broken. However, this attack is not feasible in practice, as the number of tests to be performed 2178 is out of reach.

Note that for any block cipher with block size of n bits, the maximum amount of plaintext that can be encrypted before rekeying must take place is 2n/2 blocks, due to the birthday paradox, [15] and none of the aforementioned attacks require less than 232 data.

See also

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">International Data Encryption Algorithm</span> Symmetric-key block cipher

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher, the Proposed Encryption Standard (PES).

In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis.

Articles related to cryptography include:

In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear vectorial Boolean function.

<span class="mw-page-title-main">Eli Biham</span> Israeli cryptographer and cryptanalyst

Eli Biham is an Israeli cryptographer and cryptanalyst who is a professor at the Technion - Israel Institute of Technology Computer Science department. From 2008 to 2013, Biham was the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate school. Biham invented (publicly) differential cryptanalysis, for which he received his Ph.D., while working under Adi Shamir. It had been invented before by a team at IBM during their Data Encryption Standard work; the National Security Agency told IBM to keep the discovery secret.

In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard. One version, alternatively named DTD-1, saw commercial use in the 1970s for electronic banking.

In cryptography, Camellia is a symmetric key block cipher with a block size of 128 bits and key sizes of 128, 192 and 256 bits. It was jointly developed by Mitsubishi Electric and NTT of Japan. The cipher has been approved for use by the ISO/IEC, the European Union's NESSIE project and the Japanese CRYPTREC project. The cipher has security levels and processing abilities comparable to the Advanced Encryption Standard.

In cryptography, CAST-256 is a symmetric-key block cipher published in June 1998. It was submitted as a candidate for the Advanced Encryption Standard (AES); however, it was not among the five AES finalists. It is an extension of an earlier cipher, CAST-128; both were designed according to the "CAST" design methodology invented by Carlisle Adams and Stafford Tavares. Howard Heys and Michael Wiener also contributed to the design.

In cryptography, MISTY1 is a block cipher designed in 1995 by Mitsuru Matsui and others for Mitsubishi Electric.

<span class="mw-page-title-main">DES-X</span> Block cipher

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

In cryptography, the eXtended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.

In cryptography, M6 is a block cipher proposed by Hitachi in 1997 for use in the IEEE 1394 FireWire standard. The design allows some freedom in choosing a few of the cipher's operations, so M6 is considered a family of ciphers. Due to export controls, M6 has not been fully published; nevertheless, a partial description of the algorithm based on a draft standard is given by Kelsey, et al. in their cryptanalysis of this family of ciphers.

The following outline is provided as an overview of and topical guide to cryptography:

<span class="mw-page-title-main">Twofish</span> Block cipher

In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Twofish is related to the earlier block cipher Blowfish.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

References

  1. ↑ Courtois, Nicolas T. (9 May 2011). "Security Evaluation of GOST 28147-89 In View Of International Standardisation". Cryptology ePrint Archive. IACR. Until 2011 researchers unanimously agreed that GOST could or should be very secure, which was summarised in 2010 in these words: despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken". Unhappily, it was recently discovered that GOST can be broken and is a deeply flawed cipher
  2. 1 2 "GOST R 34.12-2015 (Russian only)" (PDF). Archived from the original (PDF) on 2015-09-24. Retrieved 2015-08-28.
  3. ↑ Fleischmann, Ewan; Gorski, Michael; Hühne, Jan-Hendrik; Lucks, Stefan (2009). "Key Recovery Attack on Full GOST Block Cipher with Zero Time and Memory". Published as ISO/IEC JTC. 1.
  4. ↑ Saarinen, Markku-Juhani (1998). "A chosen key attack against the secret S-boxes of GOST". We show that a simple "black box" chosen-key attack against GOST can recover secret S-boxes with approximately 2^32 encryptions{{cite journal}}: Cite journal requires |journal= (help)
  5. ↑ Schneier, Bruce (1996). Applied cryptography : protocols, algorithms, and source code in C (2. ed., [Nachdr.] ed.). New York [u.a.]: Wiley. ISBN   978-0-471-11709-4.
  6. ↑ Eli Biham; Orr Dunkelman; Nathan Keller (2007). "Improved Slide Attacks" (PDF).
  7. ↑ Orhun Kara (2008). "Reflection Cryptanalysis of Some Ciphers".
  8. ↑ Courtois, Nicolas T. (9 May 2011). "Security Evaluation of GOST 28147-89 In View Of International Standardisation". Cryptology ePrint Archive. IACR. Until 2011 researchers unanimously agreed that GOST could or should be very secure, which was summarised in 2010 in these words: despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken". Unhappily, it was recently discovered that GOST can be broken and is a deeply flawed cipher
  9. ↑ Nicolas T. Courtois; Michał Miształ (2011). "Differential Cryptanalysis of GOST". IACR.
  10. ↑ Nicolas T. Courtois (2012). "An Improved Differential Attack on Full GOST" (PDF). IACR.
  11. ↑ Courtois, Nicolas T. (Jun 13, 2011). "Algebraic Complexity Reduction and Cryptanalysis of GOST" (PDF). Cryptology ePrint Archive. IACR.
  12. ↑ Nicolas T. Courtois; Jerzy A. Gawinecki; Guangyan Song (2012). "CONTRADICTION IMMUNITY AND GUESS-THEN-DETERMINE ATTACKS ON GOST" (PDF). Versita. Retrieved 2014-08-25.
  13. ↑ Isobe, Takanori (2011). "A Single-Key Attack on the Full GOST Block Cipher". Fast Software Encryption. Lecture Notes in Computer Science. Vol. 6733. pp. 290–305. doi:10.1007/978-3-642-21702-9_17. ISBN   978-3-642-21701-2.
  14. ↑ Dinur, Itai; Dunkelman, Orr; Shamir, Adi (2012). "Improved Attacks on Full GOST". Fast Software Encryption. Lecture Notes in Computer Science. Vol. 7549. pp. 9–28. doi: 10.1007/978-3-642-34047-5_2 . ISBN   978-3-642-34046-8.
  15. ↑ "Draft of ISO/IEC JTC 1/SC 27 Standing Document No. 12 (SD12) on the Assessment of Cryptographic Techniques and Key Lengths, 4th edition" (PDF). 2016.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.