Subject: Re: [openpgp] ECC point encoding and "flag byte"

From: Werner Koch <[email-masked]>
Date: Mon, 01 Mar 2021 09:58:32 +0100

Hi,

In "EdDSA problem and possible change about ECC" from 2019-10-29
([email-masked]) Gniibe already addressed this
problem and suggested the introduction of a new data type (dubbed SOS
for Simple Octet String) to be used for new curves.  He also provided
an initial draft for this change.

Long term implementers of PGP know about the troubles with the MPI
rules.  With the new curve(s) we have an opportunity to fix this issue.
But of course backward compatibility to RFC-6637 is required; which is
actually not too hard.

Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: NIIBE Yutaka <[email-masked]>
Date: Wed, 03 Mar 2021 12:26:52 +0900

Hello,

I tried to modify/fix the specification, but I realized that I don't
have enough skills writing (a part of) specification.

So, instead of the modifying the specification, I wrote a bug report.

Here it is (in ReST format, an initial version).

It is also available at:
https://www.gniibe.org/log/bugreport/openpgp/ecc-in-openpgp.html
(possibly, more update in future)

Your comments will be appreciated. 

--------------------------
=================================
ECC in OpenPGP (as of March 2021)
=================================

In this bug report, I describe how we can improve OpenPGP specification
for ECC, so that different implementations can inter-operate well, and
an implementation can avoid a bug.

Firstly, I point out the single issue: **Opaque Data Element should be
available in OpenPGP**.  I name it **Strange Octet String (SOS)**.

Secondly, I explain about where we should use SOS to represent ECC
things in OpenPGP.

Thirdly, I describe how ECC things were defined in OpenPGP.  And I
explain how these were implemented in GnuPG for classic ECC, then
modern ECC (Ed25519 and Curve25519).

Fourthly, I describe my bug in GnuPG 2.3-beta regarding Ed25519 key
and signature, which I'm fixing now.

Fifthly, I explain about the implementation of handling Ed448
signature and X448 encryption in GnuPG 2.3-beta, with SOS.

Lastly, I conclude that SOS may be the best apporach for OpenPGP.

1: Opaque Data Element should be available in OpenPGP
=====================================================

RFC 4880 and RFC 6637 were good, when it was common to represent data
in big-endian format.

These days, in modern ECC, things are defined in little-endian format.

In this situation, it's good to have a data element which can
represent **something in native format** (or anything, hopefully).

Don't repeat, just refer
------------------------

It's good for a specification to be able to simply **refer** another
specification when it uses technology of latter.

When we repeat some definitions in a specification from another
specification, something wrong may happen.  It's good when we can
avoid this.

Strange Octet String (SOS)
--------------------------

Here, I propose an opaque data element in OpenPGP, named Strange Octet
String (SOS).

I had tried introducing straight-forward Octet String to OpenPGP
(length in octets plus an opaque string), but for backward
compatibility, I concluded that "strange" one is better, instead.

It is defined as:

    An SOS consists of two pieces: a two-octet scalar that is the length
    of the SOS in bits followed by an opaque string of octets.

Most important point is that no semantics is given for the data
element, but it is up to underlying crypto algorithm.  (-: down to?)

Another point is that it has exactly the same structure of MPI, thus,
every MPI can be handled as an SOS.

When an SOS data object is handled as an MPI, it would look "strange"
as it may include preceding zeros, which is not allowed in well-formed
MPI.

2: Let us use SOS for ECC things
================================

I'd like to propose using SOS for ECC things.  We can use SOS for
following data.

* EdDSA Signature

  - R: to represent an EC point, use SOS
  - S: to represent integer, use SOS

* EdDSA Public Key

  - For an EC point, use SOS

* ECDH Public Key with modern Curves

  - For an an EC point, use SOS

* EdDSA Secret Key

  - Just use SOS

* ECDH Secret Key with modern Curves

  - Just use SOS

* ECDH Ephemeral Public Key with modern Curves

  - For an an EC point, use SOS

(If needed,) existing definitions for ECC can replace MPI to SOS.

3: ECC in RFC 6637, Ed25519 and Curve25519 in OpenPGP
=====================================================

You'd say, it's a mess.  But that's how it's evolved.

Classic ECC with MPI
--------------------

In RFC 6637, it is defined using MPI as:

::

   9. Encoding of Public and Private Keys
   [...]
      Algorithm-Specific Fields for ECDSA keys:
   [...]
         o  MPI of an EC point representing a public key
   [...]
        Algorithm-Specific Fields for ECDH keys:
   [...]
            -  MPI of an EC point representing a public key
   [...]
        Algorithm-Specific Fields for ECDH or ECDSA secret keys:
   [...]
         o  an MPI of an integer representing the secret key, which is a
            scalar of the public EC point
   [...]
   10.  Message Encoding with Public Keys
   [...]
      Algorithm-Specific Fields for ECDH:
   [...]
         o an MPI of an EC point representing an ephemeral public key

And ECDSA signature is effectively defined using MPI as:

::

      Algorithm-Specific Fields for ECDSA signatures:

        - MPI of ECDSA value r.

        - MPI of ECDSA value s.

Ed25519 data format
-------------------

If I described current format for Ed25519...

Keys are something like this:

::

   9. Encoding of Public and Private Keys
   [...]
      Algorithm-Specific Fields for EdDSA keys:
   [...]
         o  MPI of an EC point representing a public key with prefix 0x40
            so that we can avoid removing preceding zeros.
   [...]
        Algorithm-Specific Fields for EdDSA secret keys:
   [...]
         o  an MPI of an integer representing the secret key,
            in little-endian format, removing preceding zeros to be
            well-formed MPI.

Signature are something like this:

::

      Algorithm-Specific Fields for ECDSA signatures:

        - MPI of R of EdDSA, whcih represents an EC point without
          prefix 0x40, removing preceding zeros to make it well-formed
          MPI.

        - MPI of EdDSA value s, an integer in little endian format,
          removing preceding zeros to be well-formed MPI.

Please note that we don't put 0x40 to represent an EC point in R part
of signature.  Please also note that we have to remove preceding zeros
to form well-formed MPI for secret keys (non-encrypted), R and S part
of signature.

Curve25519 data format
----------------------

If I described current format for Curve25519, it's something like this:

::

   9. Encoding of Public and Private Keys
   [...]
        Algorithm-Specific Fields for ECDH keys:
   [...]
            -  MPI of an EC point representing a public key with prefix 0x40
               so that we can avoid removing preceding zeros.
   [...]
        Algorithm-Specific Fields for ECDH secret keys:
   [...]
         o  an MPI of an integer representing the secret key, which is a
            scalar of the public EC point (!!big-endian integer!!)
   [...]
   10.  Message Encoding with Public Keys
   [...]
      Algorithm-Specific Fields for ECDH:
   [...]
         o an MPI of an EC point representing an ephemeral public key
           with prefix 0x40 so that we can avoid removing preceding zeros.

It's a mixture of little-endian and big-endian, unfortunately.

4: Ed25519 interoperability issue in GnuPG 2.3-beta (currently being fixed)
===========================================================================

In GnuPG 2.3-beta, it is handled as SOS, so, we have an issue for Ed25519.

See:

- Key: https://dev.gnupg.org/T5120

- Signature: https://dev.gnupg.org/T5331

5: Ed448 and X448 in GnuPG 2.3-beta, using SOS
==============================================

Keys and signatures are simply defined using SOS, there are no prefix,
no removal or recovery of zeros.

As described above, it would look a bit strange as an OpenPGP data, if
you interpret it as an MPI (it may include preceding zeros), but it's
a way simple.

Conclusion
==========

For new things, like Ed448 and X448, it's better to use SOS.

Lastly, let me make an excuse.  Curve25519 in GnuPG was implemented in
that way, the intention at that time was to align to RFC 6637 and
existing implementation (X25519 specification was not yet available).
--

---

From: NIIBE Yutaka <[email-masked]>
Date: Wed, 03 Mar 2021 17:02:15 +0900

> 4: Ed25519 interoperability issue in GnuPG 2.3-beta (currently being fixed)

Here are two example files which were produced by GnuPG 2.3-beta.
Those include Ed25519 signatures.

0110.asc includes signature with S part having zero at the start.
0354.asc includes signature with R part having zero at the start.

Here are dumps of these files:

========= 0110.asc ==========
# off=0 ctb=88 tag=2 hlen=2 plen=117
:signature packet: algo 22, keyid E267B052364F028D
	version 4, created 1614755507, md5len 0, sigclass 0x01
	digest algo 10, begin of digest 4f 78
	hashed subpkt 33 len 21 (issuer fpr v4 249CB3771750745D5CDD323CE267B052364F028D)
	hashed subpkt 2 len 4 (sig created 2021-03-03)
	subpkt 16 len 8 (issuer key ID E267B052364F028D)
	data: ADEE890B755C3B52D46FB0105097F23B5905B472C626222ACB4E441D8EB40001
	data: 007119FF80C34DA152BDB07E1EF5D968CB9F2773002A0CF57911670BE248CF06

========= 0354.asc ==========
# off=0 ctb=88 tag=2 hlen=2 plen=117
:signature packet: algo 22, keyid E267B052364F028D
	version 4, created 1614755520, md5len 0, sigclass 0x01
	digest algo 10, begin of digest 28 19
	hashed subpkt 33 len 21 (issuer fpr v4 249CB3771750745D5CDD323CE267B052364F028D)
	hashed subpkt 2 len 4 (sig created 2021-03-03)
	subpkt 16 len 8 (issuer key ID E267B052364F028D)
	data: 001DB3839E3FD8D4CB81357EE5E42F4AF652C252A03A0FB21768621B1025C08C
	data: AF5A0910EF1D4D6BDD07EA0AA6D69049CB7BA7ED42427E14B8B72CF2C2231704

I wonder if other implementations can handle these files correctly.

Specifically, it is malformed MPI in terms of current OpenPGP
specification.
--

---

From: Wiktor Kwapisiewicz <[email-masked]>
Date: Wed, 3 Mar 2021 10:19:07 +0100

Hi Niibe,

Thanks for working on that! Having recently read the MPI section there 
are definitely some things that could be improved.

But I want to comment on one particular thing:

> as it may include preceding zeros, which is not allowed in well-formed

Actually from my reading of section 3.2 [0] preceding zeros are not 
explicitly disallowed in the spec. It's just the preceding zeros should 
not count towards MPI length:

>    The length field of an MPI describes the length starting from its
>    most significant non-zero bit.  Thus, the MPI [00 02 01] is not
>    formed correctly.  It should be [00 01 01].

[0]: https://tools.ietf.org/html/rfc4880#section-3.2

It doesn't say that [00 01 00 01] is invalid, just that the length 
should not include leading zeros: [00 02 01].

(Unless I'm reading something wrong: please correct me if that's the fact).

For the record I thought that the "byte length" (not MPI bit length) 
would be more appropriate because for all purposes the emitted stream 
will always contain full bytes anyway but I do understand you want to 
keep the backwards compatibility. Even though maybe new curves can use 
this new byte-length SOS.

Calculating bits correctly seems to be more complex than necessary with 
potential for confusion: I've reported it to GnuPG [1] and Sequoia [2].

[1]: https://lists.gnupg.org/pipermail/gnupg-devel/2021-March/034735.html

[2]: https://gitlab.com/sequoia-pgp/sequoia/-/issues/682

Kind regards,
Wiktor

---

From: Florian Weimer <[email-masked]>
Date: Wed, 03 Mar 2021 23:29:22 +0100

> [2]: https://gitlab.com/sequoia-pgp/sequoia/-/issues/682

This isn't really specific to ECC.  RSA has a similar issue.  I've
asked about this before, but it seems the message got lost at the
time.

From: Florian Weimer <[email-masked]>
To: [email-masked]
Subject: Implementations do not seem to use RFC 3447 PKCS#1 encoding
Date: Thu, 02 Apr 2020 22:56:26 +0200
Message-ID: <[email-masked]>

It seems that some implementations drop leading zeros from MPIs,
violating the octet string length requirements in RFC 3447, which are
also repeated in section 13.1 of RFC 4880.

This is likely the result of a rule in section 3.2 of RFC 4880 that
leading zeros in MPIs should not be encoded.

It's not possible to follow both rules at the same time.

Has this come up before?

---

From: Ángel <[email-masked]>
Date: Wed, 03 Mar 2021 23:38:41 +0100

> 1: Opaque Data Element should be available in OpenPGP

No, you can't. Or rather, I expect it is an issue of terminology :-)
Written that way, it seems that you refer to the data being in the
system native *endianness*. Which you can't do, since it must be 
possible to create a key on a big endian machine and use it (both the
public and the private one) on a little endian endian machine, or vice
versa.
On the other hand, if you mean an opaque blob private to the algorithm,
that's perfectly fine (and what's already there, I think) *but* you
need to define it anyway, it doesn't matter if it's in the OpenPGP spec
or in a specification for X curve which defines a wire format. So I
don't think you can escape from it, really :-/

Regards

---

From: Werner Koch <[email-masked]>
Date: Thu, 04 Mar 2021 09:08:48 +0100

> No, you can't. Or rather, I expect it is an issue of terminology :-)

He meant in the algorithm/protocol/curve native format.  In fact we
already use the term "Native point format of the curve follows" in the
ECC pojnt compression flag bytes.

> need to define it anyway, it doesn't matter if it's in the OpenPGP spec

The algorithm/protocol/curve already defines this.

Shalom-Salam,

   Werner

---

From: Ángel <[email-masked]>
Date: Fri, 05 Mar 2021 01:14:11 +0100

On 2021-03-04 at 09:08 +0100, Werner Koch wrote:
> already use the term "Native point format of the curve follows" in
> the ECC point compression flag bytes.
> 

Thanks Werner. I kinda expected that Niibe meant something like that.
But it needs to be stated more clearly.

I think the text should be something like this:

> Algorithm-Specific Part for ECDSA Keys
> The public key is this series of values:
> 
> 
> a variable-length field containing a curve OID, formatted as follows:
> 
> 	a one-octet size of the following field; values 0 and 0xFF are
> reserved for future extensions,
> 
> 	the octets representing a curve OID, defined in {{ecc-curve-oid}};
> 
> a variable length field containing curve-specific octets,
> representing a public key.
> 
> 
> The secret key is this single multiprecision integer:
> 
> a variable length field containing curve-specific octets,
> representing the secret key, which is a scalar of the public EC point.

And then another section like:

#### Curve-specific octets

For Curve25519: a block of 32 bytes which encode a scalar in the way
defined on section 5 of rfc7748.
For Curve448: a block of 56 bytes which encode a scalar in the way
defined on section 5 of rfc7748.

For NIST P-256:
...

(I used the term Curve-specific octets rather than Strange Octet String
in the draft, trying to keep it more obvious, albeit it's probably
still under-specified)

Best regards