GOST is a well-known Russian government block cipher. Until2010 there was no attack on GOST used in encryption cf. [23]. More recentlyquite 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 \ComplexityReduction" step [8,10], the purpose of which is to reduce the problem of breakingthe full 32-round GOST to a low-data complexity attack on a reduced-roundGOST. These reductions can be viewed as optimisation problems which seek tomaximize the number of values determined about some values inside the cipherwhich can be obtained by guessing some other values at given "cost".In this paper we consider similar optimisation questions of ¯nding a possiblyoptimal guess-then-determine attack BUT at the lower level, inside reduced roundversions of GOST. We postulate that there should be a phase transition betweenhard and easy "determine" problems, and that one can make this phase transitionoccur earlier by combinatorial optimization of the set of bits to "guess". Weintroduce a key fundamental notion of Contradiction Immunity of a blockcipher and provide some good upper bounds for the Contradiction Immunity ofGOST. This can be used to to obtain a particulary e±cient software attack onGOST with a SAT solver. Moreover the designers of new ciphers should be ableto insure that this number is going to be su±ciently high.
@article{194,
title = {Contradiction immunity and guess-then-determine attacks on gost},
journal = {Tatra Mountains Mathematical Publications},
volume = {51},
year = {2012},
doi = {10.2478/tatra.v53i0.194},
language = {EN},
url = {http://dml.mathdoc.fr/item/194}
}
Courtois, Nicolas T.; Gawinecki, Jerzy A.; Song, Guangyan. Contradiction immunity and guess-then-determine attacks on gost. Tatra Mountains Mathematical Publications, Tome 51 (2012) . doi : 10.2478/tatra.v53i0.194. http://gdmltest.u-ga.fr/item/194/