[Cfrg] Why I think 256-level is a bad idea [Was: Re: Elliptic Curves - poll on security levels (ends on February 17th)]

[Ilari Liusvaara <[e-mail]>]

On Wed, Feb 11, 2015 at 10:24:13AM -0800, Eric Rescorla wrote:
> On Tue, Feb 10, 2015 at 2:52 AM, Alexey Melnikov <[e-mail]>
> wrote:
> 
> > CFRG chairs are starting a poll, containing 2 initial questions:
> >
> > Q1: Should CFRG recommend a curve at the 192-bit security level?
> >
> > Q2: Should CFRG recommend a curve at the 256-bit security level?
> >
> > Answering Yes/No to each of these would suffice.
> 
> 
> Sorry for giving an unclear answer, but:
> 
> I believe that the CFRG should probably specify one stronger curve at
> either 192 or 256.
> Both of these seem to have arguments in favor, but if I were pushed I would
> probably
> go for 256 for the reason that if we're going to be conservative we should
> be really
> conservative.

I consider 256-level curve a bad idea (and Goldilocks as the largest practical
curve) for the following reasons:

1) Too slow

We have performance budgets, and the real world standard for higher-
security curve is P384, so that sets our performance budget.

Now, P-384 implelmentation in OpenSSL is hilariously bad (In fact, I seem
to have a version of OpenSSL where P-521 is faster(!) than P-384). But
proper P-384 would be a lot faster and even well-optimized E-521 would be
slower.

I would estimate that 256-level is about half the speed (for E-521, since
that's faster than 512-bit curves) of 192-level (and goldilocks would be
about 25% slower than 192-level, due to extraordinarily efficient prime).
This is on top of 2.5-3x penalty for 192-level over 128-level.

And remember that some CA people have actually expressed interest at
actually using the larger curve.

There's also similar arguments on low side (P-256 is the standard there),
but Curve25519 (or whatever it is called) delivers the needed performance.


2) Signature problems

Pretty much anything larger than Goldilocks (448-bit p, so ~224 security,
albeit NIST specs seem say it would be 192) runs into trouble with
signatures.

Specifically, such curve would require one of:
- Questionable signature primitives.
- >512-bit hashes (rare, so replaceability becomes a problem).
- Hash extension (very easy to get this wrong).


3) No real security benefit

Anything that can actually break 192-224 bit curve would cast at least
serious doubt on 256 bit curve (imminent breach), if not break it outright.

Rho aginst Curve25519 is already extremely nasty (due to thermodynamical
limitations). But that's a joke compared to rho on 192-224 level curve.
So classical computation projections appear invalid, so actual threats
come elsewhere. E.g. Major cryptoanalysis results, large enough QC.


4) TLS limitations

TLS is seemingly built only for up to 192-level security (even in 1.3).
One could extend TLS for 256-level, but this would run into issues with
symmetric encryption (E-521 and AES-256 aren't even close to being
matched).

Not really useful, given how high 192-level security really is.



Summary:
So not much less vague: There should be one stronger curve, at least
on 192-level (to match the present standard), but faster than P384.

Out of 192 or 256, I would say 192 (but unconstrained choice in range
might be different, but no higher than 224).



-Ilari