[Ach] choosing safe curves for elliptic-curve cryptography

[ianG]

On 12/05/2014 15:53 pm, Joe St Sauver wrote:
> Hi,
> 
> Aaron commented:
> 
> #Reference to their project has been in our Paper since almost from the
> #beginning (see theory sections - ECC).
> #Discussion here on this list hasn't shifted to that topic for a whole
> #though.
> 
> I actually did a talk on "Cryptographic Best Practices in the Post-Snowden
> Era" just last week at the Educause Security Professionals 2014 meeting, 
> see http://pages.uoregon.edu/joe/crypto-bcp/crypto-bcp.pdf
> 
> After thinking about ECC for a bit, here are my observations/concerns:
> 
> -- Suite B crypto from the NSA uses elliptic curve, and specifies curve
>    P-256 and curve P-384 for SECRET and TOP SECRET respectively. See
>    https://www.cnss.gov/CNSS/issuances/Policies.cfm (CNSSP No 15,
>    Use of Public Standards for the Secure Sharing of Information Among
>    NSS," Released 10/01/2012)
> 
> -- Yet, http://safecurves.cr.yp.to/ unambiguously flags those curves as 
>    NOT safe; see "Security Dangers of the NIST Curves" at 
>    http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf
>    for more. I'm not sure how to resolve this point with the preceding
>    point.


There is a clear contradiction here.  There are two possible theories
I've come across.  One is that the NSA simply didn't know as much ECC at
the time, and the other is that the NSA was using the standards
organisations (and its own govt. secrecy functions) to push curves that
they knew they had an asymmetric advantage in.

Currently, I can't pick between the two.

The asymmetric advantage is rapidly narrowing as China can now build big
crunchers as well as the USA (it's just chips, after all) and their
mathematicians are pretty good as well (consider Shandong/MD5/SHA1), so
maybe this is an argument that has passed its "sell-by" date.

Another issue is that Suite A is unpublished -- so what does it do?  So
far, the hint I've heard is that it doesn't use PK or EC at all...  If
the case, then that's a *big hint*.  But no real confirmation of that
other than rumours.

And then, all the Snowden revelations certainly indicate that the NSA
would sacrifice Suite B if it thought it could get away with it.

Which way to go?  Nobody really knows at this point.



> -- If you want to do ECC for publicly trusted certs, you need them 
>    issued from an appropriate root. Currently Mozilla only appears to 
>    know about four (4) ECC roots, see
>    http://www.mozilla.org/en-US/about/governance/policies/security-group/certs/included/
> 
> -- Whatever curve you want to use also needs to be supported by the
>    crypto library you're using on your server, and by your browser; 
>    that may further constrain your options
> 
> -- Not surprisingly, ECC deployment to date appears to have been 
>    quite limited
> 
> -- All of the above said, some pretty smart folks are moving to 
>    ECC with alternative cuves, including the folks at Silent Cicle, 
>    and Google (as I discuss on slide 76 of my talk)


Right.


> Hard to know what to say, given the preceding. I'd love to hear what
> people think on this issue, however.


It's an evolving thing.  Gen 1 was following the standards curves.  Gen
2 curves are now taking shape, and the big tendency is to go for
Lange/DJB curves, in part because they did the work recently, with best
available knowledge.

iang