Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry

[Douglas Stebila <[e-mail]>]

Recent news has highlighted doubts on a particular elliptic curve-based pseudorandom number generation algorithm, Dual_EC_DRBG, in which a particular point is used for which no explanation is given on how the point was generated. If it was generated so that its discrete logarithm is known with respect to another point, then a backdoor exists that can recover the seed.  (http://rump2007.cr.yp.to/15-shumow.pdf)

The NIST-standardized elliptic curves p256/p384/p512 are not related to this particular issue. 
- The prime p for each field has a special form chosen for efficiency (http://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf), not entirely unlike how the prime 2^155-19 was chosen for efficiency in curve25519.  There are no results that suggest that one prime is weaker than another prime for elliptic curve cryptography.
- The curve parameters were generated "verifiably at random", meaning a seed was chosen, and then the curve parameters a and b were generated by hashing the seed a pre-determined number of times using SHA-1.  (Appendix 4 ofhttp://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, or Section 3.1.3.1 of SEC1 http://secg.org, or ANSI X9.62)  
- I don't think it's specified how the generator was chosen, but the Diffie-Hellman problem is self-reducible, so there are no weak generators.

There are other reasons to support curve25519, including efficiency and resistance to side-channel attacks because constant-time implementations.  But not because of concerns over backdoors in p256/p384/p512.

Douglas


On 2013-09-09, at 11:34 AM, Patrick Pelletier <[e-mail]> wrote:

> Given the doubt that's recently been cast on the NIST curves, is it time to revive the idea of adding curve25519 as a named curve?
> 
> --Patrick
> 
> 
> On 3/1/10 4:20 PM, Adam Langley wrote:
>> We would like to start testing EC DHE in order to give our users
>> forward-secrecy.
>> 
>> In order to do this cheaply, one of the curves that we would like to
>> test with is curve25519[1]. There are several implementations of it
>> [2][3][4] and it's 3-4x faster than NIST's p256 (as implemented in
>> OpenSSL), while being constant-time.
>> 
>> Curve25519 doesn't currently appear on IANA's list of named curves[5]
>> and we would like to see it included.
>> 
>> As a first step I'd like to ask if there are any objections?
>> 
>> 
>> Cheers
>> 
>> AGL
>> 
>> 
>> [1] http://cr.yp.to/ecdh/curve25519-20060209.pdf
>> [2] http://cr.yp.to/ecdh.html
>> [3] http://code.google.com/p/curve25519-donna/
>> [4] http://bench.cr.yp.to/results-dh.html
>> [5] http://www.iana.org/assignments/tls-parameters/