Paper 2011/626

Algebraic Complexity Reduction and Cryptanalysis of GOST

Nicolas T. Courtois

Abstract

GOST 28147-89 is a well-known Russian government encryption standard. Its large key size of 256 bits at a particularly low implementation cost make that it is widely implemented and used, in OpenSSL and elsewhere. In 2010 GOST was submitted to ISO to become an international standard. GOST was analysed by Schneier, Biham, Biryukov, Dunkelman, Wagner, various Australian, Japanese, and Russian scientists, and all researchers seemed to agree that it looks quite secure. Though the internal structure of GOST seems quite weak compared to DES, and in particular the diffusion is not quite as good, it is always stipulated that this should be compensated by a large number of 32 rounds and by the additional non-linearity and diffusion provided by modular additions. At Crypto 2008 the hash function based on this cipher was broken. Yet as far as traditional encryption applications with keys generated at random are concerned, until 2011 no cryptographically significant attack on GOST was found. In this paper we present several new attacks on full 32-rounds GOST. Our methodology is derived from the idea of conditional algebraic attacks on block ciphers which can be defined as attacks in which the problem of key recovery is written as a problem of solving a large system of algebraic equations, and where the attacker makes some "clever" assumptions on the cipher which lead to an important simplification in the algebraic description of the problem, which makes it solvable in practice if the assumptions hold. Our methods work by black box reduction and allow to literally break the cipher apart into smaller pieces and reduce breaking GOST to a low data complexity software/algebraic/MITM attack on 8 or less rounds. Overall we obtain some 60 distinct attacks faster than brute force on the full 32-round GOST and we provide five nearly practical attacks on two major 128-bit variants of GOST (cf. Table 6). Our single key attacks are summarized in Table 3 p.53 and Table 7 p.153 and attacks with multiple keys in Table 4 page 128.

Note: Recent updates: Our latest attacks combine all of [higher-order] trun- cated differentials, complexity reduction, [approximate] fixed points, reflections, MITM and software/algebraic attacks. Single key attacks are summarized in Table 3 and Table 7 and the fastest of these is a differential attack in 2^179 by Courtois. In the multiple random key scenario, the cost of recovering one full 256-bit GOST key decreases in a spectacular way down to a nearly feasible T=2^101. This at the expense of further growing data requirements cf. Table 4 page 121. This is the "master paper" which describes a general methodology for block cipher cryptanalysis through a reduction to a low-data complexity key recovery attack and some 50 different attacks on GOST obtained with this methodology. It is here for reference, to establish priority, and to show the big picture how all these attacks are related to each other.