Subject: [Openpgp-dt] EC encoding discussion summary -- trying to move forward

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 16 Sep 2021 18:15:07 -0400

Hi folks--

last week we didn't have quorum for the design team meeting -- it was
just Stephen and Daniel Huigens and myself -- but Justus did a bunch of
work on !61 the previous week, and Daniel and I had a long conversation
during the DT call about what seem to be the constraints that folks are
interested in for ECC.

If i can summarize what i think the conversation is leaning toward as
the rough consensus, it's three main points:

 0) we don't want to inject any new algorithm IDs for elliptic curves
    into the OpenPGP spec -- we want to use the already allocated
    codepoints, which means working within the general structure already
    adopted.

 1) As a consequence of this, any EC point is going to be encoded as a
    single MPI -- this makes it easier for implementers to make
    assumptions about the structure of any OpenPGP EC public key or ECDH
    parameter even if they don't know the curve directly.

 2) Given a particular algorithm ID (EdDSA, ECDSA, or ECDH) and a
    particular ECC curve (identified by its OID), any related EC point
    or scalar should have one canonical representation on the wire
    depending on its use.  (that is, a table describing how the "MPIs"
    are formed can be used to look up the representation by curve and
    element, like: "how does curve25519 represent a secret key?")

I think there's a fourth point that follows from here, but i'm not sure
we have as strong a consensus on it:

 3) Modifying how any MPI *can* look on the wire seems likely to
    introduce uncertainty in all of the other places where any MPI might
    show up in OpenPGP.  For example, introducing an MPI where the
    "count" bytes include leading zero bits (aiui what the "SOS"
    proposal from gniibe proposes) means that there are now multiple
    distinct wire representations for the same underlying integer in
    some places.  This could have a range of other consequences if
    implementations permit it elsewhere, like interop failures where
    some implementations consider a signature valid, but others do not.
    I don't know of anyone who has tried to enumerate all the possible
    consequences of allowing variant forms of an MPI in all the places
    where MPIs can be used in OpenPGP.

    Even where a scalar is needed in EC (e.g. in signatures, or as
    secret key material), it should be represented on the wire as an
    MPI. "normal" scalars can of course be represented in usual
    big-endian form, but if we really want to stash an fixed-size octet
    string where a "scalar" typically appears -- one that might have
    leading zeros -- we can avoid a malformed MPI by using a prefix
    octet, an approach that Justus labeled "Wrapped Bit Strings".

So if we can agree that we want to hold all these wire format choices
invariant, the result is that we just need to specify how to form the
data in the "MPI" itself (for EC points, or for the different scalars
used in ECC) for each place where the "MPI" shows up.

This suggests that my earlier attempt in MR 61 at making tables to
describe algorithm-specific parts was overly flexible -- it didn't take
into account the regular structure of one OID and one MPI for an EC
pubkey, for example, and seemed to imply that some curves might use
something different.  And that my attempted definition of "SBS" was
maybe too specific -- a definition that we might not need at all.

Justus's work on !61 seems better than what i'd done, but i think it
also retains some of my mistakes from earlier.

In particular, if we assume that all the elements are MPI formatted, then
the "ECC Curve wire formats" table could just describe what goes inside
each MPI, omitting any mention of SBS or WBS or whatever.

for example, the "EC Point Format" column could just refer to the Name
column of the "ECC Point Representations" table, which wouldn't need to
reference WBS at all.

We could make a comparable "Scalar Representations" table describing how
scalars are packed/unpacked into an MPI, with the following
descriptions:

  standard:    typical OpenPGP big-endian integer

  native(N):   algorithm-native byte string, needs to be left-padded back
               to N octets from compact wire representation

  prefix(X):   algorithm-native byte string, prefixed on the wire with
               non-zero octet X

(if we want to mirror the "ECC Point Representations" table, we could
have each of these described in a subsection below the table and include
a "References" column pointing to the appropriate subsection)

Then the "Secret Key Format" and "Signature" columns in the "ECC Curve
wire formats" table could refer to these entries.

For example, ed25519's secret key format would be "native(32)", meaning
that an implementer who finds a secret key with less than 32 octets
should left-pad with zeros up to 32 octets.  And curve25519's secret key
format would be "standard", meaning that implementers relying on a
cryptographic library that uses the "native" representation would need
to know how to byteswap and zero-pad appropriately.

Does this sound reasonable to folks?  I think it represents the same
state of play as what Justus has described in the current state of !61,
but it relies on and reinforces the invariants listed above, avoiding
some of the distracting flexibility my earlier attempt had injected.

I think we'd do well to try to regularize and merge this tabluar
clarification *without* including ed448/curve448 in the merge request:
once it's in place, i think it'll make it much easier to decide between
different choices for 448, which would be a simple additional MR if the
tables are all in place.

Are there objections to this?  does someone want to try to offer a
patch?

Looking forward to talking with you all tomorrow,

          --dkg

---

From: Daniel Huigens <[email-masked]>
Date: Fri, 17 Sep 2021 13:49:39 +0000

Hi all,

(Sorry for the last minute reply.)

I agree with most of this, except for some of the details -

> to know how to byteswap and zero-pad appropriately.

I think these descriptions would be kind of confusing, since "native"
and "standard" sounds more like you don't have to do anything to encode
them. Personally I'd write something like:

Curve       |  Public Key MPI      |  Private Key MPI
------------|----------------------|-----------------------------------
P-256       |  0x04 || x || y      |  private key
(...)
Curve25519  |  0x40 || public key  |  reverse(private key)

> different choices for 448, which would be a simple additional MR if the

I also agree, however if we don't want to redefine MPIs (which is fair),
then I'm no longer sure that adding curve448 would be as trivial as
adding a row, in case we go with option 5, for example (you might say
that that excludes that option, which is also fair, but I think we
should discuss this on the call).

Just for what it's worth, there is another option, which is to define
all ECC public and private keys as SOSs, but then define the SOSs for
the existing curves in such a way that they're identical to the MPIs as
currently specified. E.g., something like:

Curve       |  Public Key SOS      |  Private Key SOS
------------|----------------------|-----------------------------------
(...)
Curve25519  |  0x40 || public key  |  leftStrip0s(reverse(private key))
Curve448    |  public key          |  private key

Where SOS(data) is defined as:
- If data[0] == 0, then: (two bytes containing length(data) * 8) || data
- Otherwise: MPI(data)

That may actually make it the most obvious what implementations should
do, and particularly what exactly they have to do to undo this encoding.

I'm happy to make a MR with the above, if people agree, or even the
first one first indeed, and then we can always still refactor it for
Curve448 later. (That way it's indeed more clear what Curve448 actually
changes.)

By the way, this is a bit of a separate point, but what OpenPGP refers
to as Curve25519, everyone else refers to as X25519, while Curve25519
generally refers to both Ed25519 and X25519. So I think we should
rename Curve25519 to X25519 in most places in OpenPGP, also in
preparation of X448. But anyway, this can also happen in a separate MR,
if people agree.

Best, Daniel

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 17 Sep 2021 17:43:54 -0400

> preparation of X448. But anyway, this can also happen in a separate MR,

I have no objection to this clarification/alignment with the rest of the
cryptographic world.  It seems like the right thing to do.

I agree that it should happen in a separate MR.

       --dkg

---

From: Paul Wouters <[email-masked]>
Date: Sat, 18 Sep 2021 11:29:00 -0400

> I agree that it should happen in a separate MR.

Agreed.

Paul