Subject: Re: [Cfrg] Point format endian (was: Adoption of draft-ladd-spake2 as a RG document)

From: Peter Gutmann <[email-masked]>
Date: Tue, 27 Jan 2015 11:03:13 +0000

Stephen Farrell <[email-masked]> writes:
>On 27/01/15 10:34, Peter Gutmann wrote:
>> The universal standard for crypto bignums is big-endian
>Hmmm.... sez who? :-)

Name any significant IETF (i.e. CFRG-relevant) crypto standard that uses
little-endian bignums.

>But seriously, if in fact this makes little or no difference, which I believe
>is the case, and which I believe you are also arguing, then what is the
>problem with going with the initial coder's choice here?

Because, as I've already pointed out in an earlier message, if the universal
standard is big-endian and the vast majority of your potential user base (via
OpenSSL, not sure about MS CryptoAPI) only does big-endian, then choosing a
format that's not big-endian is a really bad idea.

Peter.

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 27 Jan 2015 11:10:37 +0000

On 27 January 2015 11:03:13 GMT+00:00, Peter Gutmann <[email-masked]> wrote:
>Because, as I've already pointed out in an earlier message, if the universal standard is big-endian and the vast majority of your potential user base (via OpenSSL, not sure about MS CryptoAPI) only does big-endian, then choosing a format that's not big-endian is a really bad idea.

Well, OpenSSL, via Rich Salz, seems to be perfectly okay with the draft's endian as it is. (As is BoringSSL, via agl, of course.)

They're obviously going to use the specialised routines, not generic bignum ones.

Can't see the problem here with it as it is. I can see a problem with changing it.

+1 little-endian here.

- --
/akr

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 27 Jan 2015 11:16:06 +0000

> Name any significant IETF (i.e. CFRG-relevant) crypto standard that uses

Maybe this one? The point is that if we don't care much
then we don't care much.

> format that's not big-endian is a really bad idea.

You didn't say why. Why is it a bad idea? What is the downside?
("only does big-endian" isn't it clearly, because if the little
endian form were adopted here that'd no longer be true so the
question is how that'd cause problems if the spec called for it
to be done.)

I'm really asking there and not point-scoring btw. mostly because I
think this entire process has been quite fraught about even the
least important things, and I'd hope we don't do that to ourselves
again;-)

S.

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

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 27 Jan 2015 14:33:17 +0000

> OpenSSL, not sure about MS CryptoAPI) only does big-endian, then choosing
> a format that's not big-endian is a really bad idea.

OpenSSL does not care.  I speak as a member of the development team.

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 27 Jan 2015 08:41:46 -0800 (PST)

> least important things, and I'd hope we don't do that to ourselves

  It's a bad idea because standards like X9.62 and ISO/IEC 15946
and RFC 5090 have all defined the way to go from a bitstring to an
integer to a field element and back that involve representation in
big endian. This is the canonical conversion between bit strings
and elements.

  And this is not some arbitrary issue that can just be relegated to
the bowels of the crypto library where we no longer care. Knowledge
of the special-case-ness of curve25519 will percolate up to the
application writer. For instance,

  * After doing an ECDH you take the X-coordinate and pass it to
    a KDF. But how? Well, there's those rules to go from field element
    to integer to bitstring. Except now you have to have a special case.
    So you do BN_bn2bin() unless it's curve25519 then you do
    BN_bn2binle() (which doesn't exist now for a very good reason).

   * Or Imagine if someone wanted to implement Watson's SPAKE2 draft.
    It involves hashing into an elliptic curve to get elements M and N.
    So after you hash up a bunch of cruft you convert the digest as a bit
    string into an integer and then into the X-coordinate of your element.
    But how do you do that? Well you do BN_bin2bn() unless it's curve25519
    and then you do BN_bin2bnle() (which does not exist now for a very
    good reason).

  This spells interop problems even if you just adopt DJB's code to
handle curve25519. Special cases will be a continued source of trouble.

  And for what? At least Martin Luther had a list of grievances that he
nailed to the church door to start his reformation. This particular attempt
at reformation to free curves from the canonical format has none.

  regards,

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 27 Jan 2015 09:07:56 -0800

> handle curve25519. Special cases will be a continued source of trouble.

Curve25519 was specified as a function from 32 byte strings cross a
private key to 32 byte strings. There is no conversion from field
elements to strings before or after a Curve25519 calculation.

My SPAKE2 draft contains specified M&N, generated by a C program
Nathan McCullum sent me. I've been unable to determine what that
program does in anything more than the vaguest terms because OpenSSL
internals are opaque, but users do not need to generate their own
points.

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

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 27 Jan 2015 09:20:17 -0800

> big endian. This is the canonical conversion between bit strings

This is not a good thing.  I've worked on software that manipulates
P-256 public keys.  They're *variable length* because someone thought
that this was a good idea.

>     BN_bn2binle() (which doesn't exist now for a very good reason).

Sorry, but this is backwards.

As an application writer, I want to pass a string of bytes into the
bowels of the crypto library, and I want to get a string of bytes
back.  I despise the fact that, with current crypto, I have to parse
some ASN.1 crap to figure out *how many* bytes to pass to the crypto
library.

Given a choice between using ASN.1-encoded numbers (or sequences or
whatever) and strings of bytes of either endianness, I'll take the
byte strings any day.

(Also, it's 100% unambiguous how to pass octet strings into a KDF,
given that they all seem to operate, quite sensibly, on bytes.  It's
not at all unambiguous how to pass numbers to a KDF, on the other hand
-- are they big-endian zero-padded?  are they big-endian
variable-length with MSB zeros stripped?  maybe there's a length
prefix?  maybe that prefix is ASN.1?  if so, how is it encoded?)

--Andy

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 27 Jan 2015 09:30:44 -0800 (PST)

> internals are opaque, but users do not need to generate their own

  Yes, it's opaque to you, the application writer. That's the point! But
to have curve25519 as a special case then you'd have to pry into the
opacity of the code and figure out what's going on.

  So to allow Nathan McCullum to send you a chunk of code that
should work with any curve supported by OpenSSL, and have it just
work without you knowing any opaque internals, it requires a
canonical conversion of bitstring to integer to field element and
back.

  If, as you say, users do not need to generate their own points then
they're gonna have to have a registry of M and N for all curves. And
to import a bitstring (for instance from the appendix of your draft)
into code requires converting that bitstring into an element. And
without the canonical conversion then you need to know about the
opaque internals.

  Thank you for illustrating my point so well!

  Dan.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 27 Jan 2015 17:42:35 +0000

Hi Dan,

> handle curve25519. Special cases will be a continued source of trouble.

TBH I think that's a tad overstated.

The main thing that seems to be getting lost here is that big
endian vs. little endian is not a big deal. Either works and
there is little or nothing at stake worth fighting over. I've
expressed my slight preference for LE and it's fine that others
disagree - I'm sure the chairs and/or editors can write text
one way or another and it'll get fixed one way or another
before we're done as folks write code and see that it is better
or worse one way or the other. In the worst possible case,
a very late switch within CFRG from one to the other would
add a line of code and an cranky comment - so long as we get
that done before people deploy stuff widely. (And the stuff
that matters here are specific long term key values and not
code so much. If you think back to the DKIM signature format
changes the same arguments apply and so for ephemeral DH uses
this is something that stays malleable for a while yet.)

Moving on without considering this as a hill to die on and
getting to a decision before deployment but not necessarily
in the next nanosecond seems to me much more important than
which of LE vs BE is chosen.

S.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 27 Jan 2015 17:49:15 -0800

> without the canonical conversion then you need to know about the

What makes you think I wouldn't write the point appropriately? More
importantly, if this encoding was different for each curve, how would I
notice, except when I generate the table? Every point has a representation
either way.

I can always do the calculation in PARI and reverse and pad the result. In
fact, PARI only uses decimal IO so I have to convert anyway. I'm not
insisting on decimal format to make my tools work.

There is an encoding of x coordinates as 32 byte strings. The intent is
that this encoding is used for everything having to do with Curve25519. Why
is this such a large problem? At least with the Weierstrass coordinate on
the wire proposal there was a clear rationale for the change in terms of
compatibility. But this has nothing to do with compatibility: you will need
to write new code anyway.

Of course, it's not the case that there is a single universal key format.
SEC1 serializes bignums as fixed-width in keys and variable width in
signatures. PGP uses a different length encoding from TLS. Nor do all
algorithms on words take the words the same way: MD5 uses a little-endian
length encoding, and encodes the low byte first. SHA1 uses a big-endian
length encoding and big-endian words.

Furthermore, forcing applications to carry out encoding and decoding,
instead of having the library do it has several bad effects. It makes it
more complicated to use Curve25519. It prevents codesharing among
libraries, unless they have identical bignum APIs. It makes applications
non portable across libraries.

Defining Curve25519 as a function of bigintegers was considered and
rejected by multiple people due to interoperability problems historically
caused by lack of canonical byte encodings: TLS DHE uses two distinct
encodings at some point.

What's wrong with the API everyone is already using?

Sincerely,
Watson Ladd

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 27 Jan 2015 20:47:11 -0800 (PST)

> notice, except when I generate the table? Every point has a representation

  You don't understand. It's not that you don't write them appropriately.
It's that you are writing them big endian because you are interpreting the
output of the appropriate hash function as a big endian number.

  Your draft claims "[t]he points are presented in hexidecimal SEC1 format."
If someone wants to implement your draft he or she would have to convert
the bit strings in table 3 into points on the elliptic curve.

  So check out how one converts an octet string into an elliptic curve
point in
SEC1. It's section 2.3.4 and that will take you eventually to section
2.3.8 (octet
string to integer conversion) and that is quite obviously a big endian
conversion.

> to write new code anyway.

 The point is, your draft lists M and N for p256, p384, and p521 and it uses
big endian format exclusively. If one were to try to use curve25519 to
compute M and N it would have to interpret the output of the hash
function differently. So therefore someone who implements your draft
has to know about the special case of curve25519. He has to know not
to do what he'd do for every other curve.

> length encoding and big-endian words.

  No there is, and it's big endian. MD5 and SHA1 are hash algorithms and
their output is a digest, not a number. The important thing to realize
though is that if one were to use MD5 or SHA1 to generate a bit string
in order to convert the digest into a point on an elliptic curve according
to SEC1 (or X9.62 or ISO/IEC 15946 or RFC 6090) that output would be
interpreted as big endian in both instances, the internals of the hash
algorithm notwithstanding.

> non portable across libraries.

  That is exactly my point! Applications shouldn't have to carry out
different encodings and decodings. If curve25519 does not follow the
canonical convention, though, they will.

> What's wrong with the API everyone is already using?

  Exactly, and everybody is using big endian.

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 27 Jan 2015 22:02:31 -0800

>   Exactly, and everybody is using big endian.

You're confusing the job of the person who writes a library that
provides a function called X25519 with the job of the person who
writes an application that uses X25519 to calculate keys, and then
conflating that with the work required to do calculations of points on
the curve in some other application. I'll let slide the fact that
SPAKE2 will not work with X coordinate only arithmetic.

If you look in tweetnacl.c you will see a function crypto_scalarmult
that takes two const char * arguments, and places a result in a third
char *. There is no encoding or decoding anywhere in sight in an
application that uses this function. Clearly, an application calling
this function isn't affected by the endian choice, provided we all
agree. It's clear we can write down X coordinates as arguments to this
function: 64 hex nibbles as 32 bytes in the order we all know and
love: 0f10 is the byte array with first byte 15, second one 16, etc.

Now let's consider the library writer. They potentially have to write
a swap routine, if their prefered bignum library doesn't have a little
endian load. It's likely, as DJB points out, that they have to do some
work to get the padding correct even if we pick big endian.

But what if I want to do a calculation in the field F_p? Well, you can
use SAGE or PARI or your whatever: that format doesn't have anything
to do with the format here. If I'm going to take 32 bytes and
interpret them as a field element, why does it matter which one goes
first vs. which one goes first in the format used by the
crypto_scalarmult function above for purposes of picking random field
elements? And why does the absolute order that I use when doing the
calculation matter between one field and the next, so long as I know
what it is?

So what actually is your argument? It can't be that applications that
link against a library containing crypto_scalarmult_curve25519 have to
deal with an inconsistent API if we switch endianness: they don't. It
can't be that authors of libraries providing that function can't do it
if the endianness is little-endian: they clearly can. And it can't be
that we can't do calculations on the curve itself if we switch
endianness: we can.

Of course, you might as well ask why we don't use big-endian. But the
fact is that switching has costs: at minimum we need to rename the
primitive. All existing implementations of that crypto_scalarmult
function don't work anymore. All existing documentation has to be
carefully checked to ensure that it's dealing with the correct
variant. The old version isn't going away: working groups end up
having to pick one.

Is this the only way to structure the interface between the library
and the application? No. One could instead have the library separate
out the necessary steps of masking the private key, converting x to a
bignum, carrying out the scalar multiplication, and turning the result
back into a sequence of bytes. Now, there actually is something to
complain about if you decide to expose the endianness to the
application developer. But this need is entirely self-inflicted
damage: the API was already terrible by exposing details that didn't
need to be exposed.

(It's also unclear how you manage to do this: A SEC1 encoded point and
a SEC1 signature don't have the same padding. You would have to leave
almost everything about the packing and unpacking to the calling
application unless you had a per-curve encoding and decoding function,
in which case endianness can be hidden inside it.  Why would leaving
this up to the caller be a good idea?)

Sincerely,
Watson Ladd