[openpgp] Re: Encryption subkey selection

[Daniel Huigens <[e-mail]>]

Hi Falko,

I left the exact algorithm a bit open as IMO it's up for debate and also depends on which variant we go with from the ones I proposed (if any). In the first & simplest variant, I imagined it would be something like:

- for each certificate I have, in the order given by the RKS or an implementation-defined order (e.g. newest first):

- if the certificate contains an encryption subkey that I can use:

- encrypt to all valid encryption subkeys that I can use
- return

This changes the behavior even in the single-certificate case, but matches what Sequoia already does in that case. If you don't like that behavior you might like the one below more.
(It also doesn't properly handle the case where e.g. the first certificate contains an ML-KEM-768 and an ML-KEM-1024 subkey, each for a different device, and I only support ML-KEM-768, for example. But as I wrote before I think that's a silly thing to do as you don't gain security from using ML-KEM-1024 on one of the devices if the sender is always going to use ML-KEM-768 to encrypt as well.)

In the last & most flexible variant I imagined it would be something like:

- for each certificate I have, in the order given by the RKS or an implementation-defined order (e.g. newest first):

- if the certificate says that it wants all encryption subkeys to be used:

- if the certificate contains only encryption subkeys that I can use:

- encrypt to all of them
- return
- else if this is the last certificate I have:

- encrypt to all encryption subkeys that I can use
- return
- else:

- if the certificate contains an encryption subkey that I can use:

- encrypt to it
- return

That way, in both cases, there are no new failure modes introduced that there weren't before (which I agree is important).

Just FWIW, I also want to point out that while it's obvious that the second one covers more use cases than the first one, IMHO we also need to keep in mind the effort it will take to test all code paths, make sure all implementations are consistent in every case, and so on. The more complex an algorithm we propose, the more difficult that will be. So I hope we can find the simplest algorithm that covers all cases that we think are absolutely necessary :)

Best,
Daniel

On Wednesday, April 9th, 2025 at 08:33, Falko Strenzke <[e-mail]> wrote:

> Hi Daniel,
>
> I am not entirely sure what exact algorithm you are proposing for encryption key selection. Do you mean this?
>
> - if certificate has replacement key subpacket pointing to a further certificate
>
> - while have certificates to select, process next certificate in sequence
>
> - if certificate contains only encryption subkeys that I can use:
>
> - encrypt to all of them
> - return
>
> - fail to encrypt (⁕)
>
> - else:
>
> - encrypt to whatever subset of encryption keys the user or implementation prefers
>
> That would mean that the including a replacement key subpacket (RKS) pointing to the previous key would imply that all the encryption subkeys of the certificate should be used in parallel, whereas where the subpacket is absent, the sending implementation is free to choose any set of subkeys. I am not sure if everyone who will include an RKS to point to a previous key want this behaviour. This would also retroactively change the behaviour for the certificate pointed to, which possibly was created without the assumption that all encryption subkeys should be used in parallel. It would introduce a new failure case also. Or should the last step in the outer if-clause (⁕) be: “choose one certificate and encrypt to as many of it’s subkeys as possible”?
>
> And do you mean that multiple certificates of the same recipient should be handled in this way in any case (where the ordering would have to be determined somehow), or only in the case that they are linked by the RKS?
>
> Best regards,
> Falko
>
> Am 08.04.25 um 20:06 schrieb Daniel Huigens:
>
>> Hi Justus & all,
>>
>> I agree that it would be good to reach a consensus on this, and that
>> if we assume that we want to support one-subkey-per-device setups
>> (e.g. for use with integrated HSMs, to be able to generate a key
>> on each of your devices in hardware), which seemed to be the
>> conclusion from the multi-device session at the summit,
>> then we probably need some mechanism for that.
>>
>> _However_, I want to raise one specific potential solution that
>> Patrick Brunschwig proposed in that session, which is a variant of
>> "List of sets of subkeys", but rather than introducing some new
>> encoding for this, we could simply say: each certificate is such
>> a list of subkeys. In other words, we pick the first certificate,
>> see if it's usable, if so use all valid encryption subkeys in that
>> certificate. If not, try the next certificate. And so on.
>>
>> This means that, to migrate to a new encryption algorithm, you also
>> need to generate a new certificate. Often we want to do that anyway:
>> in the migration from RSA to ECC, and ECC to PQC, we've introduced
>> both new encryption algorithms and new signing algorithms.
>>
>> I know this goes a bit against what I've said previously and also
>> conflicts with the concept of "certificate equivalence" in the
>> key replacement draft (because multiple subkeys across linked certs
>> would then not behave the same as multiple subkeys in a single cert).
>> _But_ if we all agree that we need some mechanism for this then
>> I think it's best to pick the simplest possible mechanism.
>>
>> ---
>>
>> Alternatively, as an intermediary solution, we could have a single
>> _per-certificate_ flag which says: please use all valid encryption
>> keys in this certificate. (And potentially also: if you don't
>> understand all encryption subkeys, please use the fallback
>> certificate instead, if there is one. That being said, I think
>> it would be a bit silly and a very niche edge case if you want
>> to e.g. use a mix of ML-KEM-768 and ML-KEM-1024 subkeys in
>> your latest cert, _especially_ you're going to ask the sender
>> to encrypt to all of them, as then there's no security advantage
>> to using ML-KEM-1024 in one/some of the subkeys).
>>
>> That way, we could keep the existing behavior for a single cert,
>> if needed (so that you could still do a encryption algorithm
>> migration within a single cert if you only have a single device),
>> but could opt-in to the new behavior (from our perspective;
>> obviously for Sequoia it'd be the other way around) if you have
>> multiple devices.
>>
>> The only thing you then can't do is an encryption(-only) algorithm
>> migration within a single certificate with per-device subkeys.
>> But, that kinda seems like an edge case within an edge case..
>>
>> Best,
>> Daniel
>>
>> _______________________________________________
>> openpgp mailing list --
>> [e-mail]
>> To unsubscribe send an email to
>> [e-mail]
>
> --
>
> MTG AG
> Dr. Falko Strenzke
>
> Phone: [phone]
> E-Mail: [e-mail]
> Web: [mtg.de](https://www.mtg.de)
>
> ---------------------------------------------------------------
>
> MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
> Commercial register: HRB 8901
> Register Court: Amtsgericht Darmstadt
> Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
> Chairman of the Supervisory Board: Dr. Thomas Milde
>
> This email may contain confidential and/or privileged information. If you are not the correct recipient or have received this email in error,
> please inform the sender immediately and delete this email.Unauthorised copying or distribution of this email is not permitted.
>
> Data protection information: [Privacy policy](https://www.mtg.de/en/privacy-policy)