Is GOST broken?

There's an interesting paper on the IACR's eprint preprint server about a new attack against the Russian symmetric cipher GOST. This is "Security Evaluation of GOST 28147-89 In View Of International Standardization." The paper seems quite proud of the attack it describes. Here's what it says:

Clearly GOST is deeply flawed, in more than one way, and GOST does not provide the security level required by ISO. A plethora of other attacks following our general idea and paradigm for symmetric cryptanalysis, called "Algebraic Complexity Reduction" is given in [12]. With this framework which we amply describe here and illustrate with one attack, we ambition to considerably enlarge the spectrum of self-similarity attacks on block ciphers.

We must also report some facts, known to us, and the reader will excuse us for not being able to give more details now, but this is very important for the sake of the still ongoing process at the time of writing of ISO standardisation. There is much more than just a "certificational" attack on GOST faster than brute force [28]. In fact to standardize GOST now would be really dangerous and irresponsible. This is because some of our attacks are feasible in practice. Some GOST keys can indeed be decrypted in practice, which are either weak keys, or for particular natural versions of GOST. See [12] and our forthcoming publications on the same topic, for a detailed discussion of cases in which this will be possible. It appears that also that it is for the first time in history that a major standardized block cipher intended to provide a military-grade level of security and intended to protect also classfied and secret documents, for the government, large banks and other organisations, is broken by a mathematical attack.

But is this really true?

This paper seems to describe an attack against GOST that knocks 8 bits off a 256 bit key. That essentially reduces the time required to crack a key from forever to forever divided by 256, which is still forever. And it requires 264 plain-cipher pairs to do this. That's 267 bytes of data, which is just about half of the world's total storage capacity right now.

So even if I relied on GOST to protect my sensitive diplomatic and military secrets, I wouldn't be too worried by this new attack. It doesn't look like it's even be close to being feasible. 

Leave a Reply

Your email address will not be published. Required fields are marked *