Subject: [openpgp] Multi-algo pubkey, or how to create future-proof keys

From: Ángel <[email-masked]>
Date: Mon, 21 Jun 2021 03:16:42 +0200

Hello all

I would like to bring up a point I had noticed some time ago, about
having multiple public keys combined. A few days ago, we have been
talking about v5 keys, potential Post-Quantum algorithms, etc.

In OpenPGP, when creating a new key one faces a first-mover
disadvantage. Since the openpgp key itself is identified by the primary
public key, only one public key algorithm can be used.
Then, when a new algorithm appears which is -hopefully- more secure,
choosing the new algorithm means that the key cannot be used by people
with old clients (in some cases, prehistoric ones). Whereas using an
old algorithm with better support leads to no incentive to implement
the new algorithm, or to use it.

This also means that if a critical vulnerability appears in an existing
algorithm (such as a Quantumcalypse), finally forcing the use of the
better algorithm, everyone will need to create new keys and the WOT
will have to be re-created from scratch.

Note that subkeys don't help here, since if the master key is
newer/stronger than the subkey, the key won't be accepted by old
clients. And if you use a subkey stronger than the main key, an
attacker could just add a new subkey under their control.

The solution I foresee is to spec a way to have a key with *multiple*
public keys. When signing, the signer MUST provide signatures with all
of them. When verifying, unsupported algorithms SHOULD be ignored, as
long as one of them is known and least verifies correctly, it's
considered valid. Note that if a client sees a valid signature with
algo A and an invalid signature with algo B, it MUST be rejected.
Skipping is only for the cases when the algorithm is unknown /
disabled, not for ignoring invalid signatures.

I initially considered this would need to be included natively in v5,
but it can be implemented as a special pubkey algorithm (e.g. 255)
defined as a concatenation of two or more public-key packets (using
algorithms other than 255) and whose signature is a concatenation of as
many signature packets as present in the key definition.

This is just a high-level description, it obviously needs to be
formalized, but hopefully it conveys the idea.

Regarding scope, it seems suitable to include into the cryptography
revision and, although not strictly required, being included with a
major version would probably be helpful.

Does anyone have any comment about including this?
(either about the general idea or using that special "pubkey")

Best regards

Ángel

---

From: Werner Koch <[email-masked]>
Date: Mon, 21 Jun 2021 11:48:14 +0200

> major version would probably be helpful.

This is not part of the WG charter and thus this should be deferred for
a future revision.  It is also possible, as you noted, that this can be
done as a new algo. Fortunately 4480bis has a goal to make it easier to
come up with new algorithms.

n any case, it is always possible to write an I-D for an extension of
OpenPGP. We did this for ECC and I think this is the best way for new
experimental algorithms.

Salam-Shalom,

   Werner

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

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 21 Jun 2021 22:06:57 +0100

Hiya,

(This is just my personal reaction - as chair, if there were
a load of people wanting this now, I'd re-evaluate...)

> talking about v5 keys, potential Post-Quantum algorithms, etc.

I think I agree with Werner that this is better one for
later. My particular reasons are that moving from 1 to many
keys isn't so much a crypto change as an architectural one
and that as you point out, such a change if/when it comes, is
likely to be intertwined with PQC (assuming the model of
mixing "classic" and PQ algs seeming to find favour with
e.g. TLS is also sensible for pgp).

Lastly, (and this time looking at, but not quite wearing, a
chair hat:-), I'd prefer see us progress the "easier" work
first and then attempt more ambitious things.

Cheers,
S.