Hacker News Reader

Comment by tptacek | Hacker News Reader

Stop and consider for a second how crazy this page is:

https://kb.juniper.net/InfoCenter/index?page=content&id=KB28...

Dual_EC is a PKRNG. PKRNGs are a kind of crypto random number generator (CSPRNG). All the crypto keys in modern cryptosystems come from CSPRNGS.

PKRNGs are special because they embed a public key in the generator. Anyone who holds the corresponding private key can "decrypt" the output of the RNG and recover the generator's "state"; once they have that, they can fast-forward and rewind through it to find all the other numbers (read: crypto keys) it can generate.

Juniper is here saying that they recognize the problem of Dual_EC --- it's a PKRNG, and the USG may hold its private key.

So instead, they generated their own private keys and embedded them in the CSPRNGs of the VPNs they sold to customers.

WAT?

But see also this thread:

https://news.ycombinator.com/item?id=10764359

View on HN

It depends on how P and Q are generated.

The NIST document specifying Dual EC offers default values for each curve. P is the usual base point for the curve; an arbitrary point Q is provided without justification or details of its generation.

Because the NIST curves have cofactor 1, all points other than the identity generate the same subgroup. This means any two points P and Q are related by some scalar d such that d * P = Q. Knowledge of d is the back door in the generator.

This also implies a simple means for choosing Q given P: pick a random integer d and calculate Q = d * P. Publish P and Q and then write down d someplace safe. This is exactly how NSA is speculated to have chosen the Dual EC parameters.

However, the NIST document also specifies a method for generating alternative points. It boils down to hashing a random seed and mapping the result to a curve point. If you generate the base points P and Q like this, the relationship between them is unknown. The scalar d still exists, but now no one knows what it is. Without that knowledge, there is no back door.

It's not clear from that page how Juniper chose the parameters. Maybe they did choose a random scalar and multiply P, or maybe they followed the standard. The information on that page isn't enough to say one way or the other.

EDIT: Just to be clear, I'm not saying this isn't something to worry about. You should distrust and avoid anything that relies on Dual EC. I'm only saying there is not enough information to say definitively that Juniper put a back door in their own product, intentionally or otherwise.

Certicom did the same thing. The argument given was that these companies have less access to data interception, therefore the impact of a maliciously-generated set of parameters is lower. That's absolutely crazy.

The real danger of including Dual EC in any system is the risk that it adds to code. Now instead of having to include a large, easy-to-detect passive decryption backdoor, an attacker only has to change a few bytes. Sometimes just a pointer value. Once you do that, Dual EC is often ridiculously easy to attack:

http://dualec.org/DualECTLS.pdf

Just out of interest, is there any legitimate use of a PKRNG or is it just a backdoor enabler?

Not totally an expert but the explanation of what a PKRNG is overly simplified. The problem with Dual EC is not that it is a PKRNG, but that some design choice made allowed for allegedly planting a backdoor for agencies with enough computing power.

Basically one of the problem you are trying to solve with a CSPRNG is how you avoid to disclose the generator state with the random numbers. Obviously once the state is known it is easy to replay the sequence.

Since we don't like to reinvent the wheel overtime, a solution is leveraging known properties of hashing and encryption algorithms. The idea behind a PKRNG is to use a fairly simple state evolution function but then to encrypt the output with a known public key. Since a property of public key encryption is that you can't know the message if you don't know the private key, the state is safe for everybody except the owner of the key. If you then truncate the encrypted message and you choose the public key without computing the private key you get a very strong CSPRNG. To be more clear:

- There are procedure to generate a public key without generating the private key (but you should trust the person who generated the numbers).

- The encrypted message is truncated, so even if you still have the private key, you should guess the missing bit of the message to decode the state.

The problem with Dual EC is that the resulting encrypted message is not truncated enough (it is enough to protect against a casual attacker, not an organization with massive computing power like an intelligence agency). Plus doubt were casted on the procedure used to generate the public key, given that you were forced to use the one in the standard and not your own if you want to get certified.

There's no reason to use a public key transform to generate random bits other than to leverage the fact that the tranform is trapdoored with a private key. They are otherwise cost-prohibitive.

If you can point to a "good" PKRNG that sees any use, that would be an interesting way to rebut my argument.

The consensus opinion among cryptographers is converging on "no"; that the only reason to use a PKRNG is if you want key escrow.

And I don't think Dual_EC is even a particularly good RNG either.

This is a perfect example of why have a suspect feature present at all is problematic. Its usually just one configuration or compile time switch away from being used in real situations. The only reasonable response to the Dual_EC backdoor is to just delete the code entirely, keeping it around is asking for situations like this.

Its a lot easier to sneak a build or configuration flag in somewhere than it is to sneak in an entire CSPRNG subsystem.

Anybody who (as I do) finds this kind of thing fascinating should go back and read Young and Yung's work on kleptography from the late 90's: http://www.cryptovirology.com/cryptovfiles/research.html

They were way, way ahead of their time.

> So instead, they generated their own private keys and embedded them in the CSPRNGs of the VPNs they sold to customers.

Isn't it possible to still get this PRNG right by discarding the private part?

Not that mere use of such infamous algorithm isn't crazy anyway, especially since even if they did the right thing they can't prove it.

Depends on how hard it is to break. Even if it takes a while and a lot of money, for something as widespread as their firewalls, it might have been worth the effort to someone. Of course only if it is in the category of "a while and expensive", not in "impossible"?

Surely that would be the response of someone who believes his systems have been compromised and looks to invalidate all the keys an attacker could have gained access to? Or were the previous points part of the standard?

Reply on news.ycombinator.com