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

[Nico Williams <[e-mail]>]

On Tue, Mar 10, 2015 at 07:20:31PM -0700, Watson Ladd wrote:
> On Tue, Mar 10, 2015 at 6:14 PM, Paul Lambert <[e-mail]> 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.

+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?

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

This ^^^.

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

Yes.

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

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

Nico
--