Editing GOST (block cipher) (section)

==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.