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.
$\begingroup$
$\endgroup$
4
2 Answers
$\begingroup$
$\endgroup$
3
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}$ different 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.
answered Aug 2, 2015 at 11:34
-
$\begingroup$ This looks like a related-key attack where it's already (quite) infeasible to store all the required related keys, let alone getting the $2^{79+32=111}$ chosen plaintexts... $\endgroup$– SEJPMAug 2, 2015 at 11:38
-
$\begingroup$ Yep, my idea exactly. This is why I mentioned the "amount of memory" even before the "amount of processing"... Still, it seems this cipher loses even more security than DES for specific attacks. It's that they start off at 256 bit that saves the cipher against practical attacks. $\endgroup$– Maarten Bodewes ♦Aug 2, 2015 at 11:40
-
$\begingroup$ I agree particularly with the block size assessment. Sweet32 alone is reason enough to discontinue the use of 64-bit block ciphers. $\endgroup$ Jun 5, 2019 at 12:20
$\begingroup$
$\endgroup$
3
That a cipher is supported by the NSA doesn't mean that (publicly) it is developed by the NSA. The NSA can insert a backdoor requirements into the endevors of third parties, then promote this as a "secure" cypher.
AES was indeed not "developed" by the NSA, but it was promoted by the NSA. And still is. This is particularly important as this is the cypher used for cryptocurrencies and most "encrypted" info on webpages and messaging.
Furthermore the NSA does have a history of inserting backdoors. Even is less cryptographically/mathematically secure, all attacks on GOST are practically unfeasible without quantum computing, so in practice it is as secure as AES.
And it has a greater advantage: It was never intended for public use, so it woudn't be backdoored.
-
$\begingroup$ Well, When NSA says it is secure we believe immediately. I would rather say weakness to cipher, and that is going to be discovered as soon as published. If you add the attacks with their methods and success rate it will be a nice answer. $\endgroup$– kelalakaNov 16, 2018 at 20:24
-
4$\begingroup$ "[GOST] was never intended for public use, so it woudn't be backdoored"; actually, GOST was intended for use within the USSR; it has been speculated that it may have been backdoored (so that some parts of the USSR government could track what other parts of the USSR were doing...) $\endgroup$– ponchoNov 16, 2018 at 22:05
-
$\begingroup$ That isn't really very likely since as you yourself say it was all secret government issues, and there wasn't an internet back then; so, even with the cipher, the "Other parts of the USSR government" woudn't have access to the transmission channels by default, and thus not incentivized to use such "Backdoors". $\endgroup$– SilencioJan 20, 2019 at 5:40
do you know any … cipher … not supported by nsa?– Do you know anyone having access to governmental agency secrets? I’m pretty sure no one here knows (or is willing to admit he/she knows) anything about the actual cryptographic capabilities of agencies like the NSA. (2) 'any recommended cipher or public key algorithm by them they know how to crack it' – the NSA doesn’t recommend ciphers. NIST is responsible for such standardisation. Besides, most current ciphers recommended by NIST haven’t been developed in the USA. Eg: AES (Rijndael) was created in Belgium by civilian cryptographers. $\endgroup$