Re: [Cfrg] Curve manipulation, revisited

[Watson Ladd <[e-mail]>]

On Thu, Dec 25, 2014 at 7:14 AM, Adam Langley <[e-mail]> wrote:
> 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.

We're tasked with using our expertise on behalf of those who don't
have it, not making the same mistakes as they would make. They can do
that last part themselves perfectly well.

>
> 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.

It's important not to confuse "rigidity" with actually constraining
the choice of curve meaningfully. The question is not how many curves
can be generated, but how many curves the user will accept. A user who
accepts a curve generated by taking a mathematical constant, and
running it through a hash function to generate a prime and parameters,
is in fact accepting billions of potential curves.  A user who
accepted the NUMS method is accepting potentially far more curves than
one who demands high performance with numerically minimal parameters.

By contrast it is extremely hard to generate high performance primes.
Even superficially good choices can fall short.

>
> 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.

Even someone who doesn't really understand ECC should recognize the
impact of gotchas in standards. But Microsoft in April was putting
forward short Weierstrass form and an incomplete formula for Edwards,
arguing that the compatibility of short Weierstrass form outweighed
the performance and simplicity advantages. By August they had
abandoned the Weierstrass curves, and it is unclear to me at what
point the use of incomplete coordinates was abandoned. In short,
Microsoft's original proposal was considerably worse than the
alternative, and their new proposal is not better than the
alternative, even on criteria they claim to be using.

>
> 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.

Exactly. It is now the deadline: are we going to miss it because we
cannot get the 128 bit level out, despite unanimity on what it should
be?

The option to proceed with the 128 bit level first has always existed:
I hope the chairs see fit to exercise it, and leave the
higher-security level discussion for later.

In 9 months, not a single security issue with the original Curve25519
proposal has been found. It is high time we produce something.

>
> 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.

Basepoints and isogenies don't change security: if the Microsoft curve
is isogenous to Curve25519, why not use Curve25519?

>
> 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.

I don't think this is quite right. Imagine we could improve the square
root in Pollard rho to cube root via some algebraic geometry. Then
255/3=85, but 448/3=150. Even ignoring the possibility of algorithmic
improvements, progress in computing power may mean data that has to be
confidential for centuries needs a larger curve. The NSA did pick P384
for a reason.

But we can always select E521 as the large curve, or Ed448, for people
who *actually are using larger Edwards curves today*. The suggestion
to use 2^389-21 is not as good as once seemed: there are other primes
which seem much better, including Goldilocks. Sadly, the absence of a
reasonably optimized portable NUMS implementation, or a Supercop
submission, is making getting hard numbers from identical test
conditions difficult. Differences in the point format Ed448 uses are
another annoyance with getting hard numbers out.

>
> 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.

Basepoints don't affect security. As for the Ed25519 signature format,
I'd note that Supercop and Nacl attach the signature to the message,
while Py-ed25519 isn't: this is the major difference. The private key
format for NaCl in the diagram seems to be the right choice, as it
doesn't require an extra hash before using, but opinions may vary. (I
make no statement about the sanity of the NaCl format for signed
messages, only to note that it does make use of simple hash function
interface possible)

Despite the stated need for rigidity, Microsoft is now endorsing a
proposal that is different from the one they did earlier, even with
the same choice of primes.  A user who thinks that NUMS is better than
the alternative for rigidity has to ask how much flexibility there
really is. Certainly not none, probably nowhere near enough to get
more than "BAD", and almost certainly not "BADA".

Sincerely,
Watson Ladd

>
> [1] https://blog.mozilla.org/warner/files/2011/11/key-formats.png
>
>
> Cheers
>
> AGL
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin