[Cfrg] Good and bad curves

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

Certain curves are known to be weaker than other due to attacks that
require the curve meet specific criteria. There are essentially three
ways to address this problem

1) Reject curve choices that are known to be 'weak', i.e. vulnerable
to known attacks.

2) Do 1 and increase the bit length by a safety factor in case the
attack can be extended.

3) Just increase the bit length and do not attempt to reject weak curves.


My preference is for (3) since any attempt to select curves creates an
opening for IPR claims and we are going to need the safety margin
anyway.

The problem we face is not to find the best compromise or speed and
performance as some suggest. None of us know the set of unknown
attacks by definition. Even Fort Meade only knows a subset of unknown
attacks. So none of us is competent to decide on a compromise.


What the known attacks can tell us usefully is how big a safety margin
we need. So if there is an attack against curves formed from
co-factors of warped smooth numbers that reduces the work factor from
x bits to x/2 then we want a safety margin of 2 times the number of
bits regardless. So it would be interesting to see people raise those
attacks.



What this is really about is coming to a defensible choice that can
become the industry consensus. And this gets us to Bruce's observation
that any security signal inevitably gets wound up to one step below
maximum and stays there. Because nobody wants to take responsibility
for lowering the security precautions. [We now have confirmation of
what was suspected at the time, that the DHS scheme only ever went to
yellow when there was a political need to raise it to orange in the
near future],

The industry can't manage a large number of curves. In fact we only
have a need for an orange curve and a red one. Curve 25519 is plenty
fast enough that we don't need to consider alternatives and it is
comfortably secure for use as the orange curve.

We really only need one red curve and the criteria that matters is
defensibility. The 56 bit DES key space was always suspect because it
was such an odd number. 64 bits would have been just as easy, So it
was pretty clear that there was a fix in somewhere. If we go for a 480
bit key we will get similar questions.

If CFRG proposes a 480 bit key and some other group proposes 512 then
the 512 is going to win. Because there is a cost to explaining the
reason 480 bits are 'enough' and there will also be lost sales. And
those matter far more to me than some explanation about a blend of
performance that requires a PhD to fully understand.

The Red curve is going to be 512 bit. I can defend that choice very
easily because it is the largest memory bus size in common use.

Now '512 bit' could mean a prime slightly smaller like 511 or 510
bits. But it can't be suspiciously lower.


There is also a personal career development issue here. I don't think
anyone wants to leave this discussion being known as the guy (or gal)
who persuaded the industry to use the lower security option.