GOST 28147-89
Encyclopedia
The GOST block cipher, defined in the standard GOST 28147-89, is a Soviet and Russian government standard symmetric key block cipher
. Also based on this block cipher is the GOST hash function.
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
. Thus, the two are very similar in structure.
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 (Saarinen, 1998).
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 diagram to the right, 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 - 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
(Schneier, 1996).
For example, the Central Bank of Russian Federation uses the following S-boxes:
!#
!S-Box
|-
!1
|4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3
|-
!2
|14 11 4 12 6 13 15 10 2 3 8 1 0 7 5 9
|-
!3
|5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11
|-
!4
|7 13 10 1 0 8 9 15 14 4 6 12 11 2 5 3
|-
!5
|6 12 7 1 5 15 13 8 4 10 9 14 0 3 11 2
|-
!6
|4 11 10 0 7 2 1 13 3 6 8 5 9 12 15 14
|-
!7
|13 11 4 1 3 15 5 9 0 10 14 7 6 8 2 12
|-
!8
|1 15 13 0 5 7 10 4 9 2 3 14 6 11 8 12
|}>
Another concern is that the avalanche effect
is slower to occur in GOST than in DES. This is because of GOST's lack of an expansion permutation in the round function, as well as its use of a rotation instead of a permutation. Again, this is offset by GOST's increased number of rounds.
There is not much published cryptanalysis of GOST, but a cursory glance says that it seems secure (Schneier, 1996). The large number of rounds and secret S-boxes makes both linear
and differential cryptanalysis
difficult. Its avalanche effect may be slower to occur, but it can propagate over 32 rounds very effectively.
However, GOST is not fully defined by its standard: It does not specify the S-blocks (replacement tables). On the one hand, this can be additional secure information (in addition to key). On the other hand, the following problems arise:
Despite its apparently strong construction, GOST is vulnerable to generic attacks based on its short (64-bit) block size, and should therefore never be used in contexts where more than 232 blocks could be encrypted with the same key.
GOST has been submitted to ISO standardization in 2010. In 2011 severe flaws have been discovered in GOST cipher and it has been called "a deeply flawed cipher" by Nicolas Courtois
. A more detailed cryptanalysis has been published by Courtois
and Miształ in June 2011, demonstrating several attacks reducing attack complexity to
.
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
. Also based on this block cipher is the GOST hash function.
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
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
standard algorithm, DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
. Thus, the two are very similar in structure.
The algorithm
GOST has a 64-bit block sizeBlock size (cryptography)
In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the 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 (Saarinen, 1998).
GOST is a Feistel network of 32 rounds. Its round function is very simple: add a 32-bit subkey modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
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 diagram to the right, 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 - 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
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
(Schneier, 1996).
For example, the Central Bank of Russian Federation uses the following S-boxes:
!S-Box
|-
!1
|4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3
|-
!2
|14 11 4 12 6 13 15 10 2 3 8 1 0 7 5 9
|-
!3
|5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11
|-
!4
|7 13 10 1 0 8 9 15 14 4 6 12 11 2 5 3
|-
!5
|6 12 7 1 5 15 13 8 4 10 9 14 0 3 11 2
|-
!6
|4 11 10 0 7 2 1 13 3 6 8 5 9 12 15 14
|-
!7
|13 11 4 1 3 15 5 9 0 10 14 7 6 8 2 12
|-
!8
|1 15 13 0 5 7 10 4 9 2 3 14 6 11 8 12
|}>
Cryptanalysis of GOST
Compared to DES, GOST has a very simple round function. However, the designers of GOST attempted to offset the simplicity of the round function by specifying the algorithm with 32 rounds and secret S-boxes.Another concern is that the avalanche effect
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
is slower to occur in GOST than in DES. This is because of GOST's lack of an expansion permutation in the round function, as well as its use of a rotation instead of a permutation. Again, this is offset by GOST's increased number of rounds.
There is not much published cryptanalysis of GOST, but a cursory glance says that it seems secure (Schneier, 1996). The large number of rounds and secret S-boxes makes both linear
Linear cryptanalysis
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...
and differential cryptanalysis
Differential cryptanalysis
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 an input can affect the resultant difference at the output...
difficult. Its avalanche effect may be slower to occur, but it can propagate over 32 rounds very effectively.
However, GOST is not fully defined by its standard: It does not specify the S-blocks (replacement tables). On the one hand, this can be additional secure information (in addition to key). On the other hand, the following problems arise:
- different algorithm implementations can use different replacement tables, and thus, can be incompatible to each other
- possibility of deliberate weak replacement table usage
- possibility (standard does not forbid it) to use replacement tables in which nodes are not commutation, that may lead to extreme security downfall
Despite its apparently strong construction, GOST is vulnerable to generic attacks based on its short (64-bit) block size, and should therefore never be used in contexts where more than 232 blocks could be encrypted with the same key.
GOST has been submitted to ISO standardization in 2010. In 2011 severe flaws have been discovered in GOST cipher and it has been called "a deeply flawed cipher" by Nicolas Courtois
Nicolas Courtois
Nicolas Tadeusz Courtois is a cryptographer, a senior lecturer in computer science at University College London.Courtois was one of the co-authors of both the XSL attack against block ciphers such as the Advanced Encryption Standard and the XL system for solving systems of algebraic equations, used...
. A more detailed cryptanalysis has been published by Courtois
Nicolas Courtois
Nicolas Tadeusz Courtois is a cryptographer, a senior lecturer in computer science at University College London.Courtois was one of the co-authors of both the XSL attack against block ciphers such as the Advanced Encryption Standard and the XL system for solving systems of algebraic equations, used...
and Miształ in June 2011, demonstrating several attacks reducing attack complexity to
.See also
- U.S. Data Encryption Standard (DES)Data Encryption StandardThe Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
- GOST standardsGOSTGOST refers to a set of technical standards maintained by the Euro-Asian Council for Standardization, Metrology and Certification , a regional standards organization operating under the auspices of the Commonwealth of Independent States .All sorts of regulated standards are included, with examples...
Further reading
- Saarinen, Markku-Juhani (1998). A chosen key attack against the secret S-boxes of GOST.
- Schneier, Bruce. Applied Cryptography, 2nd edition, 1996. ISBN 0-471-11709-9.
- Alex Biryukov, David Wagner, Advanced Slide Attacks, EUROCRYPT 2000, LNCS, pp 589-606, 2000.