D&C GLug - Home Page

[ Date Index ] [ Thread Index ] [ <= Previous by date / thread ] [ Next by date / thread => ]

Re: [LUG] RSA what?

 

On Fri, 20 Sep 2013, Simon Waters wrote:
As the article you link notes the algorithm in question had small biases large enough to raise eyebrows by the first folks to look at it critically on the relationship between a number and it's successor.

That's now how I read that.

I had a look at the original presentation by the Microsoft guys that revealed the possible backdoor:

http://rump2007.cr.yp.to/15-shumow.pdf

Skipping over the details, it comes down to the fact that there exists a relationship between the constants P and Q defined in the Dual_EC_DRBG. The existence of this relationship in itself is a mathematical fact and, within the context of elliptic curves, isn't rocket science. It's also a known hard problem to find this relationship given P and Q.

What the researchers suggest is that the some entity might know the constant e that defines the relationship between P and Q. For 'some entity' read the NSA, which has come up with P and Q without explaining how they were derived. Indeed, if you can choose Q you can do it in a way so that you know e.

They then showed, by choosing various values for P and Q, for which they knew the constant e, how knowing such a constant indeed weakens the randomness of the algorithm quite significantly.

Note that they didn't _prove_ that there was a backdoor and I also don't read any evidence of statistical analysis of the RNG output. (If I understand it correctly, assuming someone knows this constant, it still has about 32 bits of entropy for them. That's nowhere near enough for a secure system, but would take an awful lot of statistics to prove that there is indeed a bias.)

This also makes it a proper backdoor that can be exploited only by those with knowledge of e. It's not just a weakness that anyone can exploit.

Martijn.

--
The Mailing List for the Devon & Cornwall LUG
http://mailman.dclug.org.uk/listinfo/list
FAQ: http://www.dcglug.org.uk/listfaq