### 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.

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.

#### Full Text:

Subscribers OnlyDOI: https://doi.org/10.2478/tatra.v53i0.194