The GOST block cipher (Magma), defined in the standard GOST 28147-89 (RFC 5830), is a Soviet and Russian government standard
symmetric key
Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between t ...
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.
The
GOST hash function is based on this cipher. The new standard also specifies a new 128-bit block cipher called
Kuznyechik
Kuznyechik (russian: Кузнечик, literally "grasshopper") is a symmetric block cipher. It has a block size of 128 bits and key length of 256 bits. It is defined in the National Standard of the Russian Federation GOST R 34.12-2015 and also ...
.
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
The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen nationa ...
, it was declassified and it was released to the public in 1994. GOST 28147 was a Soviet alternative to the
United States
The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
standard algorithm,
DES
Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include:
People
* Des Buckingham, English football manager
* Des Corcoran, (1928–2004), Australian politician
* Des Dillon (disambiguation), sever ...
.
[
] Thus, the two are very similar in structure.
The algorithm
GOST has a 64-bit
block size and a
key length
In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher).
Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
of 256 bits. Its
S-box
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 Shan ...
es can be secret, and they contain about 354 (log
2(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 2
32 encryptions.
GOST is a
Feistel network
In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research w ...
of 32 rounds. Its round function is very simple: add a 32-bit subkey
modulo 2
32, 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
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
.
[
]
For example, the
Central Bank of Russian Federation
The Central Bank of the Russian Federation (CBR; ), doing business as the Bank of Russia (russian: Банк России}), is the central bank of the Russian Federation. The bank was established on July 13, 1990. The predecessor of the bank can ...
used the following S-boxes:
However, the most recent revision of the standard, GOST R 34.12-2015, adds the missing S-box specification and defines it as follows.
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 2
192 when 2
64 data is available.
Since 2007, several attacks have been developed against reduced-round GOST implementations and/or
weak key In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, if one generates a rando ...
s.
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
Nicolas Tadeusz Courtois (born 14 November 1971) is a cryptographer and 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 Encry ...
. Initial attacks were able to reduce time complexity from 2
256 to 2
228 at the cost of huge memory requirements, and soon they were improved up to 2
178 time complexity (at the cost of 2
70 memory and 2
64 data).
In December 2012, Courtois, Gawinecki, and Song improved attacks on GOST by computing only 2
101 GOST rounds. Isobe had already published a single key attack on the full GOST cipher, which Dinur, Dunkelman, and Shamir improved upon, reaching 2
224 time complexity for 2
32 data and 2
36 memory, and 2
192 time complexity for 2
64 data.
Since the attacks reduce the expected strength from 2
256 (key length) to around 2
178, the cipher can be considered broken. However, 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 2
n/2 blocks, due to the
birthday paradox
In probability theory, the birthday problem asks for the probability that, in a set of randomly chosen people, at least two will share a birthday. The birthday paradox is that, counterintuitively, the probability of a shared birthday exceeds 5 ...
,
[
] and none of the aforementioned attacks require less than 2
32 data.
See also
*
GOST standards
GOST (russian: ГОСТ) refers to a set of international technical standards maintained by the ''Euro-Asian Council for Standardization, Metrology and Certification (EASC)'', a regional standards organization operating under the auspices of th ...
References
Further reading
*
*
*
*
External links
Description, texts of the standard, online GOST encrypt and decrypt toolsAn open source implementation of PKCS#11 software device with Russian GOST cryptography standards capabilities*https://github.com/gost-engine/engine — open-source implementation of Russian GOST cryptography for OpenSSL.
{{Cryptography navbox , block
Broken block ciphers
Feistel ciphers
GOST standards