On Sep 10, 2013, at 3:56 PM, Bill Stewart <bill.stew...@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.  

The cryptography mailing list

Reply via email to