[openpgp] Encryption subkey selection

[Justus Winter <[e-mail]>]

Hello,

at the OpenPGP email summit, we had a session about encryption subkey
selection.

The question is: given an OpenPGP certificate with more than one
(usable, non-expired, non-revoked) encryption subkey, which one(s) do
you use when encrypting a message for that certificate.

We started by charting the existing implementation behaviors.  We were
aware of three classes of behavior, which we will name Proton,
OpenKeyChain, and GnuPG.  (To clarify, that shouldn't be seen as more
than picking recognizable handles for classes of behavior by reusing
the name of well known implementations/organizations representing
their respective class.)

  - Proton (OpenPGP.js, GopenPGP, RNP) use the key creation time as
    metric, and uses the newest encryption subkey.

  - OpenKeyChain (also all of Sequoia's frontends) use all encryption
    subkeys.

  - GnuPG uses the key creation time as metric, and uses the newest
    encryption subkey, but it also takes the algorithm into account,
    and at least prefers ECC over RSA (this may have changed, or work
    slightly differently, but the point is that there is a more
    complex metric than just looking at the key creation time).

From this survey it seems clear that the status quo is not great: at
least we want the ecosystem to behave consistently and predictably.
But, converging on a single model would be a lot easier if that model
would cater to the various needs.

Then, we formulated properties that we like to have, and asked whether
the above models give us these properties, under the assumption that
the ecosystem agreed to use the given model.

The properties are all from the perspective of the certificate holder,
who we think should have a say over the choice of subkey selection
behavior by the peers encrypting messages for her.

  - Pick one: can the certificate holder express the wish that the
    sender uses at most one subkey?

    - Use cases: this is the status quo for many implementations, and
      the "at most 1" part is important if you hope to do transitions,
      i.e. transition to newer algorithms and stop using older ones).

  - Pick a set: can the certificate holder express the wish that the
    sender uses a set of subkeys?

    - Use cases: some forms of multi-device support.

  - Migrations: can the certificate holder express the wish to migrate
    to newer subkeys?

    - Use cases: opportunistic upgrade to newer algorithms.

Finally, we discussed potential models, and evaluated them under the
properties we identified.

  - Rank: have an explicit rank, and specify an algorithm how to chose
    using that.  The exact details are yet to be determined, but
    notably it should have the property that if subkeys tie on this
    metric, all of them are used.

  - Flag: rank over {0, 1}.

  - List of sets of subkeys: pick the first set that is usable for
    encryption (using all keys in the set).  If there is no such set,
    fail.

These are the results:

    |  Models     |  Pick 1?  |  Pick set?  |   Migrations?  |
    |-------------|:---------:|:-----------:|:--------------:|
    |  Proton     |    ✓*     |     ✗       |       ✓⸸       |
    |  GnuPG      |   (✓)†    |     ✗       |      (✓)†⸸     |
    |  OKC/"All"  |    ✓      |     ✓       |       ✗        |
    |             |           |             |                |
    |  Rank       |    ✓      |     ✓       |       ✓        |
    |  Flag       |    ✓      |     ✓       |       1‡       |
    |  List       |    ✓      |     ✓       |       ✓        |

Where:

  - * By lying about the creation time, potentially
  - ⸸ If you only have a single device/key
  - † If your preference matches GnuPG's hardcoded algorithm preference
  - ‡ One migration at a time is possible; a multi-step migration
    (e.g. RSA -> ECC -> PQC) is not possible

As usual, the devil is in the details, and time was running out, and
we didn't even get to the mechanism discussion yet.  But, the rough
agreement in the room was that the status quo should be improved, the
"Flag" model is probably too restrictive, the "List" model is overly
expressive and doesn't seem to offer an advantage over the "Rank"
model.

To make the discussion more concrete, I'm going to propose a
mechanism.

  - We add a signature subpacket that can be added to subkey binding
    signatures.  The subpacket body is a single octet representing an
    unsigned integer, the rank.

  - When encrypting a message for a cert that uses this mechanism:

    (Where "uses this mechanism" means that all non-expired,
    non-revoked encryption subkeys have a valid binding signature with
    the rank subpacket.)

    1. sort the subkeys by the rank
    2. if the list is empty, fail
    3. consider the subkeys with the highest rank
    4. attempt encryption for the subkeys with the highest rank
    5. if none of the considered subkeys were usable for encryption,
       remove them, and go to step 2
    6. construct PKESK packets for every successful encryption, and
       continue to encrypt the message (i.e. do the same for other
       recipient certs, or encrypt the payload).

  - Open questions (that I can immediately think of, but please speak
    up if you have more):

    - I think this can be extended to encryption subkey selection over
      certificate equivalence groups (see the OpenPGP Key Replacement
      draft) by adding a rank parameter to every equivalence binding
      signature (essrank_cert), then modify the above procedure to
      sort by (essrank_cert, essrank_subkey).

    - What should we do for existing certificates that do not use this
      mechanism?  I guess the path of least resistance is to keep
      doing whatever the implementation currently does.

[Notes from the session:
 https://www.openpgp.org/community/email-summit/2025/minutes/#encryption-subkey-selection-justus ]


Best,
Justus