[openpgp] Re: Encryption subkey selection

[Falko Strenzke <[e-mail]>]

Hi Daniel,

from these two options I'd indeed prefer the second one, as there it is 
made explicit how the encryption keys in a single certificate are 
intended to be used.

In general I think it will be better to specs for the mechanism for 
encryption subkey selection per certificate and the replacement key 
mechanism separate. The reason is that if they are linked to closely, it 
will be unclear what an implementation does when it supports one but not 
the other. But as far as I can see, that is given in both of your proposals.

Best regards,
Falko

Am 09.04.25 um 11:28 schrieb Daniel Huigens:
> 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):
>       o 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):
>       o 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
>       o 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
>>       o 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
>>       o fail to encrypt (⁕)
>>   * else:
>>       o 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 [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>
>>
>
>
> _______________________________________________
> openpgp mailing list [e-mail]
> To unsubscribe send an email [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>