Low-Complexity Key Recovery Attacks on GOST Block Cipher
Nicolas T. Courtois · Cryptologia · 2013
GOST is a well-known Russian government block cipher. Until 2010, there was no attack on GOST used in encryption, cf. [Citation9]. More recently, quite a few distinct key recovery attacks on full GOST have been found: [Citation1-4, Citation6, Citation7]. Most of these attacks work by so-called “complexity reduction” [Citation1]; they reduce the problem of breaking the full 32-round GOST to an attack with 2,3,4 KP for 8 rounds of GOST. In this article, we develop an alternative last step for these attacks. We present a new meet-in-the-middle attack for eight rounds, which is faster than any previous attack. Then we present a guess-then-determine attack with software using an SAT solver, which, for the same running time, requires much less memory. As a result we are able to improve by a factor of up to 226 various attacks from [Citation1, Citation3].