[Cfrg] fwd: Re: [Cryptography] IETF discussion on new ECC curves.

[=JeffH <[e-mail]>]

[ discussions wrt CFRG curve selection process seems to be spread over a 
variety of lists. fwd'g fyi/fwiw/ftr/ymmv.. ]


Subject: Re: [Cryptography] IETF discussion on new ECC curves.
From: Trevor Perrin <[e-mail]>
Date: Sat, 26 Jul 2014 22:16:06 -0700
To: Phillip Hallam-Baker <[e-mail]>
Cc: "[e-mail]" <[e-mail]>

On Sat, Jul 26, 2014 at 11:32 AM, Phillip Hallam-Baker
<[e-mail]> wrote:
 > There was much discussion on new curves for ECC. The discussion looks
 > like it is down to choosing curves that are close to powers of 2 which
 > can be computed twice as fast as the traditional random curves in a
 > constant time implementation.
 >
 > The choices on the table right now are the NUMS curves proposed by
 > Brian LaMacchia and co at Microsoft and Dan Bernstein's Curve 25519
 > (2^255-19).

There should be more on the table.  Curve4417 (DJB et al) and
Ed448-Goldilocks (Mike Hamburg) are also good curves, at ~207 and ~224
bits of security.

https://eprint.iacr.org/2014/526.pdf
http://sourceforge.net/projects/ed448goldilocks/


 > One point of comparison of course is performance but it is actually
 > quite difficult to compare like with like. There does not seem to be
 > more than a 15% difference between any of them.

Here are some efficiency scores based on extrapolating performance vs
security for Microsoft NUMS (w-*-mers and ed-*mers), Curve25519,
Goldilocks, and others:

https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0

The differences are larger than 15%.  For example, Microsoft's fastest
512-bit curve takes close to twice the time of 448-bit Goldilocks.
But you would expect a 512-bit curve to be only ~40% slower than a
448-bit curve.


 > Most of the other
 > differences fall away when the point compression patent expires which
 > I am told is a matter of weeks.

US 6141420 expires Tuesday.


 > Another point that is important for me is consistency. I want as few
 > choices as possible. Given that the CA industry is going from RSA2048
 > with a putative work factor of 2^120 and all of these alternatives are
 > much faster and with much shorter keys, I can't see why I would go for
 > a 2^128 work factor. So I am only really looking for 2^256 work
 > factor.

It's reasonable to ask for a work factor significantly greater than
2^128 as a hedge against cryptanalysis.  But people like Adam Langley,
myself, and Mike Hamburg have argued that demanding the work factor
match a precise number (like 2^256) is over-prescriptive.

https://www.imperialviolet.org/2014/05/25/strengthmatching.html
https://moderncrypto.org/mail-archive/curves/2014/000140.html

Curve size has a significant effect on efficiency due to availability
of primes and options for dividing field elements into processor
words.

(Dan Bernstein has a great discussion of this:
https://moderncrypto.org/mail-archive/curves/2014/000237.html
)

So instead of fixing an exact security level (and thus curve size) in
advance, it makes more sense to consider a range of acceptable
security levels, and then choose a particularly efficient curve within
that range, as Curve4147, Goldilocks, and the 2^521-1 curves have
done.

 > What do folks think here? I see a bunch of possibilities
 >
 > 1) We choose the NUMS curve for the 2^256 work factor curve and Curve
 > 25519 for 2^128
 >
 > 2) We choose NUMS for both
 >
 > 3) We choose Curve25519 and E521
 >
 > 4) We spend several years arguing to no point

I think the world should move towards Curve25519 for a fast
"regular-strength" curve, and choose one efficient "extra-strength"
curve in the 384-512ish range.  Curve41417, Goldilocks, and E-521 seem
like prime contenders.

FWIW, there's a "curves" list where this and other topics in elliptic
curve crypto are discussed:

https://moderncrypto.org


Trevor
_______________________________________________
The cryptography mailing list
[e-mail]
http://www.metzdowd.com/mailman/listinfo/cryptography