Re: [Cfrg] Curve manipulation, revisited

[Adam Langley <[e-mail]>]

On Wed, Dec 24, 2014 at 10:47 PM, D. J. Bernstein <[e-mail]> wrote:
> This process began in September 2013, after news of NSA sabotage of
> cryptographic standards: Patrick Pelletier wrote
>
>    Given the doubt that's recently been cast on the NIST curves, is it
>    time to revive the idea of adding curve25519 as a named curve?
>
> on the TLS mailing list. Doug Stebila followed up to say that the
> reasons to support Curve25519 were "efficiency and resistance to
> side-channel attacks" rather than concerns about backdoors. Nick
> Mathewson wrote

Nobody knowledgeable in ECC (that I know of) seriously believes that
the NIST curves are backdoored. But I've observed that the less
knowledgeable people are, the more likely they are to believe it.

Dual-EC had the subtlety of Wile E. Coyote leaving a pile of "Free
Bird Seed" on the road but, prior to 2013, I think most people
(certainly including myself) applied Hanlon's razor and disbelief that
the NSA would do something so stupid and concluded that there was
likely an innocent explanation for it. But many outside of
cryptography circles draw strong parallels between Dual-EC and NIST
curves, I think because they can't see the huge difference: there was
clearly room for a backdoor in Dual-EC, the question was "would they
really?", but a backdoor in P-256 would be alien technology.

Because of this, I suspect that Microsoft feel a need to assuage the
worries of their customers (who will generally fall into the
"less-knowledgeable" group) and provide a "NIST free" option for them.
However, because they are a US company, I imagine that they also feel
the need to demonstrate that they can't have "cooked" the alternative.
(This is all presumption—I'm obviously not familiar with Microsoft's
customer relations nor deliberations.)

But I think this (and a soupçon of ego; something that applies to
everyone) explains Microsoft's continuing strong preference for
"rigidity" in their curves. A conflict arises because Microsoft's
original drive for "rigidity" excluded everything else; including
applying any intelligence to the choice of prime or assigning any
weight to existing practice.

Yourself, myself and others want to replace P-256 not to assuage
backdoor fears, but because a replacement can be significantly faster,
safer and simpler. And we're not hand cuffing ourselves because we're
afraid of being accused of having cards up our sleeves. Finally,
although curve25519 is now pretty common in our world (SSH, OpenPGP,
QUIC etc), it has no presence in the Microsoft ecosystem at all.

You've pointed out, with bada55, that claims of rigidity are, in
general, rather limited and you're correct that Microsoft's movements
towards curve25519 and other changes are highlighting that. But that's
because we didn't accept the choices that were based on their fitness
function. I think they are trying to maintain their larger curve as
being more "rigid" (which, remember, is to convince people who don't
really understand) while accepting something more reasonable (to us)
at the 128-bit level in the hopes of getting the RFC done.

And it would be good to get something done. At present, it's unclear
whether this WG effort will manage to produce anything at all and
failure would mostly benefit P-256. Curve25519 certainly has
increasing presence, but that's in places that will do the smart thing
anyway. But there are lot of places that are less visible to
cryptographers that go with P-256 because it's "standard".
(BluetoothLE-based systems keep popping up in my view.) A failure of
this WG will probably ensure that continues.

It would be also be good to have Microsoft onboard. Microsoft software
is pretty common after all, even if people like us don't see it much.
Although I think we pass the IETF/IRTF bar of "rough consensus"
without them, I don't know if the chairs agree and it would be sad
outcome even if they did.

Curve25519 is sufficiently common now (in our side of the world, at
least) that it's not going away and each different curve supported is
quite a lot of work. (More, I think, than most people realise.) So I
want something very close (or equal) to curve25519 at ~128-bits in
order to minimise implementation, confusion and code size and achieve
the speed, simplicity and robustness that were the point of the whole
exercise.

I'm skeptical that a larger curve is actually useful. I think ~128 and
~192 bit curves have shared fate to the point where the risks from
supporting any extra curve outweigh the benefits. I don't plan on
supporting any larger curve that this WG may produce (even more so if
it's an "ugly" curve). If nothing else, P-384 isn't going away.

So I would be happy with this WG producing curve25519 and a "rigid"
curve at ~192 that Microsoft need. But, even to get there (and it's
unclear whether anyone else would be happy with that) there are still
questions at the ~128 bit level. At the moment, although Kenny has
asked MS to adopt the curve/twist cofactor criteria that results in
curve25519 being produced, Microsoft's generation procedure results in
a different base point and has an isogenous Edwards curve while the
rest of the world uses an isomorphic one. Ed25519 already has a number
of public, private and signature formats[1] however, so perhaps the
isogeny/isomorphism doesn't matter if the conversion can be done "for
free" when converting to affine anyway, but I'm not a cryptographer
and am not comfortable concluding anything here.

[1] https://blog.mozilla.org/warner/files/2011/11/key-formats.png


Cheers

AGL