Paper 2011/558

Improved Attacks on Full GOST

Itai Dinur, Orr Dunkelman, and Adi Shamir

Abstract

GOST is a well known block cipher which was developed in the Soviet Union during the 1970's as an alternative to the US-developed DES. In spite of considerable cryptanalytic effort, until very recently there were no published single key attacks against its full 32-round version which were faster than the $2^{256}$ time complexity of exhaustive search. In February 2011, Isobe used in a novel way the previously discovered reflection property in order to develop the first such attack, which requires $2^{32}$ data, $2^{64}$ memory and $2^{224}$ time. Shortly afterwards, Courtois and Misztal used a different technique to attack the full GOST using $2^{64}$ data, $2^{64}$ memory and $2^{226}$ time. In this paper we introduce a new fixed point property and a better way to attack 8-round GOST in order to find improved attacks on full GOST: Given $2^{32}$ data we can reduce the memory complexity from an impractical $2^{64}$ to a practical $2^{36}$ without changing the $2^{224}$ time complexity, and given $2^{64}$ data we can simultaneously reduce the time complexity to $2^{192}$ and the memory complexity to $2^{36}$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Block ciphercryptanalysisGOSTreflection propertyfixed point property2D meet in the middle attack
Contact author(s)
itaid @ weizmann ac il
History
2011-10-11: received
Short URL
https://ia.cr/2011/558
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/558,
      author = {Itai Dinur and Orr Dunkelman and Adi Shamir},
      title = {Improved Attacks on Full GOST},
      howpublished = {Cryptology ePrint Archive, Paper 2011/558},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/558}},
      url = {https://eprint.iacr.org/2011/558}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.