Cryptanalysis of GOST in the multiple-key scenario

Rok, strany: 2013, 45 - 63

GOST 28147-89 is a well-known 256-bit block cipher. In 2010 GOST was submitted to ISO, to become an international standard. Then many academic attacks which allow to break full GOST faster than brute force have been found. The fastest known single-key attack on GOST for $2⁶⁴$ of data is $2¹⁷⁹$ of [Courtois, N.: \textit{An improved differential attack on full GOST,} Cryptology ePrint Archive, Report 2012/138, \url{http://eprint.iacr.org/2012/138}] and for $2³²$ of data it is $2¹⁹¹$ of [Courtois, N.: \textit{Algebraic complexity reduction and cryptanalysis of GOST,} Preprint, 2010–13, \url{http://eprint.iacr.org/2011/626}]. Other results are slower but require significantly less memory [Courtois, N.: \textit{Algebraic complexity reduction and cryptanalysis of GOST,} Preprint, 2010–2013, \url{http://eprint.iacr.org/2011/626}], [Dinur, I.—Dunkelman, O.—Shamir, A.: \textit{Improved attacks on full GOST,} in: Fast Software Encryption—FSE '12, 19th Internat. Workshop, Washington, USA, 2012, Lecture Notes in Comput. Sci., Vol. 7549, Springer, Berlin, 2012, pp. 9–28, \url{http://eprint.iacr.org/2011/558/}]. The common stereotype is that these will be ``the best'' attacks on GOST. However, ciphers are not used in practice with single keys, on the contrary. In this paper we intend to show that there exist attacks on GOST which are more versatile and even somewhat more ``practical'' than the best single key attack. We argument that multiple random key attacks not single key attacks, are more practical and more likely to be executed in the real life. They recover keys when other attacks recover none. One can break some (weaker) GOST keys in a population of 256-bit keys generated at random with a TOTAL computational effort as low as $2¹²⁰$, this including the cost to examine also the cases in which the attack does not work. All our attacks are based on special non-trivial properties of data inside the cipher which however are such that keys for which the property does not hold can be rejected efficiently.

ISO 690:

Courtois, N. 2013. Cryptanalysis of GOST in the multiple-key scenario. In Tatra Mountains Mathematical Publications, vol. 57, no.4, pp. 45-63. 1210-3195.

APA:

Courtois, N. (2013). Cryptanalysis of GOST in the multiple-key scenario. Tatra Mountains Mathematical Publications, 57(4), 45-63. 1210-3195.