Cryptanalysis of GOST in the multiple-key scenario

Abstract

GOST 28147-89 is a well-known 256-bit block cipher. In 2010 GOST was submitted to ISO, to become
an international standard. Then many academic attacks which allow to break full GOST faster than
brute force have been found. The fastest known single-key attack on GOST for 264 of data is 2179 of [10]
and for 232 of data it is 2191 of [6]. Other results are slower but require signicantly less memory [14, 6].
The common stereotype is that these will be \the best" attacks on GOST. However ciphers are not used
in practice with single keys, on the contrary. In this paper we intend to show that there exist attacks on
GOST which are more versatile and more \practical" than the best single key attack. We argument that
multiple random key attacks not single key attacks, are more practical and more likely to be executed in
the real life. They recover keys when other attacks recover none. One can break some (weaker) GOST
keys in a population of 256-bit keys generated at random with a TOTAL computational eort as low as
2120, this including the cost to examine also the cases in which the attack does not work. All our attacks
are based on special non-trivial properties of data inside the cipher which however are such that keys for
which the property does not hold can be rejected eciently.