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

From: Dan Brown <[email-masked]>
Date: Thu, 12 Mar 2015 11:40:35 +0000

Just to clarify, the old standards point formats are (per curve): 

fixed length octet strings,
big-endian (for mod p,n ints),
short Weierstrass,
x-only for computation purposes,

where old standards means IEEE 1363, ANSI X9.62/63, SEC1, NIST, FIPS, ...

with the _1_ exception ‎that _if_ ASN.1 is used to convey an ECDSA signature, as in PKIX/X.509, then the INTEGER type is used for r and s. If you are not using ASN.1, the old standards do not say how to encode a signature: you can encode however you like.  Weirdly, there's also an extra conversion to BIT STRING which is not even a proper way to do ASN.1: because a specific encod, DER, lands into an abstract value.   Here, I think ECDSA just followed the RSA /X.509 way.

I get the feeling that some people see ECDSA signatures in certs, and get the impression that _all_ the old point formats are variable length, and the ECDH calcs include y, etc. Wrong.

‎Also, there was an IKE spec that used both x and y for ECDH calcs, but I think that's been fixed.

Anyway, I slightly prefer the old formats, but don't mind adjusting them on a per curve basis, or perhaps per hash/KDF/signature_alg, if people say that's easy. It kinda precludes an old generic curve implementation being able to talk Curve25519 with a new implementation, but maybe that's what's wanted, anyway.

Best regards, 

-- Dan
  Original Message  
From: Viktor Dukhovni
Sent: Thursday, March 12, 2015 2:17 AM
To: [email-masked]
Reply To: [email-masked]
Subject: Re: [Cfrg] On why point and APIs formats matter (Re: Submission of curve25519 to NIST from CFRG -> was RE: On "non-NIST")

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

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

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.

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

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

On Thu, Mar 12, 2015 at 11:40:35AM +0000, Dan Brown wrote:
> Anyway, I slightly prefer the old formats, but don't mind adjusting
> them on a per curve basis, or perhaps per hash/KDF/signature_alg, if
> people say that's easy. [...]

The ECDH Curve25519 point representation doesn't work for signatures.
That same curve can be used with signatures in the Edwards form, but
we're calling it a different curve for this purpose.  So Curve25519 has
one point representation, and Ed25519 has another, even though they are
the same curve.  That's fine.

(Code duplication here is not a concern: it's either that or point
representation conversion code, and either way there's plenty of storage
for code like this in most every application.  Micro SDcards nowadays
are a complete computer, complete with RAM and flash storage for the
code run and state kept.)

>                   [...] It kinda precludes an old generic curve
> implementation being able to talk Curve25519 with a new
> implementation, but maybe that's what's wanted, anyway.

Neither that nor the opposite is nor should be a goal.  This is
icing-on-cake territory.  ECC implementations tend to be highly
optimized for each curve.  Genericity went out the window naturally, and
that's OK.

Mind you, if someone wants genericity, they can have it: just keep a
table of curve point representations and conversions.  That's not unlike
having codepoint assignments for Oakley MODP groups, just bigger tables,
and only slightly more code (after all, there's already a variety of
point representations to support generically, as you listed them).  It's
just not a big deal, but it does mean change for an "old generic curve
implementation", but that's not a breaking change.  Whereas changing
Curve25519's point representation would be a breaking change.

Codepoint assignments for standardized groups/curves are a very useful
thing from the points of view just about everyone.  We then start
talking about "groups" and "curves" as the registered objects rather
than the mathematical objects -- a small price to pay for the
convenience of codepoint assignments.

Nico
--

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 12 Mar 2015 18:42:00 +0000

+1 to what Nico and Watson wrote.

--  
Senior Architect, Akamai Technologies
IM: [email-masked] Twitter: RichSalz

---

From: Watson Ladd <[email-masked]>
Date: Thu, 12 Mar 2015 20:30:28 -0700

On Thu, Mar 12, 2015 at 4:40 AM, Dan Brown <[email-masked]> wrote:
> with the _1_ exception ‎that _if_ ASN.1 is used to convey an ECDSA
signature, as in PKIX/X.509, then the INTEGER type is used for r and s. If
you are not using ASN.1, the old standards do not say how to encode a
signature: you can encode however you like. Weirdly, there's also an extra
conversion to BIT STRING which is not even a proper way to do ASN.1:
because a specific encod, DER, lands into an abstract value. Here, I think
ECDSA just followed the RSA /X.509 way.

Except there is a choice between compressed and uncompressed. Yes, one can
design a good API that deals with these issues, but most existing
implementations don't do this, forcing the right choice of encoding onto
the caller. The padding bug I mentioned above results from a different type
confusion, where the x coordinate has the same type as a DHE result, and
that type is not a string of bytes put directly into the hash function, but
rather a bignum that can be encoded multiple ways.

>
> I get the feeling that some people see ECDSA signatures in certs, and get
the impression that _all_ the old point formats are variable length, and
the ECDH calcs include y, etc. Wrong.

But implementations that support signatures as well do have to deal with
two distinct encodings bignums, and there are two different lengths of
point encodings: one for compressed, one for uncompressed. It's possible
people have their own oddball encodings of ECDSA signatures, but having
such encodings makes higher-level APIs tricky: either encoding is a
separate step, or you multiply the number of functions.

> Anyway, I slightly prefer the old formats, but don't mind adjusting them
on a per curve basis, or perhaps per hash/KDF/signature_alg, if people say
that's easy. It kinda precludes an old generic curve implementation being
able to talk Curve25519 with a new implementation, but maybe that's what's
wanted, anyway.

Yes, it's true that if someone actually implemented generic curve support,
they wouldn't be able to automatically support Curve25519 unless TLS
decided to use the Weierstrass coordinates, as that's the only option for
generic curves in TLS. It is of course easy to support the current
Curve25519 format with an existing implementation of ECC multiplication:
one reverses the bytes, adds a constant, recovers y, carries out the ECC
multiplication, discards y, subtracts the constant, and reverses the bytes.

The point of limiting the number of formats is to write a pair of functions
curve25519_scalarmult(char *p, const char *q, const char *s), and
curve25519_scalarmult_base(char *p, const char *s), and likewise higher
level signing and verification functions that work for all protocols. These
functions can and probably will share code internally, and can use whatever
calculations are desired.

One can achieve this for any reasonable set of choices: it's not an
advantage of one form over another. I've written such code (well, almost)
for the choices NIST made. But it's much harder to do this correctly for
things not x coordinate Montgomery, and the varieties of formats don't help.

The concerns raised about little-endian representation and existing API
compatibility presuppose libraries that force all users to pay attention to
such details, even when all they want is to encrypt and sign data. The
claimed advantage of these libraries is the flexibility to parametrize
protocol implementations over curves, and let users implement any protocol.
But that's not the library application programmers actually want to use,
and it's irrelevant how the library works internally.

Sincerely,
Watson Ladd

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

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