Cryptology ePrint Archive: Report 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.
Category / Keywords: Block ciphers, GOST, differential cryptanalysis, sets of differentials, truncated differentials, guess-then-determine, Gaussian distribution, distinguisher attacks
Original Publication (with major differences): Springer LNCS 9001, to appear in March 2016
Date: received 14 Mar 2012, last revised 17 Dec 2015
Contact author: n courtois at cs ucl ac uk
Available format(s): PDF | BibTeX Citation
Note: Updated extended version, 17 December 2015.
Version: 20151217:235719 (All versions of this report)
Short URL: ia.cr/2012/138
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]