Re: [Cfrg] Requirements for elliptic curves with a view towards constrained devices

["D. J. Bernstein" <[e-mail]>]

RONDEPIERRE Franck writes:
> It seems that the current CFRG discussion quickly swiped the
> "hardware" point of view, qualifying it as out of the topic.

Many people here consider hardware important. Fortunately, within the
scope that CFRG is considering (elliptic curves over big prime fields),
the best curves for software are also the best curves for hardware.

> For some devices, the code size is the main limitation and hence has
> to be taken into account prior to speed performances.

This isn't a software-vs.-hardware issue. Unnecessarily complex crypto
(the NIST P-256 prime, Weierstrass failure cases, ECDSA inversion, etc.;
see http://blog.cr.yp.to/20140323-ecdsa.html for many details) produces
crypto software that's hard to write, even harder to get right, a royal
pain to audit, and a huge source of security failures.

Fortunately, we know how to make ECC much simpler. This doesn't cause
trouble for the people who care about speed; it even improves speed.

I realize that IETF has historically done a very bad job of managing
migrations---people seem to think that the primary goal is to add new
options (e.g., TLS 1.3) rather than to eliminate the code for the bad
options (e.g., SSLv3); that "agility" means waving your arms rather than
getting your feet out of the tar pit. But some migrations do succeed.
There are many Internet protocols that haven't even started using ECC
yet, and it's easy to envision a path towards future implementations
that don't have to suffer through NIST's obsolete version of ECC.

> We analyze hereafter the impact of switching to Edwards curves while
> keeping Short-Weierstrass ones for backward compatibility.

Obviously, until a migration is complete, there's a certain minimum
level of code complexity required to handle the obsolete options. Adding
support for the new options costs very little code---even if new point
formats are used on the wire, as I recommend; the conversions are easy.

> The efficient implementations of Short-Weierstrass and Twisted Edwards (or
> Montgomery) formulae are quite different. Not only the group law operation is
> different but also the precomputations and the internal point representations
> are different. It thus doubles all the multiplication implementations:
> fixed-base case, variable-base case, double-scalar case.

No.

It's true that people _who want top speed_ will write separate code for
the fast new options (to the extent that it isn't written already), the
same way that they've already written separate code for, e.g., NIST
P-256 reduction.

It's obviously not true that people will write separate code if "the
code size is the main limitation". In that case they'll stick to a
merged code base using the obsolete Weierstrass approach to scalar
multiplication, because that's the only thing that the old curves
support. The new curves support this option too.

Obviously the reuse-old-code implementation option isn't the fast
implementation option---but if we stick to cofactor 1, as you recommend,
then we're _eliminating_ the fast option. What's the advantage supposed
to be? This is bad for all of the people who want more speed; it also
destroys the possibility of eventually migrating to a simpler code base
that throws away the obsolete Weierstrass approach.

> Furthermore, google.com, which is by far the most consulted website,
> currently processes around 10^5 requests per second

Searches are not connections; connections are not ECC operations; and,
most importantly, clients are not servers---often they're rather slow
smartphones. Google has already shown many times that it's willing to
sacrifice server performance for the sake of reduced client latency.

The bottom line, in any case, is that Google has already stated that it
cares about curve speed: "We're looking for a replacement [for P-256]
because we think that we can get something much faster and simpler."

> However when performances matters, why not taking Short Weierstrass
> curves with a=0?

That's an extremely special type of curve called a "GLV curve", adding
extra structure (an "endomorphism") for speed---but the main GLV speedup
is subject to Certicom patents 7100538 and 7995752. There are also nice
speeds from "GLV+GLS curves", including GLV+GLS Edwards curves, but all
of this is subject to the same patents. (Side question to Dan Brown:
Weren't you required to mention these patents when you suggested that
CFRG might be interested in these speeds?)

In the patent-free world, scalar multiplication for a=0 ends up being
slower than Montgomery and Edwards. The curve shape is also incompatible
with most primes (even if CFRG doesn't require twist-security), creating
larger gaps from powers of 2 and causing further slowdowns.

> Also for convenience, we think that the new curves should keep p=3 mod
> 4 as it is the case for most NIST and Brainpool curves: it allows
> simpler implementations and backward compatibility.

A moment ago you were insisting on measuring the code size for an
implementation that can handle the old options; now you're suddenly
advocating a requirement that eliminates, e.g., NIST P-224. This is a
strange notion of "backward compatibility".

Anyway, your underlying assessment of code size is incorrect. There's a
considerable cost in code size to handling NIST P-224 efficiently (see
http://cr.yp.to/papers/sqroot.pdf for the fastest options), but it's
very easy to handle primes that are 5 mod 8, such as Curve25519.

> This side-channel attack uses the fact that a zero value may appear in an
> intermediate result in the computation of the scalar multiplication, and that
> zero-value cannot be randomized with classical countermeasures.

False. For example, Coron's second countermeasure (more than 15 years
old now!) converts the input point into a random point, so the zero
disappears. There are many other important countermeasures against
side-channel attacks; would you rather have your resources devoted to
those countermeasures, or to unnecessarily slow curve computations?

---Dan