Low-Complexity Key Recovery Attacks on GOST Block Cipher
GOST is a well-known Russian government block cipher. Until 2010, there was no attack on GOST used in encryption, cf. [9]. More recently, quite a few distinct key recovery attacks on full GOST have been found: [1-4, 6, 7]. Most of these attacks work by so-called complexity reduction [1]; 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 [1, 3].
block ciphers sat solvers black-box reductions key scheduling low-data complexity attacks meet in the middle russian gost cipher self-similarity