World Library  
Flag as Inappropriate
Email this Article

Gost 28147-89

Article Id: WHEBN0018961320
Reproduction Date:

Title: Gost 28147-89  
Author: World Heritage Encyclopedia
Language: English
Subject: Data Encryption Standard, Index of cryptography articles, GOST, BestCrypt
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Gost 28147-89

GOST 28147-89
240px
Diagram of GOST
General
Designers USSR
First published 1994-05-23 (declassified)
Successors GOST hash function
Certification GOST standard
Cipher detail
Key sizes 256 bits
Block sizes 64 bits
Structure Feistel network
Rounds 32

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.[1] 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.[2]

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.[3]

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 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.[3][4] 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-boxes (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.

Since 2007, several attacks were developed against GOST implementations with reduced number of rounds and/or keys with additional special properties.[5][6]

In 2011 several authors discovered more significant flaws in GOST cipher, being able to attack full 32-round GOST with arbitrary keys for the first time. It has been even called "a deeply flawed cipher" by Nicolas Courtois.[7] First attacks were able to reduce time complexity from 2^{256} to 2^{228} at the cost of huge memory requirements,[8] and soon they were improved up to 2^{178} time complexity (at the cost of 2^{70} memory and 2^{64} data).[9]

As of December 2012 the best known attack on GOST (2^{101}) is on par with the best known attack (2^{100}, based on another weakness noted by Nicolas Courtois) on widely used Advanced Encryption Standard.

GOST has been submitted to ISO standardization in 2010.

See also

References

Further reading

  • Alex Biryukov, David Wagner, Advanced Slide Attacks, EUROCRYPT 2000, LNCS, pp 589–606, 2000.

External links

  • GOST — The Soviet Encryption Algorithm
  • Online GOST encrypt and decrypt tool
  • Online GOST hashing tool
  • SCAN's entry for GOST
  • An open source implementation of PKCS#11 software device with Russian GOST cryptography standards capabilities
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.