Cryptology ePrint Archive: Report 2012/138

An Improved Differential Attack on Full GOST

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 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 is insecure on more than one account. There is a substantial variety of recent attacks on GOST. We have reflection attacks, attacks with double reflection, self-similarity guess then determine attacks which do not use any reflections and advanced differential attacks. The final key recovery step in various attacks is in many cases a software algebraic attack, frequently also or combined with a Meet-In-The-Middle attack and in differential attacks key bits are guessed and confirmed by the differential properties. In this paper we consider some recent differential attacks on GOST and show how to further improve them. We present one new single-key attacks 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: secret-key cryptography / Block ciphers, GOST, differential cryptanalysis, sets of differentials, aggregated differentials, iterative differentials

Date: received 14 Mar 2012, last revised 11 Dec 2012

Contact author: n courtois at cs ucl ac uk

Available format(s): PDF | BibTeX Citation

Note: We can compare it to the most recent result by Shamir et al. with time complexity of 2^192 which is going to be presented at FSE 2012 in Washington DC, on 19 March 2012. Our new attack is several thousands of times faster and the fastest ever found.

Version: 20121211:215646 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]