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

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:
> 
> On Tue, Dec 18, 2018 at 9:54 PM Peter Gutmann <[email-masked]> wrote:
>> 
>> Jeffrey Walton <[email-masked]> writes:
>> 
>>> 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.
>> 
>> 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.
> 
> 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
> 
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag

---

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