Is the GOST block cipher broken? Is the GOST cipher broken or known to be weak and insecure? Please try to simplify your answer since I am a programmer and not a cryptographer and please consider this web page and tell me if the claims made there are true.
There are two ways a cipher can be broken: theoretically and practically. If the paper is correct then:


  Our fastest attack achieves a nearly feasible $T=2^{101}$ (cf. Section 28.6 and [28]). (emphasis mine)


If we verify this claim then we get:


  If we have a diverse population of at least $2^{79}$ diﬀerent 256-bit GOST keys generated at random, with access to $2^{32}$ CP per key, one can recover one of these 256-bit keys in total overall time of about $2^{101}$ GOST encryptions.


Now theoretically a cipher is broken if there is an attack that is (significantly) faster than brute force. Simply said, $2^{101}$ is a darn amount better than $2^{255}$ required for brute force. So if this claim is correct then the theoretical security of GOST is much lower than it is supposed to be. Hence it could be called broken.

Of course, nobody is going to invest that amount of memory or processing power to even prove this point. SHA-1 has a much lower effective security margin and it took a very long time before a collision could be found.



Given the structure of the paper I would say that it's likely that the claims are correct. That doesn't mean that anybody can now attack GOST. It does show that too many kinds of attack are possible. These kind of attacks will only get stronger. This is a clear indication that it would be wise to upgrade. The block size of 64 bit is also a good reason to upgrade, 64 bit is considered on the low side for many applications of block ciphers.

That all said, these specific cryptographic attacks can not be used to attack any well designed / implemented protocol that makes use of GOST. 101 bit security is generally thought to be out of reach, i.e. the "nearly feasible" in the text.