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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision.Springer LNCS 9001, to appear in March 2016
Keywords
Block ciphersGOSTdifferential cryptanalysissets of differentialstruncated differentialsguess-then-determineGaussian distributiondistinguisher attacks
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/138,
      author = {Nicolas T.  Courtois},
      title = {An Improved Differential Attack on Full GOST (extended version)},
      howpublished = {Cryptology ePrint Archive, Paper 2012/138},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/138}},
      url = {https://eprint.iacr.org/2012/138}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.