Advanced Truncated Differential Attacks Against GOST Block Cipher and Its Variants

GOST block cipher, defined in the GOST 28147-89 standard, is a well-known 256-bit symmetric cipher that operates on 64-bit blocks. The 256-bit level security can be even more increased by keeping the specifications of the S-boxes secret. GOST is implemented in many standard libraries such as OpenSSL and it has extremely low implementation cost and as a result of this it could be considered as a plausible alternative for AES-256 and 3-DES. Furthermore, nothing seemed to threaten its high 256-bit security [CHES 2010] and in 2010 it was submitted to ISO 18033-3 to become a worldwide industrial standard. During the period of submission many new attacks of different types were presented by the cryptographic communities against full 32-rounds of GOST. We have algebraic complexity reduction attacks, advanced differential attacks, attacks using reflection property, and many others. However, all of these attacks were against the version of GOST which uses the standard set of S-boxes. In this paper, we study the security of many variants of GOST against advanced forms of differential attacks which are based on truncated differentials techniques. In particular we present an attack against full GOST for the variant of GOST which is supposed to be the strongest one and uses the set of S-boxes proposed in ISO 18033-3. Our attack is of Depth-First key search style constructed by solving several underlying optimization problems and has time complexity 2245. 4 and 264 memory and data complexity. It is very interesting to note that this attack is unoptimized with respect to several aspects and can be immediately improved by discovering more efficient ad-hoc heuristics which could eventually lead to the discovery of better truncated differential properties.