[Cfrg] Another perspective on the Curve256/255 problem

[Phillip Hallam-Baker <[e-mail]>]

Lets recap what we need for Internet protocols, as far as I am
concerned there are only two buckets that matter:

WF128 - High performance / small public key size. 2^128 work factor
WF256 - High security delivering a confidence factor of 50+ years.
2^256 work factor

[I am using WF128 to remind ourselves that this is a 2^128 Work Factor
which is what really matters here.]

Given that any ECC scheme is a LOT faster than RSA2048 and much more
secure than RSA4048, it is actually quite easy to fit most
applications into one bucket or the other. Without really good reasons
to the contrary:

* Any key that is relied on for encryption of stored data should be WF256
* Any key that is embedded as a long term Key Signing Key must be WF256

So PKIX, S/MIME and OpenPGP should just use WF256. Which means that a
TLS stack is going to need the ability to do WF256.

PFS is a different case since in a well designed protocol, PFS is an
additional confidentiality control rather than a single point of
failure. Breaking the PFS key should only affect the forward secrecy
of a communication and then only if the master key exchange has been
compromised.

Since PFS is an additional control, there is a good argument that
performance is critical. The parties might just turn PFS off if it is
too slow. So there is quite an argument to be made to keep an WF128
bucket in that case.


At the meeting we saw the NUMS curves compared to the FastPrimes
curves and we saw two different arguments

DJB: Speed! Speed! Speed!

BAL: The most important thing is to assure people there is no special
reason for the choice of curve and so we must eliminate subjective
choices completely.


Now these are both important considerations of course. But DJB's
argument is only a good one for WF128 and BAL's is only really valid
for WF256.

Lets consider BAL's argument first.

For WF256, I think it is a really good one because the only way that
the 2^512-569 or E-521 curves is going to be breakable is if there is
either a flaw in the whole ECC approach or something really special
about a particular chosen curve. We can't know which curve might have
an issue but we can know the reason one curve is being chosen. 2^512
is a round number in crypto, 2^521 is a very odd one.

For WF128, BAL's argument is nonsense. Anyone who cares about the
possibility that the NSA might be manipulating the choice of prime
should be using WF256 crypto. There is a chance that there is
something odd about Curve25519 that makes it easier top break. But the
chance that there is a flaw in ECC that makes Curve25519 highly
vulnerable but leaves 2^256-x unscathed is much smaller.


Equally, DJB's arguments for speed don't really apply at the WF256
level. There isn't a conveniently close curve for a start. So there is
a 'gut check' call and we go looking for Goldilocks curves.

All of the curve choices on offer are significantly faster than
RSA2048 which is what every major application doing public key is
using today. All other things being equal, performance is significant.
But there are many things that have a higher priority:

* Explaining the choice.
* Compatibility with legacy crypto HSMs
* Compatibility with standard data paths

All these arguments favor the 2^512-569 curve. It is really easy to
explain that this is the natural compliment to AES256. E21 is not
going to be offering any more security and might well offer less.

Having sold crypto for 20 years I know that what people care about
most is strength even if they have no clue what it means. It is not
unusual for someone to argue that its too much CPU to turn on TLS
everywhere. Then after they finally decide to bit the bullet they turn
on AES256 because they can. This despite the fact that RSA2048 is the
weakest link.


My people can sell ECC certs pretty easily as being the essential
compliment to AES256. And that is probably the fastest route to
getting ubiquitous deployment of PFS. That speaks for a WF256 solution
that has as little to cloud the argument as possible.

So in my view, the split decision is actually a lot more principled
than splitting the baby. The two camps are focused on different
security needs at different poles and are making the arguments suited
to their chosen poles. Further, we are seeing deployment of Curve25519
which might well be making the issue of choosing a different curve
problematic.


So in summary, these are the suite choices I think would be relevant to TLS:

Key Signing Certs:  RSA4096 or RSA2048 or NUMS-512 ECDSA
End-Entity Certs: RSA2048 or NUMS-512 ECDSA

WF128 security:
    AES-128-GCM + Curve25519 ECDHE PFS

WF256 security:
    AES-256-GCM + NUMS-512 ECDHE PFS

Additional:
    AES-256-GCM + Curve25519 ECDHE PFS
    CHA-CHA-POLY + Curve25519 ECDHE PFS
    CHA-CHA-POLY + NUMS-512 ECDHE PFS


That would make for a total of 10 new suite IDs assuming we go for the
CHA-CHA-POLY options as well.

This time I would want to restrict RSA to a specific key size. There
is no point in using a RSA4096 EE cert with ECC crypto (!) and nothing
less is permitted. So lets nix that degree of freedom.