Editing GOST (block cipher)

{{short description|Soviet/Russian national standard block cipher}}
{{Infobox encryption method
|name           = GOST 28147-89 (Magma)
|image          = [[File:GOSTDiagram.png|240px|center]]
|caption        = Diagram of GOST
|designers      = [[USSR]], [[KGB]], 8th Department
|publish date   = 1994-05-23 (declassified)
|series         = 
|derived from   = 
|derived to     = [[GOST (hash function)|GOST hash function]], [[Kuznyechik]]
|related to     = 
|certification  = [[GOST|GOST standard]]
|key size       = 256 bits
|security claim = 
|block size     = 64 bits
|structure      = [[Feistel network]]
|rounds         = 32
|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]].<ref>
{{cite journal
 |last=Courtois
 |first=Nicolas T.
 |title=Security Evaluation of GOST 28147-89 In View Of International Standardisation
 |url=http://eprint.iacr.org/2011/211
 |journal=Cryptology ePrint Archive
 |publisher=[[International Association for Cryptologic Research|IACR]]
 |date=9 May 2011
 |quote=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}}
</ref>
}}

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.<ref name="std2015"/> The [[GOST (hash function)|GOST hash function]] is based on this cipher. The new standard also specifies a new 128-bit block cipher called [[Kuznyechik]]. 

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, [[Data Encryption Standard|DES]].<ref name=fleischmann2009>
{{cite journal
 |last=Fleischmann
 |first=Ewan
 |author2=Gorski, Michael |author3=Hühne, Jan-Hendrik |author4= Lucks, Stefan
 |title=Key Recovery Attack on Full GOST Block Cipher with Zero Time and Memory
 |journal=Published as ISO/IEC JTC
 |year=2009
 |volume=1}}
</ref> Thus, the two are very similar in structure.

==The algorithm==

GOST has a 64-bit [[block size (cryptography)|block size]] and a [[key length]] of 256 bits. Its [[S-box]]es can be secret, and they contain about 354 (log<sub>2</sub>(16!<sup>8</sup>)) 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<sup>32</sup> encryptions.<ref>{{
cite journal
 |last=Saarinen
 |first=Markku-Juhani
 |title=A chosen key attack against the secret S-boxes of GOST
 |year=1998
 |url=http://citeseer.ist.psu.edu/rd/96002585%2C277448%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/compress/0/papers/cs/13215/http:zSzzSzwww.jyu.fizSz~mjoszSzgost_cka.ps.gz/saarinen98chosen.ps
 |quote=We show that a simple "black box" chosen-key attack against GOST can recover secret S-boxes with approximately 2^32 encryptions}}
</ref>

GOST is a [[Feistel network]] of 32 rounds. Its round function is very simple: add a 32-bit subkey [[modular arithmetic|modulo]] 2<sup>32</sup>, 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]].<ref name=schneier1996>
{{cite book
 |last=Schneier
 |first=Bruce
 |title=Applied cryptography : protocols, algorithms, and source code in C
 |url=https://archive.org/details/Applied_Cryptography_2nd_ed._B._Schneier
 |year=1996
 |publisher=Wiley
 |location=New York [u.a.]
 |isbn=978-0-471-11709-4
 |edition=2. ed., [Nachdr.]}}</ref>

For example, the [[Central Bank of Russia|Central Bank of Russian Federation]] used the following S-boxes: <!--http://www.intuit.ru/department/security/networksec/3/4.html-->

{|class="wikitable"
 !#
 !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.<ref name="std2015">{{Cite web |url=http://tc26.ru/standard/gost/GOST_R_3412-2015.pdf |title=GOST R 34.12-2015 (Russian only)  |access-date=2015-08-28 |archive-url=https://web.archive.org/web/20150924113434/http://tc26.ru/standard/gost/GOST_R_3412-2015.pdf |archive-date=2015-09-24 |url-status=dead }}</ref>

{| class="wikitable"
 !#
 !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 2<sup>192</sup> when 2<sup>64</sup> data is available.

Since 2007, several attacks have been developed against reduced-round GOST implementations and/or [[weak key]]s.<ref>
{{cite news
 |url=https://www.iacr.org/archive/fse2007/45930152/45930152.pdf
 |title=Improved Slide Attacks
 |year=2007
 |author1=Eli Biham |author2=Orr Dunkelman |author3=Nathan Keller }}
</ref><ref>
{{cite news
 |url=http://dl.acm.org/citation.cfm?id=1484903.1484932
 |title=Reflection Cryptanalysis of Some Ciphers
 |year=2008
 |author=Orhun Kara}}</ref>

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]].<ref>
{{cite journal
 |last=Courtois
 |first=Nicolas T.
 |title=Security Evaluation of GOST 28147-89 In View Of International Standardisation
 |url=http://eprint.iacr.org/2011/211
 |journal=Cryptology ePrint Archive
 |publisher=[[International Association for Cryptologic Research|IACR]]
 |date=9 May 2011
 |quote=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}}
</ref> Initial attacks were able to reduce time complexity from 2<sup>256</sup> to 2<sup>228</sup> at the cost of huge memory requirements,<ref>
{{cite news
 |url=http://eprint.iacr.org/2011/312
 |title=Differential Cryptanalysis of GOST
 |year=2011
 |publisher=[[International Association for Cryptologic Research|IACR]]
 |author1=Nicolas T. Courtois |author2=Michał Miształ }}
</ref> and soon they were improved up to 2<sup>178</sup> time complexity (at the cost of 2<sup>70</sup> memory and 2<sup>64</sup> data).<ref>
{{cite news
 |url=http://eprint.iacr.org/2012/138.pdf
 |title=An Improved Differential Attack on Full GOST
 |year=2012
 |publisher=[[International Association for Cryptologic Research|IACR]]
 |author=Nicolas T. Courtois}}</ref><ref>{{cite web | last=Courtois | first=Nicolas T. | title=Algebraic Complexity Reduction and Cryptanalysis of GOST | url=https://eprint.iacr.org/2011/626.pdf | work=Cryptology ePrint Archive | publisher=[[International Association for Cryptologic Research|IACR]] | date=Jun 13, 2011}}
</ref>

In December 2012, Courtois, Gawinecki, and Song improved attacks on GOST by computing only 2<sup>101</sup> GOST rounds.<ref>{{cite web | url=http://www.sav.sk/journals/uploads/0114113604CuGaSo.pdf | title=CONTRADICTION IMMUNITY AND GUESS-THEN-DETERMINE ATTACKS ON GOST | publisher=Versita | date=2012 | access-date=2014-08-25 |author1=Nicolas T. Courtois |author2=Jerzy A. Gawinecki |author3=Guangyan Song }}</ref> Isobe had already published a single key attack on the full GOST cipher,<ref>{{cite book |last1=Isobe |first1=Takanori |series=Lecture Notes in Computer Science |title=Fast Software Encryption |date=2011 |chapter=A Single-Key Attack on the Full GOST Block Cipher |volume=6733 |issue=Fast Software Encryption |pages=290–305 |doi=10.1007/978-3-642-21702-9_17|isbn=978-3-642-21701-2 }}</ref> which Dinur, Dunkelman, and Shamir improved upon, reaching 2<sup>224</sup> time complexity for 2<sup>32</sup> data and 2<sup>36</sup> memory, and 2<sup>192</sup> time complexity for 2<sup>64</sup> data.<ref>{{cite book |last1=Dinur |first1=Itai |last2=Dunkelman |first2=Orr |last3=Shamir |first3=Adi |title=Fast Software Encryption |chapter=Improved Attacks on Full GOST |series=Lecture Notes in Computer Science |date=2012 |volume=7549 |issue=Fast Software Encryption |pages=9–28 |doi=10.1007/978-3-642-34047-5_2 |isbn=978-3-642-34046-8 |doi-access=free }}
</ref>

Since the attacks reduce the expected strength from 2<sup>256</sup> (key length) to around 2<sup>178</sup>, the cipher can be considered broken. However, this attack is not feasible in practice, as the number of tests to be performed 2<sup>178</sup> 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 2<sup>n/2</sup> blocks, due to the [[birthday paradox]],<ref>
{{cite news
 |url=http://www.din.de/blob/78392/d77aae03d0d7cc16978912d4290b877e/sc27-sd12-data.pdf
 |title=Draft of ISO/IEC JTC 1/SC 27 Standing Document No. 12 (SD12) on the Assessment of Cryptographic Techniques and Key Lengths, 4th edition 
 |year=2016}}
</ref> and none of the aforementioned attacks require less than 2<sup>32</sup> data.

==GOST 2-128==
	
GOST 2-128 was released in 2016.<ref>{{cite web |url=https://github.com/bobman78/GOST2-128|website=Github |title=GOST2-128 in C language }}</ref> It has exactly the same design but has twice as many S-tables and uses 64-bit integers instead of 32-bit integers. It no longer works on 64-bit blocks but on 128-bit blocks like AES.
	
The two S-tables are those of the Central Bank of Russian Federation and that of the GOST R 34.12-2015 standard.
		
GOST had 256-bit keys that were reused as subkeys. In GOST 2-128, subkeys are generated by a one-way hash function, representing 4096 bits. Thus, no weak keys exist and attacks against GOST do not work in GOST 2-128.

==See also==
*[[GOST|GOST standards]]

==References==
{{reflist|30em}}

==Further reading==
* {{cite web |url=http://gostcrypto.com/index.html |title=WebCrypto GOST Library |publisher=Rudolf Nickolaev, WebCrypto GOST team }}
* {{cite web |date=March 2010 |url=http://tools.ietf.org/html/rfc5830 |title=RFC 5830: GOST 28147-89 encryption, decryption and MAC algorithms |publisher=IETF |last1=Dolmatov |first1=Vasily }}
* {{cite web |date=January 2006 |url=http://tools.ietf.org/html/rfc4357 |title=RFC 4357: Additional Cryptographic Algorithms for Use with GOST |publisher=IETF |last1=Popov |first1=Vladimir |last2=Leontiev |first2=Serguei |last3=Kurepkin |first3=Igor }}
* {{cite conference
    |author1=Alex Biryukov  |author2=David Wagner
     |name-list-style=amp | title = Advanced Slide Attacks
    | conference = Advances in Cryptology, Proceedings of [[EUROCRYPT]] 2000
    | pages = 589–606
    | doi = 10.1007/3-540-45539-6_41
    | publisher = Springer-Verlag
    | date = May 2000
    | location = [[Bruges]]
    | url = https://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf
    | access-date = 2007-09-03 | doi-access = free
    }}

==External links==
* [https://web.archive.org/web/20120226123825/http://gostshifr.narod.ru/ Description, texts of the standard, online GOST encrypt and decrypt tools]
* [http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#GOST SCAN's entry for GOST]
* [http://sourceforge.net/p/atoken/ An 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}}

[[Category:Broken block ciphers]]
[[Category:Feistel ciphers]]
[[Category:GOST standards]]