Hacker News Reader

Comment by Perseids | Hacker News Reader

Whatever justifications the NSA comes up with, the crux with Dual_EC_DRBG remains: Either they are as malicious as is now publicly believed and those points were indeed generated with an included backdoor. Or they are stupid enough to endorse an RNG that is slow, not provably secure and may even contain a backdoor.

Extending on the provably secure part: There actually are constructions that allow you to reduce the discrete logarithm problem to the one-way property and to the pseudo randomness property of the RNG. And without such a proof, what is the benefit of a slow elliptic curve RNG anyway?

Regarding the backdoor part: Even for the NSA the potential of a backdoor is a problem, because every division has to trust the person that has actually generated the points. And as the Dual_EC_DRBG was used by the DoD, this person potentially has the keys to some very sensitive parts of the kingdom.

View on HN

"In truth, I can think of no better way to describe our failure to drop support for the Dual_EC_DRBG algorithm as anything other than regrettable."

'malicious', perhaps?

For some reason, this feigned almost-apology seems a lot more dickish than if they were just silent on the matter completely.

It's pretty well-accepted at this point that they intended the algorithm to allow for "key escrow" (a government backdoor) from the very beginning. And instead of just admitting that's what they did, they're trying to come up with a story about how it was all a big mistake and no they didn't backdoor it, they just supported a broken and insecure algorithm.

It's like someone coming up to you, punching you in the face, and then saying "oh, sorry, didn't mean to do that, my hand slipped". The words just add insult to injury.

> Even for the NSA the potential of a backdoor is a problem, because every division has to trust the person that has actually generated the points. And as the Dual_EC_DRBG was used by the DoD, this person potentially has the keys to some very sensitive parts of the kingdom.

While this is generally true, it is possible for a person or organization to remove the backdoor by generating their own point and/or by reducing the number of bits generated from curve points at each RNG step (which NIST had pushed for an insecure number of).

I can't claim to know for sure, but it would be my guess that the implementations used at the Federal Reserve, the DoD and other highly sensitive areas of government that use public algorithms highly vetted to remove known implementation problems and weak parameterizations.

In the case of the NSA: Never attribute to stupidity what can be attributed to malice.

And that is the only compliment they will get from me.

Pardon me if I'm misinterpreting you, but isn't the existence of one-way functions equivalent to P != NP? So far we definitely haven't proved/disproved that one-way functions exist, so any primitive that relies on them is not provably secure.

More generally, I don't think there are any CSPRNGs that are actually provably secure; please correct me if I'm wrong. The proofs all rely in some way on problems that are conjectured to be hard, which depends on P != NP. This isn't necessarily the case, if we could devise an algorithm that depends on a decidable problem harder than NP-complete, but I don't think we have proved if any such problems exist.

Edit: On reflection, I think the parent is saying that there was never a proof published that Dual_EC_DRBG is reducible to a hard problem, and without that we cannot even say whether Dual_EC_DRBG is as secure as other PRNGs that can be shown to be related to hard problems.

To say that something is reducible to a conjectured hard problem is what 'provably secure' means in cryptography. Also, cryptographic hardness is not trivially relatable to P vs. NP, especially for hardness assumptions used to build public-key systems. For example, a poly-time factoring algorithm would not prove P == NP, but it would break RSA.

Good point, thanks. It looks like a few of them, including factorization and the discrete log problem, are conjectured to be NP-intermediate; that is, NP but neither P nor NP complete. However, this class may actually be empty, and is only non-empty if P != NP.

If P = NP, NP-intermediate is necessarily empty, so problems like factorization would be P = NP = NP-complete. You're right, though: the existence of a (classical) polynomial-time factorization algorithm doesn't solve P = NP.

> Edit: On reflection, I think the parent is saying that there was never a proof published that Dual_EC_DRBG is reducible to a hard problem, and without that we cannot even say whether Dual_EC_DRBG is as secure as other PRNGs that can be shown to be related to hard problems.

Yes, that was what I meant to say. There are elliptic curve PRNGs for which it is proven that breaking their security properties allows you to calculate the discrete logarithm on the elliptic curve. IIRC, no such proof is publicly known for Dual_EC_DRBG, even under the assumption that both points P and Q were chosen at random.

If you have specifically crafted the points (you know the logarithm of Q to base P), then breaking Dual_EC_DRBG is trivial. And by "breaking" I mean recovering the internal state of the PRNG out of its output.

Reply on news.ycombinator.com