Subject: [openpgp] Algorithm-specific data: problems with Simple Octet Strings, and possible alternatives

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 24 Mar 2021 20:54:49 -0400

Hi OpenPGP folks--

I spent a good part of today trying to write a patch for including
Simple Octet Strings in the crypto-refresh draft, pursuant to gniibe's
presentation at IETF 110 and his public memo at:

   https://www.gniibe.org/memo/standard/openpgp/ecc-in-openpgp-sos.html

This message doesn't include the patch i wanted to make because I think
i ran into a problem with it.  I'm trying to explain the problem here,
and how my thinking has shifted in the course of trying to write the
thing down.  Please correct me where I've erred.

IIUC, SOS is basically intended as a genericization of MPI; it
represents its length in a two-vector scalar as (8*octet-count) instead
of as (bit-count).  It "fits" where MPI fits, but doesn't require
leading-zero removal, or require interpretation as an integer at all.

The problem comes with the different length representations, in
particular for existing ECC mechanisms.

Because existing ECC points are currently represented with a leading
prefix byte (0x04 for NIST curves, 0x40 for 25519), and that byte has
the leading bit cleared, the MPI version of the length scalar is
*different* on the wire from the SOS version of the length scalar.

As a concrete example, a NIST p256 pubkey looks today like this (using
visualization from "sq packet dump --hex"):

```
Public-Key Packet, old CTB, 2 header bytes + 82 bytes
    Version: 4
    Creation time: 2021-03-24 22:06:14 UTC
    Pk algo: ECDSA public key algorithm
    Pk size: 256 bits
    Fingerprint: D4732B93D4E82D068EE197A63A73ED20925926A6
    KeyID: 3A73ED20925926A6
  
   00000000  98                                                 CTB
   00000001     52                                              length
   00000002        04                                           version
   00000003           60 5b b7 d6                               creation_time
   00000007                       13                            pk_algo
   00000008                           08                        curve_len
   00000009                              2a 86 48 ce 3d 03 01   curve
   00000010  07
   00000011     02 03                                           ecdsa_public_len
   00000013           04 29 75 bb 53  55 49 31 80 ab 03 54 15   ecdsa_public
   00000020  a0 6c 29 10 a8 85 b7 2f  e5 93 81 90 48 08 b8 0e
   00000030  c7 02 55 aa 51 b2 b7 6a  00 7a a1 2b cf 25 a7 e7
   00000040  9c 95 b1 fa 79 87 c2 cb  94 53 a8 da c2 00 58 45
   00000050  79 a0 96 8e
```

but if it was represented in SOS form, we'd see this change:

```text/x-diff
    00000010  07
-   00000011     02 03                                           ecdsa_public_len
+   00000011     02 08                                           ecdsa_public_len
    00000013           04 29 75 bb 53  55 49 31 80 ab 03 54 15   ecdsa_public
```

The result is that the fingerprint would also change (to
C9EAB3BE6B20CAEA568BE93F9BA3D29CBB873842), since the bytestream that
feeds into the fingerprint calculation changes.  This means that we can
represent a single EC public key (with the exact same creation date) in
at least two different ways just by varying whether the public point is
seen as an SOS or an MPI.

(note: this concern is not necessarily just for ECC; it's also relevant
for traditional RSA, DSA, and ElGamal key MPI components that might have
the highest set bit somewhere other than just below an octet boundary.
For example, if we were to "retcon" RSA's e component as an SOS instead
of an MPI, the most common value for e (65537) could change on the wire
from [00 11 01 00 01] to [00 18 11 00 01], resulting in a similar change
to the fingerprint)

This leaves me wondering about the utility of the SOS abstraction.  I
can imagine a few distinct options:

 a) Introduce SOS and apply it to existing ECC pubkeys.  This is what I
    understand to be gniibe's proposal.  It looks like this means an
    implementation will have to cope with multiple distinct wire
    representations and fingerprints of the exact same public key.

 b) Introduce the SOS abstraction, but only use it for *new* pubkey
    algorithms.  All existing ECC (including NIST and 25519) would still
    be this weird pseudo-MPI, representing the count based on the
    highest set bit, not 8*octet-count, and requiring clearing of
    leading zeros.

 c) Introduce a variant of SOS that indicates count based on highest set
    bit (not 8*octet-count) and use that for everything, but without
    requiring removal of leading all-zero octets.

 d) Not introduce the SOS abstraction at all, but instead explicitly say
    that new algorithms can define their own fixed algorithm-specific
    bytestream for public key material, secret key material, and
    signatures -- it does not need to be MPIs (gniibe's memo calls this
    approach "Each data format definition by each curve").

 e) No SOS abstraction, and just keep on doing the kind of pseudo-MPI
    we've been doing for any new curves (gniibe's memo calls this
    "Practically easiest").

 f) Introduce a new distinct data type that uses an actual octet count
    for each bytestring (gniibe's memo calls this "Non-strange but Just
    an Octet String")

Of these choices, I'm leaning toward (d) but i'd love to hear what other
people think.

(a) Seems problematic because of the multiple acceptable representations
    outlined above.  It's already pretty tricky that the fingerprint of
    a piece of given public key material can vary depending on the
    creation timestamp.  Some implementations might try to normalize an
    SOS into a "compliant" MPI, thereby affecting their ability to
    calculate the correct fingerprint.  I don't think we currently have
    any tests that demonstrate interoperability in the face of this kind
    of confusion.

(b) Seems sort of pointless because it doesn't let us clean up any of
    the existing mess.  If we're going to keep all the existing mess, we
    might as well go with (d).

(c) Introduces a new problem: When encoding an SOS string, how many
    leading zero-octets should be used?  If the answer is
    "implementation gets to decide" then we share the
    multiple-representations problem with (a); And if the answer is
    "each algorithm has a mandated size" then we might as well go with
    (d).  Also, when consuming such a string, an implementation would
    need to first scan through all the leading zero-octets before it
    could use the length count to jump to the next field.  That's a new
    piece of ugliness for OpenPGP parsing.

(e) Bothers me because it means that each new algorithm introduced has
    to declare not only its data formats, but how to transform those
    data formats into the semblance of an OpenPGP "MPI".  This just
    seems like extra work and new ways for both implementers and
    specifiers to get things wrong.

(f) Seems excessive: why declare a standard for encoding lengths of
    fields in those cases where the lengths are pre-determined by the
    algorithm in question (i expect that to be most cases for new
    algorithms).  For specific algorithms which have variable length
    parameters, *those algorithms* can declare how they want to delimit
    the fields.  If the goal is to be able to skip over
    algorithm-specific details of an algorithm that we don't know, what
    are we skipping *to*?  For public key packets and signature packets,
    the only thing that comes next is the end of the packet, whose size
    we already know.  For secret key packets, we *might* try to skip
    from the public key material to the secret key material, but again,
    if we don't know how many MPIs (or SOSes or JOSes) to skip for
    public keys we might not even be able to tell when the s2k usage
    octet starts, so we can't do that today anyway.

I will probably try to draw up a concrete patch for (d) unless other
folks in the WG think it would be useful for consideration.  The patch
will likely ask IANA to add new columns to the "public key algorithm"
registry (e.g. "public key representation", "secret key representation"
and "signature representation") and to formally include an Elliptic
Curves registry with similar columns, so that we have a compact way to
view these distinctions, and a place for new proposals to include
updates.

If any of my analysis above is wrong, please help me understand it
better!

      --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 25 Mar 2021 16:57:07 -0400

>     any tests that demonstrate interoperability in the face of this kind

I've opened this issue in the interop test suite suggesting a way to
test whether implementations might diverge:

https://gitlab.com/sequoia-pgp/openpgp-interoperability-test-suite/-/issues/45

sorry to not offer it with any specific implementation yet.

        --dkg

---

From: Ángel <[email-masked]>
Date: Fri, 26 Mar 2021 03:44:00 +0100

Some thoughts, trying to write down the problem definition (of which I
may be missing something) and throwing out a few ideas, not necessarily
useful.

> ```text/x-diff

Tthe source of this difference is
 04h = 0000 0100b.

Thus, SOS would counts those 5 leading zero bits but MPI doesn't.

Currently a consumer could round the bit length to the next multiple of
8 and use that for jumping n octets, *except* if the encoded number
would begin with the high bit set.
E.g. number 128 is [00 08 00 80] not [00 08 80] (which would a negative
number, could that appear anywhere?)

Spurious leading zeroes (e.g. [00 09 00 00 00 01 FF]) are not allowed
now.

However, in SOS-land, an algorithm may want to use a block of octets
"00 00 00 01 FF". That could be prepended with a length of 40 (SOS
proposal) 09 (MPI bit counting)...

If we restrict ourselves to the modern ECC pubkeys (retconning this to
RSA would be very cool, but probably impossible) it currently uses,
for NIST curves:

 04 || x || y 

which is an UncompressedPointRepresentation (rfc8422#section-5.4.1):
an uncompressed(4) PointConversionForm followed by X & Y opaques.

and for Ed25519/Curve25519 it uses 
 40 || x

I'm thinking that perhaps the SOS could be defined as having *three*
prefix bytes. The upper 13 bits defining the length of the black box,
followed by a 3 bit parameter checksum and an algo parameter not
included in the SOS count. NIST Curves would be defined as X || Y and
receive a PointConversionForm of 4 as parameter.

Similarly for X25519.

That would allow defining the current pseudo-MPIs in a cleaner way
based on an algorithm-specific opaque string as SOS tried to.

Future algorithms could set a parameter such as 0x80 or 0xFF to produce
a nicer count, but considering the first byte as a separate (and
somewhat magic) value outside of the opaque string do allow a better
definition than the current MPI which are really something else, while
making existing implementations fit instead of requiring special casing
("Practically easiest" option).

However, that doesn't work for the signature, where there *is* zero-
removal/zero-recovery.

Best

---

From: NIIBE Yutaka <[email-masked]>
Date: Fri, 26 Mar 2021 15:24:00 +0900

Hello,

> leading-zero removal, or require interpretation as an integer at all.

Sorry, I was not able to describe SOS accurately, in detail.

In the implementation of SOS in GnuPG 2.3-beta, it is mixture of two;
One case is with bit-count and another case is with 8*octet-count.
Former is used when there is no problem of leading-zero removal.  Latter
is used to ensure no removal of leading zeros.

>  a) Introduce SOS and apply it to existing ECC pubkeys.

My (not-so-strong) proposal is to introduce SOS data type, and apply it
for ECC (pubkey or ephemeral key, signature, and secret), so that we can
explicitly require no removal of leading zeros to allow fixed-size data.

Implementations will have to handle new representation with leading
zeros (when interpreted as an MPI).  Actually, many already do when
reading data.

I think that we cannot remove the existing mess from implementations,
when we need to support existing data.

What I pursued was to clarify the mess with possible improvement by the
specification.

The benefit of this approach is:

    Minimum impact to the specification and implementations.

    Compatibility, possibly encouraging better interoperability for
    existing corner-cases (of Ed25519 and ECDH with Curve25519).

    Flexibility, for new curves, no extra definition will be needed.

But, I know that describing existing data of Ed25519 as weird MPI
representation acculately ... would be difficult in a specification.

So, I don't insist much for applying SOS idea in the specification.  For
some implementers, it would work as a technical guidance for
interoperability to interpret existing OpenPGP data with Ed25519.

Well, nevertheless, I believe that it's good to introduce a new distinct
data type (if not SOS) for opaque octet string, if possible.  It will be
useful to be friendly to not-yet-standardized things.
--

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 26 Mar 2021 13:43:27 -0400

Thanks for responding, gniibe--

> is used to ensure no removal of leading zeros.

I think you're saying that GnuPG 2.3-beta will select between these two
choices based on the algorithm in use -- whether that's a first-order
algorithm as selected from the public-key algorithms registry, or a
distinct curve OID within a EdDSA/ECDSA/ECDH pubkey selection.

Is that right?  which choices are made in what cases?

> explicitly require no removal of leading zeros to allow fixed-size data.

If we have fixed-sized data for all three of these elements for a
particular algorithm (which i expect to be the case with new elliptic
curves) then why do we need a prefix length indicator at all?

> zeros (when interpreted as an MPI).

Are you saying that there are certificates, private keys, or signatures
in the wild that provide MPIs for existing, specified algorithms, which
have leading zero bytes, or have the MPI length specified in such a way
that it counts leading zero bits?  If so, which implementations are
producing them?

> Actually, many already do when reading data.

How do they cope with multiple representations and fingerprints of the
same key material?  I've opened
https://gitlab.com/sequoia-pgp/openpgp-interoperability-test-suite/-/issues/45
to try to gather data on how different implementations would cope with
encountering something like this in the wild (but i haven't written any
test yet, i'm hoping other folks will step up and write those tests, but
if you have code that is producing these things already, please point ot
it)

>     existing corner-cases (of Ed25519 and ECDH with Curve25519).

My worry is that we actually get *worse* interoperability with existing
corner cases, if we have two distinct ways to represent exactly the same
public key, and two distinct fingerprints for the same public key
material + date.

>     Flexibility, for new curves, no extra definition will be needed.

But if the octet strings for each new curve are going to use a "native"
format for that curve, then we need a definition per curve anyway.  Why
isn't it easier to just include the size in the curve-specific
definition, and not put it directly on the wire at all?

> representation acculately ... would be difficult in a specification.

I think our current draft actually *underspecifies* a lot of what is
currently expected of an implementation.  I'm hoping we can improve
that, even if it's difficult.

> interoperability to interpret existing OpenPGP data with Ed25519.

i'd love to see some concrete guidance for implementers, and some of
that could be in the spec (even if just in an "implementation guidance"
section).  But I'm worried about the impact of recommending handling of
these variant forms.

> useful to be friendly to not-yet-standardized things.

If we have not-yet-standardized things that ultimately do need a new
abstraction, I agree we should consider a common abstraction.  But if
this abstraction isn't going to work directly for any existing piece,
and if the main new things that we contemplate don't need any
abstraction at all (they can just be well-documented fixed-length
fields), then i'm not convinced that this particular abstraction is
useful.  Why do we need such an abstraction?

        --dkg

---

From: Niibe Yutaka <[email-masked]>
Date: Mon, 29 Mar 2021 16:52:23 +0900

> Sorry, I was not able to describe SOS accurately, in detail.

So, I write this.  It is also available at:
https://www.gniibe.org/memo/standard/openpgp/sos-in-openpgp.html

==========================

SOS is a suggestion to OpenPGP implementations to address the zero
removal/recovery problem.  I know that implementations already handle
it by adding zero recovary for Ed25519.  For new curves, it's good if
we won't need to support zero recovary again.

SOS in practice
===============

Referring the definition of SOS (in the previous article), 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.

The important point here is: There are multiple interpretations of
"the length of the SOS in bits".

This means that canonicalizing SOS representation is not defined by
the SOS handling itself.

Reading SOS representation
--------------------------

When parsing octet sequence in SOS representation, an implementation
expects a two-octet scaler and then an opaque string of octets with
the following length in octets:

    ("the length of the SOS in bits" + 7) / 8

Then, it does **not** check representation in bits.

Thus, when reading, the SOS [00 02 01] is considered formed correctly.
So are [00 08 01], and [00 08 00].

Writing SOS representation
--------------------------

When writing an octet string into SOS representation, an
implementation does following steps:

* 1: Examine the first octet in the octet string.

* 2: NBITS = 8 * length_of_string_in_octets

  * 2-1: If the first octet is zero, then no change of NBITS.

  * 2-2: If it's not zero, examine the bit-representation of it, to
         tweak NBITS = NBITS - number_of_leading_0_bits.

* 3: Output the scalar to represent NBITS, then the octet string.

Note that it does **never** remove anything from an octet string.

Impact to OpenPGP implementations
=================================

If it will be agreed, implementations will have to support non-zero
removal representations in Ed25519 signature and secret.

My conclusion (Manga practice requires conclusion, but I don't insist)
=======================================================================

SOS asks a clarification of Ed25519 signature and secret, and adding
support of non-zero removal to implementations.

In return, it will be easier to add support of new curves in a cleaner
way, with no need to support zero-recovery.

Note that it's not best for new curves, when assigning algo number to
specification is possible.  Use of SOS means that adding a two-octet
scalar to represent an octet string (in each use), which might not be
needed if the length information is determined by the context easily.

Post Script
===========

I don't like zero-removal or any removal by some internal processing.

I remember that for the song `S.O.S`_ (around 1977 in Japan), the intro
of the track was removed during its broadcast.

.. _S.O.S: https://en.wikipedia.org/wiki/S.O.S._(Pink_Lady_song)
--

---

From: Florian Weimer <[email-masked]>
Date: Mon, 29 Mar 2021 10:31:52 +0200

> Impact to OpenPGP implementations

Let me note again that zero-stripping for MPIs affects RSA as well and
makes OpenPGP inconsistent with its normative references.

---

From: Ángel <[email-masked]>
Date: Wed, 31 Mar 2021 01:28:13 +0200

Thanks gniibe, I think this makes it clearer.

Naming it "the length of the SOS in bits" seems a bit confusing, so
perhaps better to refer differently to that.

> This means that canonicalizing SOS representation is not defined by

But you *do* need a canonical representation, as notedd by dkg

Seems easy to solve, though. When you a SOS like [00 02 01] or [00 08
01] specify it must be computed as its canonical representation
(i.e. [00 01 01]). Although I would prefer to just reject them as
malformed.

You would still need to support reading a SOS with zero removal and
without, switching between those depending on the algorithm (eek), but
those would be two different representations, not nine.

This specification of SOS would be backwards compatible to MPI in that
values without leading zeroes would have the same representation in MPI
and SOS, and SOS would support reading a MPI-encoded value.

Main problem seem to be the signatures, where you have multiple
MPI/SOS.
Maybe someone can test how the different implementations in the
interoperability test suite behave when seeing signatures by Alice
without zero removal?
Probably most of them will consider it broken, but explicitly knowing
that is probably be an interesting answer nevertheless.

Best regards

---

From: Wiktor Kwapisiewicz <[email-masked]>
Date: Wed, 31 Mar 2021 09:51:43 +0200

Hi Ángel,

Just a minor note from me reading the MPI section:

> Spurious leading zeroes (e.g. [00 09 00 00 00 01 FF]) are not allowed

If by "now" you mean MPIs then a careful reading of "3.2. 
Multiprecision Integers" [0] reveals that was is forbidden is counting 
leading zeros in length. If the length is properly computed ("starting 
from its most significant non-zero bit") then there is nothing that 
prevents implementations from inserting zero bytes between length and 
the first non-zero byte.

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

Example:

"Thus, the MPI [00 02 01] is not formed correctly.  It should be [00 01 
01]."

But there is no rule that prevents [00 01 00 01] from being valid.

Kind regards,
Wiktor