Contradiction immunity and guess-then-determine attacks on gost

Abstract

GOST is a well-known Russian government block cipher. Until
2010 there was no attack on GOST used in encryption cf. [23]. More recently
quite a few distinct key recovery attacks on full GOST have been found: [8, 10,
21,11,12,13,14,15,17,30]. Most of these attacks start by a so called \Complexity
Reduction" step [8,10], the purpose of which is to reduce the problem of breaking
the full 32-round GOST to a low-data complexity attack on a reduced-round
GOST. These reductions can be viewed as optimisation problems which seek to
maximize the number of values determined about some values inside the cipher
which can be obtained by guessing some other values at given "cost".
In this paper we consider similar optimisation questions of ¯nding a possibly
optimal guess-then-determine attack BUT at the lower level, inside reduced round
versions of GOST. We postulate that there should be a phase transition between
hard and easy "determine" problems, and that one can make this phase transition
occur earlier by combinatorial optimization of the set of bits to "guess". We
introduce a key fundamental notion of Contradiction Immunity of a block
cipher and provide some good upper bounds for the Contradiction Immunity of
GOST. This can be used to to obtain a particulary e±cient software attack on
GOST with a SAT solver. Moreover the designers of new ciphers should be able
to insure that this number is going to be su±ciently high.