Subject: [Openpgp-dt] Curve448

From: Daniel Huigens <[email-masked]>
Date: Thu, 02 Sep 2021 14:49:58 +0000

Dear Design Team,

I was asked in the last meeting to summarize some of the encoding
options for Curve448. Here they are:

(Let me know if you think I misrepresented any of the options.)

# Option 1: Same as Curve25519

(Public parameters; private parameters):

- EdDSA key: OID, MPI(0x40 || public key); MPI(private key seed)
- EdDSA signature: MPI(r), MPI(s)
- ECDH key: OID, MPI(0x40 || public key), KDF; MPI(reverse(private key))
- ECDH message: MPI(public ephemeral key), one-octet length || symmetric key

As I've said before on the mailing list, this is my personal preference,
as I think it would be strange to introduce Curve25519 and Curve448 in
the same document with a different format (though the last option below
would also avoid that).

# Option 2: MPIs, but non-reversed

- EdDSA key: OID, MPI(0x40 || public key); MPI(private key seed)
- EdDSA signature: MPI(r), MPI(s)
- ECDH key: OID, MPI(0x40 || public key), KDF; MPI(private key)
- ECDH message: MPI(public ephemeral key), one-octet length || symmetric key

This is what Justus proposed, I believe (correct me if I'm wrong).

# Option 3: Native format, same public key algorithm IDs

This option would be to use the native Curve448 formats:

- EdDSA key: OID, 57 octets of public key; 57 octets of private key seed
- EdDSA signature: 57 octets of r, 57 octets of s
- ECDH key: OID, 56 octets of public key, KDF; 56 octets of private key
- ECDH message: 56 octets of public ephemeral key, one-octet length || symmetric key

IMHO, this option is bad(tm), as it breaks compatibility with RFC6637,
in the sense that software may assume that ECDH keys always have an MPI
as the private key, for example.

# Option 4: Native format, new public key algorithm IDs

Same as above, but with new algorithm IDs:

- EdDSA-native key: OID, 57 octets of public key; 57 octets of private key seed
- EdDSA-native signature: 57 octets of r, 57 octets of s
- ECDH-native key: OID, 56 octets of public key, KDF; 56 octets of private key
- ECDH-native message: 56 octets of public ephemeral key, one-octet length || symmetric key

The above is just one possibility; obviously there are other options,
such as defining algorithm IDs that are specific to Curve448, and
dropping the OIDs. However, if we go with this option, I personally
think it would be nice to allow Curve25519 keys in them, and then
deprecate the old algorithm IDs for Curve25519 (though I think this
would also be strange, as officially speaking, this document is the
first place where EdDSA is introduced, for example).

# Option 5: Simple Octet Strings

Simple Octet Strings (SOS) are a proposal by Gniibe to simplify the
handling of leading zeros going forward.

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

- EdDSA key: OID, SOS(public key); SOS(private key seed)
- EdDSA signature: SOS(r), SOS(s)
- ECDH key: OID, SOS(public key), KDF; SOS(private key)
- ECDH message: SOS(public ephemeral key), one-octet length || symmetric key

I believe this is what GnuPG 2.3-beta implemented; correct me if I'm wrong.

# Option 6: Backwards-compatible with Curve25519

- EdDSA key: OID, SOS(0x40 || public key); SOS(private key seed)
- EdDSA signature: SOS(r), SOS(s)
- ECDH key: OID, SOS(0x40 || public key), KDF; SOS(reverse(private key))
- ECDH message: SOS(public ephemeral key), one-octet length || symmetric key

We could use this option also for Curve25519 (existing software written
to handle MPIs would most likely handle SOSs correctly). We could also
use it for Curve448, of course, if we want to be consistent between
Curve448 and Curve25519 (which I personally would be in favor of).

Finally, we could also define the 0x40 prefix as optional, and accept it
for existing (Curve25519) keys, but not generate it for new
(Curve448, and perhaps eventually also Curve25519?) keys. However, that
would raise the question of how to compute the fingerprint (since there
would then be two versions of the same public key, with and without the
prefix), so that would most likely require either computing the
fingerprint based on how the key was encoded on the wire originally, or
storing the key as-is when parsing (with or without prefix).

Hope this helps, and lmk if you think I missed any important options.

Best,
Daniel

---

From: Justus Winter <[email-masked]>
Date: Thu, 02 Sep 2021 17:16:22 +0200

> - EdDSA key: OID, MPI(0x40 || public key); MPI(private key seed)

Private key seed?

> This is what Justus proposed, I believe (correct me if I'm wrong).

Yeah, but having thought about !61, I'd now do:

- EdDSA key: OID, MPI(0x4F || public key); MPI(0x4F || private key)
- EdDSA signature: MPI(r), MPI(s) // wart...
- ECDH key: OID, MPI(0x4F || public key), KDF; MPI(0x4F || private key)
- ECDH message: MPI(0x4F || public ephemeral key), one-octet length || symmetric key

I.e. for every cryptographic artifact (point and scalar, but cannot fix
signature w/o a new EdDSA algorithm identifier), take the octet string
as-is, prefix 0x4F (ASCII 'O' as in octet-string), then MPI encode.

See: https://gitlab.com/openpgp-wg/rfc4880bis/-/merge_requests/61/diffs?commit_id=29e9a3112e961afbea96cf96dccd8b0148d60f29

Cheers,
Justus

---

From: Daniel Huigens <[email-masked]>
Date: Thu, 02 Sep 2021 17:59:31 +0000

> Private key seed?

Certain software (e.g. NaCl) refers to what RFC7748 calls the
"private key" as the "seed", and refers to output of the hashing step
(private scalar + right half of the hash) as the "private key" - see
e.g. [1]. I thought I'd clarify that it refers to the former, also
because [2] seems to imply it's the latter. But yeah, probably we should
just always refer to it as the private key, sorry for the confusion.

[1]: https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/
[2]: https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-crypto-refresh#section-5.6.5

> See: https://gitlab.com/openpgp-wg/rfc4880bis/-/merge_requests/61/diffs?commit_id=29e9a3112e961afbea96cf96dccd8b0148d60f29

OK, yeah. I mean, I personally still think we should do something that's
consistent, or backwards compatible with Curve25519 in OpenPGP, so that
(as much as possible) we don't need two separate code paths for
Curve25519 and Curve448. But OK, we can discuss that tomorrow :)

Best,
Daniel

---

From: Daniel Huigens <[email-masked]>
Date: Thu, 02 Sep 2021 18:03:11 +0000

(Sorry, I meant RFC8032, ofc.)

---

From: Justus Winter <[email-masked]>
Date: Fri, 03 Sep 2021 17:13:10 +0200

> I believe this is what GnuPG 2.3-beta implemented; correct me if I'm wrong.

This is a key as generated by GnuPG 2.3.0.  I haven't looked at whether
the secret scalar is reversed or not.  I note that -at least in this
case- all artifacts were well-formed MPIs, i.e. they did not contain
leading zero bytes.

% cat C6A189EE3A8A832326AFDD586FA330A88FDC1A0C.pub.pgp
% cat C6A189EE3A8A832326AFDD586FA330A88FDC1A0C.sec.pgp
% sq packet dump --mpis C6A189EE3A8A832326AFDD586FA330A88FDC1A0C.sec.pgp
Secret-Key Packet, old CTB, 131 bytes
    Version: 4
    Creation time: 2021-09-03 15:01:37 UTC
    Pk algo: EdDSA Edwards-curve Digital Signature Algorithm
    Fingerprint: C6A189EE3A8A832326AFDD586FA330A88FDC1A0C
    KeyID: 6FA330A88FDC1A0C

    Public Key:
        Curve: Unknown curve (OID: [43, 101, 113])

        00000000  f1 a0 5d 93 5d 71 37 d0  40 21 c0 d9 c4 72 d7 a2   q
        00000010  1f c4 91 d1 6d 61 28 f0  0a 08 f8 94 e3 2d 87 19
        00000020  5a ab d0 18 31 51 57 7d  9e 1d 3a a8 2e 76 cd e9
        00000030  ee 17 fb a7 0e f3 00 ae  80

    Secret Key:

        Unencrypted

        00000000  f6 cd 6b f1 fb b8 eb f8  7b d1 71 f4 53 33 81 ce   scalar
        00000010  c3 f7 bc 04 e3 a0 2b bd  67 f2 1c fa dd ce 37 e4
        00000020  65 6b 02 96 d4 7c 81 58  1c af 59 32 f0 dc cb bb
        00000030  64 6c 3f 99 f9 80 50 f5  dd

User ID Packet, old CTB, 35 bytes
    Value: Ed448 / X448 generated by GnuPG 2.3

Signature Packet, old CTB, 198 bytes
    Version: 4
    Type: PositiveCertification
    Pk algo: EdDSA Edwards-curve Digital Signature Algorithm
    Hash algo: SHA512
    Hashed area:
      Issuer Fingerprint: C6A189EE3A8A832326AFDD586FA330A88FDC1A0C
      Signature creation time: 2021-09-03 15:01:37 UTC
      Key flags: CS
      Symmetric algo preferences: AES256, AES192, AES128, TripleDES
      AEAD preferences: OCB, EAX
      Hash preferences: SHA512, SHA384, SHA256, SHA224, SHA1
      Compression preferences: Zlib, BZip2, Zip
      Features: MDC, AEAD, #2
      Keyserver preferences: no modify
    Unhashed area:
      Issuer: 6FA330A88FDC1A0C
    Digest prefix: 591A
    Level: 0 (signature over data)

    Signature:

        00000000  86 57 6d d1 6d de 3a 51  cc 79 3b e1 8c 0a 2f 6f   r
        00000010  28 bf 61 4b bd 6c df e7  fc e2 ad 76 7d 82 e0 99
        00000020  23 6c b7 e9 7b 11 e4 76  b0 f5 e4 29 90 8e 58 91
        00000030  1d ce 06 3e d4 4a 84 94  00

        00000000  fd 30 e5 d6 fb 5b 82 db  e9 51 f0 09 68 47 6b 8c   s
        00000010  eb de 2b 8f 63 45 aa 30  8b 33 b8 f6 14 86 91 fa
        00000020  cb 6d 34 6d d5 98 55 c6  9b 17 f7 cb 33 ba d5 cf
        00000030  53 9f 30 64 8d 1a 6d 17  00

Secret-Subkey Packet, old CTB, 133 bytes
    Version: 4
    Creation time: 2021-09-03 15:02:10 UTC
    Pk algo: ECDH public key algorithm
    Fingerprint: 498D84702456605AECACF8CD2924B48203CA1421
    KeyID: 2924B48203CA1421

    Public Key:
        Curve: Unknown curve (OID: [43, 101, 111])
        Hash algo: SHA512
        Symmetric algo: AES with 256-bit key

        00000000  71 2a b7 32 2f 09 de c3  d8 76 dd 82 2c 7d 48 1d   q
        00000010  cd d2 9f 76 b2 17 4c 5e  de 1a 1f 5a 4c ce 5d 18
        00000020  9c ca bb 84 87 fe 7a c4  22 bb 60 ff aa 20 68 c9
        00000030  ce ee b8 0f fe d5 6a db

    Secret Key:

        Unencrypted

        00000000  3b 8e 89 5e fc 82 4f 6c  12 20 e1 78 d0 52 67 22   scalar
        00000010  35 d0 fe 6d 70 3c 22 fd  cc ab 8c 51 e7 5b d8 b9
        00000020  48 04 47 db 55 14 c1 c5  3c f3 a0 68 63 c6 01 9e
        00000030  b5 40 83 7a 1f 17 59 8e

Signature Packet, old CTB, 170 bytes
    Version: 4
    Type: SubkeyBinding
    Pk algo: EdDSA Edwards-curve Digital Signature Algorithm
    Hash algo: SHA512
    Hashed area:
      Issuer Fingerprint: C6A189EE3A8A832326AFDD586FA330A88FDC1A0C
      Signature creation time: 2021-09-03 15:02:10 UTC
      Key flags: EtEr
    Unhashed area:
      Issuer: 6FA330A88FDC1A0C
    Digest prefix: 3E3F
    Level: 0 (signature over data)

    Signature:

        00000000  68 11 e8 bb f7 5e 02 39  f3 77 31 7c 6f b2 f5 ca   r
        00000010  81 ec b9 91 1d a8 57 1e  69 49 1a b2 12 c4 30 88
        00000020  18 13 48 23 ce 6e 58 69  0d 84 fb 20 41 38 d8 67
        00000030  c0 52 ba 9c b9 44 e5 31  00

        00000000  83 b5 16 84 f1 7f c2 a8  86 90 d7 cf a0 6a a9 33   s
        00000010  bd ca a0 df 69 25 12 b5  18 b5 92 79 e8 44 b1 4a
        00000020  9e 72 a0 f1 c3 a9 51 79  e8 22 ba 14 2f 8c b2 8c
        00000030  fc d1 e4 fc e8 19 85 2d  00

Justus

---

From: Justus Winter <[email-masked]>
Date: Wed, 08 Sep 2021 12:39:32 +0200

>         00000030  ee 17 fb a7 0e f3 00 ae  80

A 57 octet value, so this is an Ed448 public key without an encoding
prefix.  This makes me think that we're looking at SOS-encoding.

>         00000030  64 6c 3f 99 f9 80 50 f5  dd

Likewise, though current practice is not to prefix EdDSA scalars.

>         00000030  53 9f 30 64 8d 1a 6d 17  00

We don't expect prefixes here, but these are two 57 octet MPIs that we
expect for Ed448.  See below though.

>         00000030  ce ee b8 0f fe d5 6a db

A 56 octet value, so this is an X448 public key without an encoding
prefix.  This makes me think that we're looking at SOS-encoding.

>         00000030  b5 40 83 7a 1f 17 59 8e

Likewise, though current practice is not to prefix ECDH scalars.

I generated a lot of keys until I got one starting with a zero octet
(password is foo):

If we inspect it, we see that Sequoia complains about the encoding of
the public key:

Unknown or Unsupported Packet, old CTB, 2 header bytes + 177 bytes
    Tag: Secret-Key Packet
    Error: Malformed MPI: leading bit is not set: expected bit 8 to be set in        0 (0)

   00000000  94                                                 CTB
   00000001     b1                                              length
   00000002        04                                           version
   00000003           61 38 8b a3                               creation_time
   00000007                       16                            pk_algo
   00000008                           03                        curve_len
   00000009                              2b 65 71               curve
   0000000c                                       01 c8 00 ba               ....
                                     leading zero octet ^^
   00000010  ba 58 e0 97 dc 54 54 43  7c 77 b2 31 c4 41 1a 38   .X...TTC|w.1.A.8
   00000020  fe 3b 2d 80 2d ae f2 ef  cf 9c ec 92 ad 28 8e eb   .;-.-........(..
   00000030  4d 15 a4 35 a0 23 d5 df  12 5d 6c ce 6d 63 14 05   M..5.#...]l.mc..
   00000040  c9 d8 d5 2d 14 af 80 fe  07 03 02 76 93 f3 d7 cc   ...-.......v....
   00000050  d7 a0 42 ff e0 8b 94 bd  e9 9a 39 cf d2 5b 5f 1e   ..B.......9..[_.
   00000060  6d df a7 23 a5 ea 30 23  f5 a7 72 ba 7b bf 44 62   m..#..0#..r.{.Db
   00000070  ec 68 62 0e 3a 0f 39 77  a1 58 39 01 be 03 26 dc   .hb.:.9w.X9...&.
   00000080  6e 84 7c b3 92 6f fe 86  ef 9c 57 88 b3 7f 99 f2   n.|..o....W....
   00000090  2a fe 23 a4 3d fc bb 81  59 00 c9 77 33 6b 67 9d   *.#.=...Y..w3kg.
   000000a0  9e b6 a4 54 65 7b 25 b4  9d 61 f9 d5 7b 5d 5c ed   ...Te{%..a..{]\.
   000000b0  f8 6c 84                                           .l.

Maybe even more interesting, we see that the EdDSA signature is also SOS
encoded (password is foo):

If we dump it, the userid's binding signature fails to parse:

Secret-Key Packet, old CTB, 2 header bytes + 177 bytes
    Version: 4
    Creation time: 2021-09-08 10:03:12 UTC
    Pk algo: EdDSA Edwards-curve Digital Signature Algorithm
    Fingerprint: 77F0FE1E592E1BCE2816EA79C422FE1E8B740A5F
    KeyID: C422FE1E8B740A5F
[..]

User ID Packet, old CTB, 2 header bytes + 5 bytes
    Value: ed448
[..]

Unknown or Unsupported Packet, old CTB, 2 header bytes + 204 bytes
    Tag: Signature Packet
    Error: Malformed MPI: leading bit is not set: expected bit 8 to be set in        0 (0)

  00000000  88                                                 CTB
  00000001     cc                                              length
  00000002        04                                           version
  00000003           13                                        type
  00000004              16                                     pk_algo
  00000005                 0a                                  hash_algo
  00000006                    00 42                            hashed_area_len
  00000008                           16                        subpacket length
  00000009                              21                     subpacket tag
  0000000a                                 04                  version
  0000000b                                    77 f0 fe 1e 59   issuer fp
  00000010  2e 1b ce 28 16 ea 79 c4  22 fe 1e 8b 74 0a 5f
  0000001f                                                05   subpacket length
  00000020  02                                                 subpacket tag
  00000021     61 38 8a 60                                     sig creation time
  00000025                 02                                  subpacket length
  00000026                    1b                               subpacket tag
  00000027                       03                            key flags
  00000028                           05                        subpacket length
  00000029                              09                     subpacket tag
  0000002a                                 03 c2 67 00         key expiry time
  0000002e                                             05      subpacket length
  0000002f                                                0b   subpacket tag
  00000030  09 08 07 02                                        pref sym algos
  00000034              03                                     subpacket length
  00000035                 22                                  subpacket tag
  00000036                    02 01                            pref aead algos
  00000038                           06                        subpacket length
  00000039                              15                     subpacket tag
  0000003a                                 0a 09 08 0b 02      pref hash algos
  0000003f                                                04   subpacket length
  00000040  16                                                 subpacket tag
  00000041     02 03 01                                        pref compression algos
  00000044              02                                     subpacket length
  00000045                 1e                                  subpacket tag
  00000046                    07                               features
  00000047                       02                            subpacket length
  00000048                           17                        subpacket tag
  00000049                              80                     key server pref
  0000004a                                 00 0a               unhashed_area_len
  0000004c                                       09            subpacket length
  0000004d                                          10         subpacket tag
  0000004e                                             c4 22   issuer
  00000050  fe 1e 8b 74 0a 5f
  00000056                    24                               digest_prefix1
  00000057                       73                            digest_prefix2
  00000058                           01 c8 00 b5 c5 99 15 8f           ........
                        leading zero octet ^^
  00000060  3b 8d 88 83 d9 69 63 4a  4b de a0 bb 99 30 fd 4b   ;....icJK....0.K
  00000070  f3 99 90 fa ac c7 33 05  4f d5 24 68 37 fa ec 38   ......3.O.$h7..8
  00000080  38 28 a1 55 b2 f7 b2 0e  e4 b9 84 00 86 3f d9 f4   8(.U.........?..
  00000090  88 e4 00 01 c8 c7 cb 3f  f8 26 f2 89 86 38 6b 4d   .......?.&...8kM
  000000a0  79 36 29 5f d3 60 9b 99  40 2f cd fb b2 b4 77 78   y6)_.`..@/....wx
  000000b0  9b 56 5d 30 fc ad 31 1b  1d 1a 95 07 b8 01 e4 6f   .V]0..1........o
  000000c0  53 21 f9 7c d2 c5 f4 c8  2f 6f 15 25 28 00         S!.|..../o.%(.

Justus

---

From: Daniel Huigens <[email-masked]>
Date: Fri, 10 Sep 2021 13:05:02 +0000

Thanks for the key, and analysis! I can confirm that the X448 secret key
is non-reversed (see attached x448.py).

It is also somewhat noteworthy that it is not in canonical form, either,
which is not an issue (as RFC7748 allows this) but it is another slight
inconsistency with Curve25519 in OpenPGP, where this was seemingly
required (as far as I remember). In other words, I think GnuPG masks the
Curve25519 private key during generation, but the Curve448 private key
during usage (which RFC7748 requires - e.g. see the steps on page 8).
Of course, it should be fine to always do both, if one values
consistency between the two (at the cost of sacrificing the simplicity
of just generating random bytes as the private key in X448).

(I haven't tested what GnuPG does for Curve25519 in a while, fwiw, so I
may be misremembering or it might have changed in GnuPG 2.3.)

Best,
Daniel

---

From: Paul Wouters <[email-masked]>
Date: Wed, 15 Sep 2021 15:47:59 -0400 (EDT)

> of just generating random bytes as the private key in X448).

I don't think consistency between curve25519 and curve448 is very
imporant. It might be worth more to consider how any newer curves
later would be best implemented. If that makes curve25519 more of an
outlier, I think that's fine. No need to stain curve448 with that?

Paul

---

From: Daniel Huigens <[email-masked]>
Date: Wed, 15 Sep 2021 21:41:19 +0000

> outlier, I think that's fine. No need to stain curve448 with that?

I find it unlikely that after Curve448, new curves will ever be desired.
Its security level is high enough to likely remain unbreakable by
classical computers forever; quantum computers are the main threat to
its security. So imo after this crypto refresh we should (eventually)
focus our attention on post-quantum crypto, with new algorithm
identifiers entirely, and new (non-MPI-resembling) encodings, etc.

That being said, from the last two calls, it seemed that people
preferred to spec Curve448 in a more straightforward way, without the
oddities of Curve25519, which I'm not opposed to, but I think it's
worth pointing out that we'll then most likely forever have two
outliers, not one.

(Of course, the elephant in the room remains the question of whether
GnuPG is willing to still change their implementation, if not we should
just spec what GnuPG does imo, personally I think it's not such a bad
option, anyway, but I know not everybody agrees ^.^)

Best, Daniel

---

From: Werner Koch <[email-masked]>
Date: Mon, 20 Sep 2021 09:49:07 +0200

> I find it unlikely that after Curve448, new curves will ever be desired.

I can't agree to that.  I once took care in 6637 that arbitrary curves
could be used and not just a small set of publicly known curves.  The
reason for that were the Brainpool curves which are required in Europe
for restricted communication _and_ for qualified electronic signatures.
There are a lot of more curves on the table including those with
classified parameters.  Any standard which has no provisions to allow
there use will be doomed.

FWIW, I am in favor of keeping ed25519/curve25519 in OpenPGP as they
are, that is not renaming them (because X25519 is different) and to have
a more straightforward way to encode newer curves.

SOS is a way for a more clear definition for ECC stuff and can be used to
replace the problematic MPI encoding which we kept in OpenPGP only for
PGP2 backward compatibility.  I am also fine with any other method,
including a prefix octet, for newer curves (e.g. 448) as long as parsing
a keyblock or message is possible without knowing the curve.

I don't think that the 16 bit we have for MPIs will pose a problem for
PQC as long as we introduce a new key formatversion which can then
finally use a simpler type for numbers or strings (i.e. what ssh does).

Shalom-Salam,

   Werner

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

---

From: Justus Winter <[email-masked]>
Date: Mon, 20 Sep 2021 10:03:07 +0200

> finally use a simpler type for numbers or strings (i.e. what ssh does).

I did a survey of third-round PQ finalists:

https://mailarchive.ietf.org/arch/msg/openpgp/cUTLEANtkI2x-3X8tAR2aJUl3K4/

tl;dr is McEliece won't fit and most signature schemes are problematic.

Justus

---

From: Werner Koch <[email-masked]>
Date: Mon, 20 Sep 2021 13:21:51 +0200

> tl;dr is McEliece won't fit and most signature schemes are problematic.

Not really.  Dilithium would fit fine and is at least for the BSI the
most promising candidate.  I remarked that we will need a new key packet
version anyway for PQC and thus MPIs won't be necessary.  It would be a
good opportunity to introduce a new datatype with a key version 6.

Salam-Shalom,

   Werner