0
$\begingroup$

David Wong in his book Real-World Cryptography writes:

In 2013, following revelations from Edward Snowden, it was discovered that NSA had purposefully and successfully pushed for the inclusion of backdoor algorithms in standards (see “Dual EC: A Standardized Back Door” by Bernstein et al.), which included a hidden switch that allowed NSA, and only the NSA, to predict your secrets. These backdoors can be thought of as magic passwords that allow the government (and only it, supposedly) to subvert your encryption. <...> Recently, in $2019$, it was found that the Russian standard GOST has been a victim of the same treatment.

The GOST reference is probably with regards to Streebog and Kuznyechik.

Although the author refers to "magic passwords" it is understood that this is oversimplification, so it might not be taken literally.

I would like to know this: in both of the cases (Dual EC and Streebog/Kuznyechik s-box) what is the information that allows the exploitation? Is it

  • a secret key, similar to a private key in asymmetric cryptography algorithms that cannot be derived from public data; or
  • some secret way (algorithm) of exploitation that is unknown to public
  • both
  • something else

In other words, would everyone be able to exploit those backdoors, if some kind of a secret key was known to the public, or is there some science/algorithm knowledge missing too?

$\endgroup$
3
  • $\begingroup$ Dual EC let the NSA learn random number generator's next state from 32 byte that can be seen from nonces of TLS.. $\endgroup$
    – kelalaka
    Commented Mar 9, 2022 at 23:53
  • $\begingroup$ @kelalaka so that's the question, what NSA has that general public do not that allows them to learn that? $\endgroup$ Commented Mar 10, 2022 at 0:42
  • $\begingroup$ @AndrewSavinykh The NSA is no longer decades ahead of the public when it comes to cryptographic knowledge. Thankfully, it's quite possible to tell when a design could not have been backdoored with a high probability. Even if the NSA could easily design a backdoored cipher, the public would realize that its very design makes backdooring possible in theory and would reject it. $\endgroup$
    – forest
    Commented Mar 18, 2022 at 20:21

1 Answer 1

2
$\begingroup$

in both of the cases (Dual EC and Streebog/Kuznyechik s-box) what is the information that allows the expotaition?

In the case if Dual EC, it is essentially a private key. Dual EC has two internal elliptic curve points (P and Q); if someone knows the relation between the two (that is, know the integer $n$ that satisifies ($nP = Q$), then they can predict future outputs from the current one. If they don't (and can't otherwise solve the Computational Diffie Hellman problem), then they can't.

This relation is known as the discrete log; it is essentially the private key in most elliptic-curve based cryptosystems.

As for Streebog and Kuznyechik, that's not nearly as clear. We don't know that there is a backdoor (it is widely suspected, because of unexplained regularities within the sbox - one possible reason for those regularities would be so a backdoor would work - however, that's not the only possible reason).

As we don't know how the backdoor (if any) was inserted, it's not as clear how the backdoor would be used. One possibilities is the insertion of a linear characteristic (or something similar); if this guess is correct, then the exploit would involve knowing some amount of plaintext and ciphertext, and then using that characteristic to be able to test parts of the key.

$\endgroup$
2
  • $\begingroup$ Thank you, I understand the answer. A follow up question, is it common in modern cryptography to accept an algorythm as a standard, when its security depends on no one knowing a "private key" which is "hardcoded" into the standard? Because when explained like that, it seems like an obvious thing to look out for when reviewing a proposed standard $\endgroup$ Commented Mar 12, 2022 at 20:24
  • $\begingroup$ @AndrewSavinykh: one would think that would not be accepted, however there is at least one current proposed standard where that has it: Spake+2 datatracker.ietf.org/doc/draft-bar-cfrg-spake2plus (which is a proposed PAKE); it does have embedded $N$ and $M$ values in the standard, and if you know their discrete logs, you can test a large number of passwords from a single key exchange. I don't know if the community would find that acceptable... $\endgroup$
    – poncho
    Commented Mar 16, 2022 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.