Subject: [Cfrg] On why point and APIs formats matter (Re: Submission of curve25519 to NIST from CFRG -> was RE: On "non-NIST")

From: Watson Ladd <[email-masked]>
Date: Tue, 10 Mar 2015 19:20:31 -0700

On Tue, Mar 10, 2015 at 6:14 PM, Paul Lambert <[email-masked]> wrote:
> It would be a mistake to delay an opportunity to send a recommendation from
> this
>
> committee to NIST. Please note the quote:
>
>      "NIST encourages presentations and reports
>
>       on preliminary work that participants plan
>
>       to publish elsewhere."
>
> Your concerns about endianness are a trivial in comparison to the
>
> overall industry change to new public key algorithms.  Please have some
> focus
>
> and do not add noise to the topic.

No, they aren't: they are actually much more important than the
question of which curve to use. Periodically some TLS implementation
will investigate a rare failure of their NIST ECC implementation when
negotiating a handshake. And what will have happened is that they
encoded the x coordinate as a DHE result is encoded, without leading
null bytes. But this is incorrect: the x coordinate is zero padded in
ECDHE results.

These bugs and many like them are the result of poor internal design
of cryptography libraries, that treat all public key primitives as
accepting bignums. If you make that design choice, then yes, using
little-endian makes the Curve25519 implementation more difficult. But
that design choice makes using the library much more difficult:
instead of a single function call, the user has to make multiple calls
to encode and decode data, before and after cryptography. For extra
credit, ensure the decoding function cannot be used to properly
validate PKCS 1.5 signatures, and the calls expose failures that
shouldn't be revealed.

Of course, NIST standards (actually NSA, laundered through SEC1 and
ANSI X.9) do properly specify this. But they define *multiple*
separate encoding for public keys, mean that one has to specify two
separate encodings in a protocol using NIST curves, namely one for the
keys on the wire and a second for the ECDH result. Signatures have
their own ASN.1 inspired encoding, forcing multiple variations on
bignum encoding and decoding.

Furthermore, the choice of how to represent public keys has security
implications. Montgomery x-coordinate has, as everyone has noted, very
large improvements in simplicity, and hence security. The fact that
there is a unique encoding means that the API can be extremely simple
and difficult to misuse.

By contrast, which curve to choose (out of a set with the same shape)
doesn't have nearly the same impact on security or performance.  Given
the preliminary nature of NISTs efforts, it's far more useful to talk
about the important choices then the unimportant ones.

>
>
>
> The topic was a request to the Chairs to relay a position from this task
> group
>
> to NIST before the March 15th deadline.

And that position should reflect the choices that impact security and
interoperability, most of which haven't been officially made, rather
than the ones which don't, which have been made. I don't see what we
have to add on the subject that would represent a consensus view.

Sincerely,
Watson Ladd

>
>
>
> Paul
>
>
>
>
>
> From: Watson Ladd [mailto:[email-masked]]
> Sent: Tuesday, March 10, 2015 4:20 PM
> To: Paul Lambert
> Cc: [email-masked]; Tony Arcieri; [email-masked]
> Subject: RE: [Cfrg] Submission of curve25519 to NIST from CFRG -> was RE: On
> "non-NIST"
>
>
>
>
> On Mar 10, 2015 3:34 PM, "Paul Lambert" <[email-masked]> wrote:
>>
>> > Standards fragmentation is a fact of life. But we should strive to
>> > minimize it.
>> >And we shouldn't make it worse by varying endianess or encoding for
>>
>> Could we please desist with the off-topic rants.  This was a request to
>> the Chairs
>> to work more directly with NIST to propagate this task groups
>> recommendations.
>
> This group only has a recommendation of a curve right now. But that's not
> enough: you need to specify what gets sent on the wire, and that's where
> NIST potentially picks differently. So it's not enough to say use these
> primes and these curves to NIST: that won't necessarily have the effect you
> intend, precisely because that doesn't specify the coordinates and encoding,
> even if they take our suggestion as opposed to others.
>
> That's the worst possible outcome, especially if the names are the same.
>
>>
>> There was NO mention of endian! Such irrelevant points only add noise to
>> the mailing list.
>>
>> >something that for 8 years was done a different way: there's no
>> >benefit to doing it needlessly.
>>
>> Duh … and what about the 15+ years everyone else has setup the
>> bytes the other way round… (please do not answer on list, I don’t
>> care about the byte order today, my point is on irrelevant noise
>>
>> and arguments).  If you wish to debate endian … start your
>> own new subject line.
>>
>>
>>
>> Paul
>>
>>
>>
>>
>>
>> From: Watson Ladd [mailto:[email-masked]]
>> Sent: Tuesday, March 10, 2015 3:22 PM
>> To: Tony Arcieri
>> Cc:[email-masked]; Paul Lambert;[email-masked]
>>
>> Subject: Re: [Cfrg] Submission of curve25519 to NIST from CFRG -> was RE:
>> On "non-NIST"
>>
>>
>>
>>
>> On Mar 10, 2015 3:17 PM, "Tony Arcieri" <[email-masked]> wrote:
>> >
>> > I am very curious about this as well. It would make for a very confusing
>> > situation if NIST adopted different curves from the CFRG curves.
>> >
>>
>> and Brainpool, and the French and Chinese governments, and the Russians,
>> and the Brazilians.
>>
>> Standards fragmentation is a fact of life. But we should strive to
>> minimize it. And we shouldn't make it worse by varying endianess or encoding
>> for something that for 8 years was done a different way: there's no benefit
>> to doing it needlessly.
>>
>> > --
>> > Tony Arcieri
>> >
>> > _______________________________________________
>> > Cfrg mailing list
>> >[email-masked]
>> >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

---

From: Nico Williams <[email-masked]>
Date: Thu, 12 Mar 2015 00:37:30 -0500

> validate PKCS 1.5 signatures, and the calls expose failures that

+1

In addition to API simplicity, for which Curve25519 sets a high bar!,
there are other reasons to stick with its use of little-endian encoding:

 - it (the encoding) is fast (not just simple)

 - code exists and has been deployed, why break it?

   Sure, if using Montgomery x-only, fixed-length, little-endian created
   a security vulnerability...  But it does not.

   (We can say that there's nothing to break.  But that's not true.  It
   means significant amounts of code will need to be modified,
   re-written, or be allowed to lapse into obsolescense.  No thanks.)

 - fixed-length coordinate encodings mean no need to add additional
   length encoding as compared to bignums (I'm repeating the simplicity
   argument here)

 - with modular DH we had true genericity (see the SSHv2 "group
   exchange" protocol, which allows the server to use a group that it
   computed if it wants to), but with ECC we've long ago left that
   behind

   We'll never have a node send parameters for curves of its own
   invention.  Therefore we don't need truly generic encodings for
   points on curves.

and finally:

 - insisting on a common point encoding is a huge complication (e.g., if
   we insisted on sending x and y, or x and sign of y) that precludes
   useful optimizations like Montgomery x-only.

   Again, a reprise of the simplicity argument, with more feeling, but
   also a more detailed rationale.

   These optimizations optimize more than bandwidth and/or CPU.  They
   also optimize away patent claims, which have a lot to do with getting
   solid crypto deployed widely.

   Nobody wanted to hammer Curve25519 into existing point encodings so
   it could be used in TLS, but many have been begging for TLS support
   for Curve25519.  The recognized solution is: let each curve dictate
   how points are to be encoded, and having done so, accept that they
   dictate different point encodings.  This is strong evidence in favor of
   this approach!

   (Incidentally, if someone wanted to use a different point
   representation for the same curve as Curve25519, they could, they'd
   just get a different curve registration, which is just fine.)

   WHY would we now try to force TLS WG back to a generic point
   encoding?  Or worse still, to a negotiable point encoding?

> there is a unique encoding means that the API can be extremely simple

This ^^^.

> about the important choices then the unimportant ones.

Yes.

> > The topic was a request to the Chairs to relay a position from this
> > task group
> >

I agree with everything that Watson said above (including the bit that I
elided).  +1e6.

Nico
--

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 12 Mar 2015 06:17:02 +0000

On Tue, Mar 10, 2015 at 07:20:31PM -0700, Watson Ladd wrote:

> question of which curve to use.

Though I still retain enough graduate school mathematics to understand
the fundamentals of EC crypto, I am not a mathematician or cryptographer.
Rather, these days I am an implementor of applications that employ
crypto, most notably Postfix where I maintain the SMTP TLS feature-set,
and I have plans to contribute DANE support to one or more TLS libraries.

So with my implementor hat on (the only hat that fits here), I'd
like very much to second Watson's remarks.

In the DANE space with 24 different combinations of the TLSA (usage,
selector, mtype) parameters not only do essentially all the other
implementations I've tried to read offer incomplete support for
some corner cases, they are also insecure for a subset of the
parameters!  On top of that, users get confused and publish
incorrect records.

Yes, the analogy is rather imperfect, but I believe that the key
observations Watson makes are relevant.

(In)security will depend a lot more on how easy it is to implement
the design incorrectly than on how easy it will be to perform a
cryptanalytic attack.  The curves considered here are sufficiently
strong to make implementation considerations be a key differentiator.

So if we can agree that 25519 with a fixed length little-endian
octet-string encoding (not variable length big-endian int) is more
robust in the hands of mortal implementors, that should be given
due consideration.

-- 
	Viktor.

---

From: James Cloos <[email-masked]>
Date: Thu, 12 Mar 2015 09:13:59 -0400

>>>>> "NW" == Nico Williams <[email-masked]> writes:

NW> In addition to API simplicity, for which Curve25519 sets a high bar!,
NW> there are other reasons to stick with its use of little-endian encoding:

Those reasons are valid for keeping 25519 as it is, but do not imply
that new curves also need to be little-endian.

Each curve should define all of its particulars, with points et alia
always -- of course -- stored and transmitted as fixed lenght octet
strings.  But that allows any curve to choose big-endian.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Nico Williams <[email-masked]>
Date: Thu, 12 Mar 2015 11:26:23 -0500

> that new curves also need to be little-endian.

Indeed it doesn't.

> strings.  But that allows any curve to choose big-endian.

+1.

Though Montgomery x-only point representations naturally lend themselves
to fixed-length x representations with whatever endianness is most
convenient in the most common case (x85_64), which happens to be
little-endian.  I'd expect little-endian to be the common choice, but
I'd certainly not require it!

Nico
--