[curves] The great debate over point formats (Mike Hamburg)

[Michael Hamburg]

On Feb 2, 2014, at 11:55 AM, Paulo S. L. M. Barreto <pbarreto at larc.usp.br> wrote:

> On Sun, February 2, 2014 16:10, Mike Hamburg wrote:
>> Furthermore, P-384 is pretty ugly -- it's a non-64-bit-aligned pentanomial --
>> and I don't think it makes sense to use that field unless we want some sort of
>> compatibility.
> 
> I wonder where this baffling "ugliness" trend originated. It is clearly
> impossible to make everybody happy. Some will find non-NIST field "ugly"
> because of compatibility concerns, some others will find NIST fields "ugly"
> because they are outdated, and so on. Someone might well find all
> non-trinomials (e.g. 2^255 - 2^4 - 2^1 - 1) "ugly," someone else might find
> all polinomials whose exponents are not all multiples of 64 (e.g. 2^255 - 2^4
> - 2^1 - 1) "ugly," and yet someone else might find non-128-bit aligned
> trinomials or pentanomials (e.g. 2^448 - 2^224 - 1) "ugly," without end (this
> list is clearly far from exhaustive). Tell me about Greeks and Trojans…

You’re right.  I shouldn’t have said “ugly”.

What I meant is that implementations of P-384 on most modern processors are slower and more complex than those of other primes at a similar security level, and I suspect that this trend will get worse in the future.  For example, "openssl speed” on my 64-bit laptop reports that ECDH-P521 takes about 15% longer than ECDH-P384, but it’s computing 35% more field operations.  So the 384-bit field is significantly slower.

Contrast this to a vectorless 32-bit ARM (Cortex A9): ECDH-P521 takes 2.15x as long as ECDH-P384, which is almost what you’d expect from their sizes.  P-384 was designed for 32-bit full-radix implementations, and it only performs well on hardware that also favors those implementations.

>> I agree that there are serious concerns about any compatibility strategy.
>> "Nobody pours new wine into old wineskins," such a compatible design would
>> have most of the problems of both new and old.
> 
> This is utterly impossible to solve. NIST primes are old. They were designed
> with 32-bit processors in mind. If we focus on 64 bits, or even on 128 bits,
> we'll soon enough have people complaining "why didn't those short-sighted guys
> choose 256-bit aligned polynomials?”

I was referring to the Weierstrass form with this comment, not the prime shape.  I agree with Robert and Watson from a few posts ago (and, it seems, with you) that it’s dangerous to try to reuse Weierstrass implementations with new curves, because they’ll have the problems of the old ones (incomplete formulas) and the new (cofactors), and possibly worse ones from the combination (cofactors leading to corner cases).

And again, you’re right.  If we choose primes which require a certain implementation or particular hardware to be fast, that will be a short-sighted decision.

Cheers,
— Mike