Paper 2011/312

Differential Cryptanalysis of GOST

Nicolas T. Courtois and Michal Misztal

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 thus increasingly popular and used. 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 is insecure on more than one account. There is an amazing variety of recent attacks on GOST. We have reflection attacks, attacks with double reflection, and various attacks which does not use reflections. All these methods follow a certain general framework called "Algebraic Complexity Reduction", a new general "umbrella" paradigm. The final key recovery step is in most cases a software algebraic attack and sometimes a Meet-In-The-Middle attack. In this paper we show that GOST is NOT SECURE even against (advanced forms of) differential cryptanalysis (DC). Previously Russian researchers postulated that GOST will be secure against DC for as few as 7 rounds out of 32 and Japanese researchers were already able to break about 13 rounds. In this paper we show a first advanced differential attack faster than brute force on full 32-round GOST. This paper is just a sketch and a proof of concept. More results of this kind will be published soon.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Block ciphersGOSTdifferential cryptanalysissets of differentials
Contact author(s)
n courtois @ cs ucl ac uk
History
2011-07-02: last of 4 revisions
2011-06-13: received
See all versions
Short URL
https://ia.cr/2011/312
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/312,
      author = {Nicolas T.  Courtois and Michal Misztal},
      title = {Differential Cryptanalysis of GOST},
      howpublished = {Cryptology ePrint Archive, Paper 2011/312},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/312}},
      url = {https://eprint.iacr.org/2011/312}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.