Paper 2012/138

An Improved Differential Attack on Full GOST (extended version)

Nicolas T. Courtois

Abstract

GOST 28147-89 is a well-known block cipher and the official encryption standard of the Russian Federation. A 256-bit block cipher considered as an alternative for AES-256 and triple DES, having an amazingly low implementation cost and it is becoming increasingly popular. Until 2010 researchers unanimously agreed that: “despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken”, and in 2010 it was submitted to ISO 18033 to become a worldwide industrial encryption standard. In 2011 it was suddenly discovered that GOST can be broken and it is insecure on more than one account. There is a substantial variety of recent innovative attacks on GOST. We have reflection attacks, attacks with double, triple and even quadruple reflections, a large variety of self-similarity and black-box reduction attacks, some of which do not use any reflections whatsoever and few other. The final key recovery step in various attacks is in many cases a software algebraic attack or/and a Meet-In-The-Middle attack. In differential attacks key bits are guessed and confirmed by the differential properties and there have already been quite a few papers about advanced differential attacks on GOST. There is also several even more advanced “combination” attacks which combine the complexity reduction approach based on high-level self-similarity of with various advanced differential properties with 2,3 or 4 points. In this paper we consider some recent differential attacks on GOST and show how to further improve them. We present a single-key attack against full 32-round 256-bit GOST with time complexity of 2^179 which is substantially faster than any previous single key attack on GOST.

Note: Updated extended version, 17 December 2015.