[Cryptography] People should turn on PFS in TLS (was Re: Fwd: NYTimes.com: N.S.A. Foils Much Internet Encryption)

[John Kelsey]

On Sep 10, 2013, at 3:56 PM, Bill Stewart <bill.stewart at pobox.com> wrote:

>> One point which has been mentioned, but perhaps not emphasised enough - if NSA have a secret backdoor into the main NIST ECC curves, then even if the fact of the backdoor was exposed - the method is pretty well known - without the secret constants no-one _else_ could break ECC.
>> So NSA could advocate the widespread use of ECC while still fulfilling their mission of protecting US gubbmint communications from enemies foreign and domestic. Just not from themselves.


I think this is completely wrong.

First, there aren't any secret constants to those curves, are there?  The complaint Dan Bermstein has about the NIST curves is that they (some of them) were generated using a verifiably random method, but that the seeds looked pretty random.  The idea here, if I understand it correctly, is that if the guys doing the generation knew of some property that made some of the choices of curves weak, they could have tried a huge number of seeds till they happened upon one that led to a weak curve.  If they could afford to try N seeds and do whatever examination of the curve was needed to check it for weakness, then the weak property they were looking for couldn't have had a probability much lower than about 1/N.  

I think the curves were generated in 1999 (that's the date on the document I could find), so we are probably talking about less than 2^{80} operations total.  Unlike the case with the Dual EC generator, where a backdoor could have been installed with no risk that anyone else could discover it, in this case, they would have to generate curves until one fell in some weak curve class that they knew about, and they would have to hope nobody else ever discovered that weak curve class, lest all the federal users of ECC get broken at once.  

The situation you are describing works for dual ec drbg, but not for the NIST curves, as best I understand things.  

--John