Paper 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.
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.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Block ciphersGOSTdifferential cryptanalysissets of differentialsaggregated differentialsiterative differentials
- Contact author(s)
- n courtois @ cs ucl ac uk
- History
- 2015-12-17: last of 3 revisions
- 2012-03-22: received
- See all versions
- Short URL
- https://ia.cr/2012/138
- License
-
CC BY