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.