[Cryptography] IETF discussion on new ECC curves.

[Trevor Perrin]

On Sat, Jul 26, 2014 at 11:32 AM, Phillip Hallam-Baker
<phill at hallambaker.com> 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