Join Log in
Score:0
avatar Crypto

What is required to use a cryptographic algorithm backdoor?

jp flag
Andrew Savinykh

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?

99
0 + 0
nsa
kelalaka avatar
in flag
kelalaka
Dual EC let the NSA learn random number generator's next state from 32 byte that can be seen from nonces of TLS..
0
Reply
jp flag
Andrew Savinykh
@kelalaka so that's the question, what NSA has that general public do not that allows them to learn that?
0
Reply
forest avatar
vn flag
forest
@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.
0
Reply
Score:2
poncho avatar Crypto
my flag
poncho

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.

0 + 0
jp flag
Andrew Savinykh
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
0
Reply
poncho avatar
my flag
poncho
@AndrewSavinykh: one would think that would not be accepted, however there is at least one current proposed standard where that has it: Spake+2 https://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...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.