Subject: [saag] draft-ietf-curdle-pkix and endianess of strings

From: Jeffrey Walton <[email-masked]>
Date: Tue, 18 Dec 2018 14:37:18 -0500

Bernstein's papers detail the byte strings a little endian format.
I.e., the LSB is at byte 0 instead of 31. Cf.,
https://cr.yp.to/ecdh/curve25519-20060209.pdf, Section 2, page 4.

https://tools.ietf.org/html/rfc7748 also uses little endian format for
the strings, but it does not provide details of encodings.

https://tools.ietf.org/html/draft-ietf-curdle-pkix provides
information on encodings but does not discuss endianess of the strings
in the ASN.1 structure.

I believe all other encodings I have seen use big endian formation for
octet strings and bit strings.

Would someone please confirm the strings are written in big endian
format. I.e., an application that uses little endian format for
calculations will have to "byte reverse" to/from ASN.1 encoding.

Thanks in advance.

---

From: Jim Schaad <[email-masked]>
Date: Tue, 18 Dec 2018 12:18:13 -0800

>From the text:

subjectPublicKey contains the byte stream of the public key

It should probably be 'byte string' rather than 'byte stream', but it means
that you take the bytes of the public key and put them there.  There is no
INTEGER ASN.1 type involved anywhere.

Jiim

> -----Original Message-----
> From: saag <[email-masked]> On Behalf Of Jeffrey Walton
> Sent: Tuesday, December 18, 2018 11:37 AM
> To: [email-masked]
> Subject: [saag] draft-ietf-curdle-pkix and endianess of strings
> 
https://cr.yp.to/ecdh/curve25519-
> 20060209.pdf, Section 2, page 4.
> 
> https://tools.ietf.org/html/rfc7748 also uses little endian format for the
strings,
> but it does not provide details of encodings.
> 
> https://tools.ietf.org/html/draft-ietf-curdle-pkix provides information on
> encodings but does not discuss endianess of the strings in the ASN.1
structure.
> I believe all other encodings I have seen use big endian formation for
octet
> strings and bit strings.
> 
> Would someone please confirm the strings are written in big endian format.
> I.e., an application that uses little endian format for calculations will
have to
> "byte reverse" to/from ASN.1 encoding.
> 
> Thanks in advance.
> 
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag

---

From: Jeffrey Walton <[email-masked]>
Date: Tue, 18 Dec 2018 15:28:59 -0500

> INTEGER ASN.1 type involved anywhere.

Thanks.

So this is a new ASN.1 type? a little endian octet string?

Jeff

---

From: Jeffrey Walton <[email-masked]>
Date: Tue, 18 Dec 2018 15:38:20 -0500

> So this is a new ASN.1 type? a little endian octet string?

Thanks again Jim.

Let me rephrase this. Given a 32-byte private key x, we clamp byte 0
with x[0] &= 248.

Where exactly does x[0] show up in the octet string? Is it the first
octet or the last octet?

My apologies for my confusion.

Jeff

---

From: Jim Schaad <[email-masked]>
Date: Tue, 18 Dec 2018 12:52:47 -0800

Octet string do not have an endian-ness.  Integers do but octet strings are just a sequence of bytes.

Jim

> From: Jeffrey Walton <[email-masked]>
> Sent: Tuesday, December 18, 2018 12:29 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [saag] draft-ietf-curdle-pkix and endianess of strings
> 
> > It should probably be 'byte string' rather than 'byte stream', but it
> > means that you take the bytes of the public key and put them there.
> > There is no INTEGER ASN.1 type involved anywhere.
> 
> Thanks.
>

---

From: Jim Schaad <[email-masked]>
Date: Tue, 18 Dec 2018 12:55:18 -0800

> Sent: Tuesday, December 18, 2018 12:38 PM
> > > It should probably be 'byte string' rather than 'byte stream', but
> > > it means that you take the bytes of the public key and put them
> > > there.  There is no INTEGER ASN.1 type involved anywhere.
> >
> > Thanks.
> >
> Let me rephrase this. Given a 32-byte private key x, we clamp byte 0 with x[0]
> &= 248.
> 
> Where exactly does x[0] show up in the octet string? Is it the first octet or the
> last octet?

This is a 32-byte octet string (byte string).  The value is encoded w/o any changes byte strings do not have any endianness.

x[0] is the first byte in the octet string.

---

From: Jeffrey Walton <[email-masked]>
Date: Tue, 18 Dec 2018 16:32:46 -0500

On Tue, Dec 18, 2018 at 3:55 PM Jim Schaad <[email-masked]> wrote:
> ...

Thanks for clearing that up.

You might consider adding a note that the byte array is written to the
octet string with the LSB in the first position, and the MSB in the
last position. As far as I know this draft is the only one that
reverses the byte ordering for presentation. It will avoid confusion
for future readers who expect network byte ordering in ASN.1
presentations.

Bernstein calls it little-endian when describing the algorithm. And to
be clear, here is Bernstein's description of the sequence of bytes
(section 2, page 4):

<quote>
The set of bytes is, by definition, {0,1, ..., 255}. The encoding of a
byte as a sequence of bits is not relevant to this document. Write s
|-> s-bar for the standard little-endian bijection {0,1, ..., 2^256-1}
to the set {0,1, ..., 255}^32 of 32-byte strings: in other words, for
each integer s in {0,1, ..., 2^256-1}, define s-bar = (s mod 256,
floor(s/256) mod 256, ..., floor(s/256^31) mod 256).
</quote>

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 19 Dec 2018 02:54:41 +0000

Jeffrey Walton <[email-masked]> writes:

>octet string with the LSB in the first position, and the MSB in the last 
>position. As far as I know this draft is the only one that reverses the 
>byte ordering for presentation. It will avoid confusion for future readers 
>who expect network byte ordering in ASN.1 presentations.

This was requested when the RFCs were written (alongside using the standard
X9.62 form that everything else uses), but nothing got done.  Basically the
encoding used for the Bernstein curves is the reverse to the way everything
else does it.  So you take the standard form used by all other curves, then
encode the values backwards.  In my code I use a shim layer that reverses
the bytes, at which point they can be handled by code that expects them in
the standard form.

Peter.

---

From: Jeffrey Walton <[email-masked]>
Date: Wed, 19 Dec 2018 16:13:29 -0500

> the bytes, at which point they can be handled by code that expects them in

Yeah, using the little endian presentation brings up some weird use
cases. Suppose a named curve is not used (i, e., curve25519 parameters
are specified). The other domain parameters like prime and subgroup
order are big endian but the keys are little endian.

I'm fairly certain the best course of action is to make this use case
work as expected:

$ dumpasn1 ed25519.bin
  0  52: SEQUENCE {
  2   1:   INTEGER 0
           ...
 33  32:   OCTET STRING
       :     6D C5 9D 3F 09 7F B2 3D 44 BA 90 79 12 81 B4 53
       :     25 8D 69 1A 55 AF 5C E4 F1 EE 71 2F DF 91 AE 98
       :   }

And then something like this with Botan (or pick your favorite library):

   uint8_t sb[32] = {0x6D, 0xC5, ... 0xAE, 0x98};
   BigInt sk(sb, 32);

The extra "byte reverse" needed to make things work as expected is
non-intuitive and not documented. But maybe I am missing something or
I don't understand the motivation.

Jeff

---

From: Russ Housley <[email-masked]>
Date: Wed, 19 Dec 2018 17:03:30 -0500

This discussion probably belongs on the CURDLE WG mail list ...

Note that draft-ietf-curdle-pkix has been published as RFC 8410.

When this object identifier is used:

   id-Ed25519   OBJECT IDENTIFIER ::= { 1 3 101 112 }

the algorithm parameters are absent, so there is no opportunity to define the curve through parameters.

The RFC warns:

   Both [RFC7748] and [RFC8032] define the public key value as being a
   byte string.  It should be noted that the public key is computed
   differently for each of these documents; thus, the same private key
   will not produce the same public key.

The RFC could have also warned about the big-endian vs. little-endian encoding used in different RFCs related to elliptic curve.

Russ

> On Dec 19, 2018, at 4:13 PM, Jeffrey Walton <[email-masked]> wrote:
>

---

From: David Benjamin <[email-masked]>
Date: Wed, 19 Dec 2018 17:03:19 -0600

(Is the concern that RFC 7748 and RFC 8032 differ in endianness or that the
pair of them differ in endianness from X9.42-style EC? I'm assuming it's
the latter, because the former is not the case. RFC 7748 and RFC 8032 both
specify little-endian. They're different for other reasons.)

No objections to clarifying, but RFC 8032 (correctly) specifies Ed25519 and
X25519 algorithms as functions on byte strings and RFC 8410 (correctly)
defers to that. So probably a better question is whether RFC 8032 is clear
enough on the internal serialization.

I think the best architecture here is for byte string serialization to be
handled by your Ed25519 and X25519 implementations internally, so the ASN.1
layer doesn't need to care. (Endianness is far from the biggest distinction
between X9.42-style EC and X25519/Ed25519. They use different curve
equation shapes altogether.)

As an analogy, if you look at SHA-256's internals, a SHA-256 hash isn't 32
bytes, but eight 32-bit integers. But this is not a useful public
interface, so SHA-256 comes with a particular byte encoding of those eight
integers. It could have been big-endian, little-endian, or middle-endian
and nothing outside of low-level SHA-256 implementations would have known.

It is unfortunate that ECDSA got this wrong and saddled us with a mess of
different serializations, wasting time and complexity. RFCs 8032 and 8410
happily did not repeat this mistake, and we should keep this up.

To that end, the quoted text talks about using curve parameters explicitly
rather than a non-named curve. RFC 8410 doesn't specify such a thing. I
would have made a lot of noise if it had. :-) Which encoding is this
referring to?

David

On Wed, Dec 19, 2018 at 4:03 PM Russ Housley <[email-masked]> wrote:

> The RFC could have also warned about the big-endian vs. little-endian
> encoding used in different RFCs related to elliptic curve.
>
> Russ
>
>
> last
> Curdle mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/curdle
>
>

---

From: Jeffrey Walton <[email-masked]>
Date: Wed, 19 Dec 2018 18:34:23 -0500

> Note that draft-ietf-curdle-pkix has been published as RFC 8410.

Thanks Russ.

Off-topic, my Google search for curve OIDs and encodings lead me to
draft-ietf-curdle-pkix . I plugged in
https://tools.ietf.org/id/draft-ietf-curdle-pkix.txt and got version
10 of the document.

The document does not state there is an RFC available. Here's the
relevant preamble:

Network Working Group                                       S. Josefsson
Internet-Draft                                                    SJD AB
Intended status: Standards Track                               J. Schaad
Expires: November 9, 2018                                 August Cellars
                                                             May 8, 2018

>From an outsider's view, all we know is the IETF is working on it. The
doc has expired but it is the latest available.

When NIST supersedes a document they serve pages like...

FIPS 186-3 search:
* https://csrc.nist.gov/publications/detail/fips/186/3/archive/2009-06-25

SP800-53A Rev 1 search:
* https://csrc.nist.gov/publications/detail/sp/800-53a/rev-1/archive/2010-06-29

NIST makes it harder to use the wrong document for the typical use case.

Jeff

---

From: Jeffrey Walton <[email-masked]>
Date: Wed, 19 Dec 2018 19:37:28 -0500

On Wed, Dec 19, 2018 at 6:03 PM David Benjamin <[email-masked]> wrote:
> ...
> To that end, the quoted text talks about using curve parameters explicitly rather than a non-named curve. RFC 8410 doesn't specify such a thing. I would have made a lot of noise if it had. :-) Which encoding is this referring to?

Thanks David.

I have this test program handy for interop testing. I believe it is
using the EC key format from RFC 5480. This is what everyone has been
using in the void before the latest IETF deliverables.

In the program below the OID is new, but previous to getting Thawte's
OID we used GNU's old OID for curve25519. In between new (Thawte) and
old (GNU) we could use the OID's draft-josefsson-pkix-newcurves. Many
folks have to support 8 or 10 OIDs for the curves.

EC domain parameters (instead of a named curve) was going to be my
next test case to ensure we interop or work as expected.

I guess the point is, just because the latest RFC does not specify it,
it does not mean it is not going to happen. In fact, it has been
happening for years now because of the information void. RFC 5480
(with a mashup of OIDs) was enough to keep us going.

Jeff

$ cat x25519.c
#include <openssl/evp.h>
#include <openssl/pem.h>

int main (int argc, char* argv)
{
    EVP_PKEY *pkey = NULL;
    EVP_PKEY_CTX *pctx = EVP_PKEY_CTX_new_id(EVP_PKEY_X25519, NULL);
    EVP_PKEY_keygen_init(pctx);
    EVP_PKEY_keygen(pctx, &pkey);
    EVP_PKEY_CTX_free(pctx);
    PEM_write_PrivateKey(stdout, pkey, NULL, NULL, 0, NULL, NULL);
    return 0;
}

And then compile it. In the example below, OpenSSL was configured with
--prefix=/opt/openssl-1.1.1.

$ gcc -I /opt/openssl-1.1.1/include/ -L /opt/openssl-1.1.1/lib
x25519.c -o x25519.exe -l:libcrypto.a -lpthread -ldl$

And finally:

$ ./x25519.exe
-----BEGIN PRIVATE KEY-----
MC4CAQAwBQYDK2VuBCIEIMBio4/nGHPiJzCUDifuMl7zg6Me2XlI5jAKCyPRlW5R
-----END PRIVATE KEY-----

$ echo MC4CAQAwBQYDK2VuBCIEIMBio4/nGHPiJzCUDifuMl7zg6Me2XlI5jAKCyPRlW5R
| base64 -d > x25519.bin

$ dumpasn1 x25519.bin
  0  46: SEQUENCE {
  2   1:   INTEGER 0
  5   5:   SEQUENCE {
  7   3:     OBJECT IDENTIFIER curveX25519 (1 3 101 110)
       :     }
 12  34:   OCTET STRING, encapsulates {
 14  32:     OCTET STRING
       :       C0 62 A3 8F E7 18 73 E2 27 30 94 0E 27 EE 32 5E
       :       F3 83 A3 1E D9 79 48 E6 30 0A 0B 23 D1 95 6E 51
       :     }
       :   }

0 warnings, 0 errors.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 20 Dec 2018 11:59:37 +0000

Jeffrey Walton <[email-masked]> writes:

>The extra "byte reverse" needed to make things work as expected is non-
>intuitive and not documented. But maybe I am missing something or I don't
>understand the motivation.

One fix, adopted by a significant user overseas, is to retry a failed
signature verification with the bytes reversed.  They'd apparently used some
Ed25519 implementation with a Java library that emitted the standard (big-
endian) representation for the signature, and it wasn't until other
implementations tried to interop that they found the two sides couldn't verify
each other's signatures.  So the adopted solution was to verify with whatever
they read, and if they got a failed verification, reverse the bytes and try
again.

Perhaps someone should do an RFC warning implementers about the booby-trap
built into the IETF specs that use 25519, and how to work around it, e.g. by
retrying failed signature verifications with the bytes reversed.

Peter.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 22 Dec 2018 21:02:54 -0500

> the bytes, at which point they can be handled by code that expects them in

Can we drop this nonsense? The point is that Bernstein specified a
function from a sequence of 32 bytes cross a sequence of 32 bytes to
32 bytes. And we apply this function to the bytes, which are what goes
in the format defined in the draft. Why is this so hard to understand
or apparently to implement? There are even test vectors!

What is the endianness of bytes that contain the bits emerging from a
Huffman encoder?

--
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 23 Dec 2018 02:28:47 +0000

> X9.62 form that everything else uses), but nothing got done.

That's not quite accurate. The issue was brought up and discussed, and the CFRG decided to not do this.

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 28 Dec 2018 02:58:45 +0000

Watson Ladd <[email-masked]> writes:

>The point is that Bernstein specified a function from a sequence of 32 bytes
>cross a sequence of 32 bytes to 32 bytes. And we apply this function to the
>bytes, which are what goes in the format defined in the draft. 

So does ECDSA, and presumably every other ECC.  The difference is that all of
them except the Bernstein ones use a standardised encoding that's been around
for 20-odd years.  The Bernstein ones encode the same values backwards to what
the near-universal usage has been.

>Why is this so hard to understand or apparently to implement? 

It's not hard to understand, the problem is that you now need to implement a
special-snowflake version of every function and mechanism that uses the
Bernstein curves with their backwards encoding of the parameters.  So
everywhere where you formerly had:

  read ECC parameters;
  use ECC parameters;

you now need to have:

  if( special-snowflake-curve )
    reverse data in parameters;
  read ECC parameters;
  use ECC parameters;

And, as a previous poster pointed out, you need even more special-snowflake
handling when some parts of the ECC values are in standard form and other
parts are backwards (big- vs. little-endian).

Peter.