Subject: [openpgp] Discussion regarding signalling of preferences for multiple encryption-capable keys

From: Falko Strenzke <[email-masked]>
Date: Thu, 14 Apr 2022 15:06:16 +0200

I cannot post to the Design Team list, so I post it on this mailing list:

Regarding the discussion around multiple encryption-capable subkeys, I 
would like to make the following remarks on behalf of the project 
PQC@Thunderbird. At IETF 113 we presented our ongoing project for the 
standardisation of PQC in OpenPGP. Well aware that this is not in the 
scope of the crypto refresh, we still want to make a comment on the 
signalling mechanism for a preferred usage of multiple encryption 
subkeys, as it is currently being discussed by the Design Team. The 
reason is that a related issue will in our view most likely also arise 
in the context of multi-algorithm encryption. What we refer to as 
multi-algorithm encryption is often also referred to as hybrid 
encryption and means the combined encryption with two public key 
encryption schemes in such a way, that the combined scheme is only 
broken when both constituent schemes are broken. "Both constituent 
schemes" will typically be a classical scheme and a PQC scheme. For such 
a combination of two public-key encryption operations, an algorithm for 
the derivation of the session key from the input-keys encrypted in each 
PKESK is also needed. Proposals for this exist and typically involve the 
use of a KDF.

So far to introduce the background. Now we come to the point were the 
signalling of the intended subkey usage matters in this approach: If a 
user wants to restrict others to only sending him encrypted messages 
using multi-algorithm encryption with two specific encryption subkeys 
from his keyring in combination – i.e. not allowing them to use either 
of the two keys in the default "single-algorithm" manner, the question 
arises
* how to signal to the sender that a certain encryption subkey must only 
be used in a multi-algorithm combination with another (specific) subkey 
from the same keyring (e.g. to indicate: "use this PQC key only in 
multi-algorithm encryption together with ECDH")?

In our understanding this problem could be solved by a signalling 
mechanism analogous to the one discussed now regarding parallel 
encryption. The mechanism would have to be enhanced by a flag signalling 
the intended use of a key in the multi-algorithm context only.

We just want to provide this piece of information for the case it 
matters for the ongoing discussion in Design Team.

Best regards,
Falko

-- 

MTG AG
Dr. Falko Strenzke
Executive System Architect

Phone: +49 6151 8000-24
E-Mail: [email-masked]
Web: 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: www.mtg.de/en/privacy-policy

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 14 Apr 2022 13:52:39 -0700

Hi Falko--

On Thu 2022-04-14 15:06:16 +0200, Falko Strenzke wrote:
> PQC@Thunderbird.

Thanks for this note, you're making it in the right forum :)

I agree with you that the semantics for PQC hybrid encryption schemes
are likely to be similar to (but subtly different from) the semantics
for parallel encryption schemes.  Their signalling probably does belong
in the same sort of spot in the spec, however that gets worked out.

I'm currently imagining that it's either a bit in the key usage flags
subpacket, or it's an entirely new subpacket (possibly marked critical,
i'm not sure).  Either way, i'd imagine that the subpacket with this
indicator probably belongs in the subkey binding signature.

> multi-algorithm encryption together with ECDH")?

right, there are two distinct things a keyholder might want to signal:

- the *capability*: that they can accept a hybrid scheme, and
- the *requirement*: that they *require* a hybrid scheme.

But, i'm not sure how much the keyholder's preference really matters for
the requirement part -- when encrypting, it's really the sender's policy
that ultimately governs, right?

For example, the sender can always send cleartext, which is arguably
worse than single ECDH.  And if the sender ignores the keyholder's
stated requirement for hybrid encryption, and chooses to just use ECDH
to encrypt a message to a single key that the recipient has, would the
recipient really refuse to decrypt it?  I mean, maybe some would, but
it's pretty hard to convince (for example) a MUA that they shouldn't at
least try to decrypt a ciphertext if they have the key available, even
if it's not their preferred algorithm.

The end user wants to see the cleartext!

What would you think about starting with a definition of just the
*capability* signal as you ramp up this work?  the semantics of the
*requirement* signal seem pretty ambiguous to me.

        --dkg

---

From: Falko Strenzke <[email-masked]>
Date: Fri, 15 Apr 2022 10:44:12 +0200

Hi Daniel,

Am 14.04.22 um 22:52 schrieb Daniel Kahn Gillmor:
> - the*capability*: that they can accept a hybrid scheme, and
> - the*requirement*: that they*require*  a hybrid scheme.
>

I agree in so far as that currently OpenPGP does not model and and does 
not need to model any similar requirement regarding signalling such 
restrictions for the use of encryption keys. But I think the 
post-quantum setting and the transition to it brings in a new aspect. 
Say Alice is a party aware of the need for secure encryption regarding 
messages sent to her. She has a PQC encryption and and ECDH key in her 
public key ring. Say Bob is among the users that send messages to Alice. 
If Alice wants Bob to use the highest possible degree of encryption, 
that would be the multi-algorithm combination of the PQC encryption 
scheme with ECDH. Let's now assume we only use signalling of the 
*capability* for multi-algorithm (i.e. what you refer to as hybrid) 
encryption. Bob uses some MUA that uses whatever policy the implementers 
chose for encrypting the message to Alice based the capabilities 
signalled in her keyring. This MUA thus chooses on its own one of these 
possible ways of encrypting the message:

- multi-algorithm combination of ECDH and the PQC key
- only the PQC key
- only the ECDH key
- parallel encryption with both keys

The point that I want to make is that currently with OpenPGP, Alice can 
restrict Bob to using an encryption key for messages to her by only 
including encryption keys in her keyring that she considers secure and 
telling him "send this sensitive data to me encrypted", the latter being 
an instruction that Bob must be assumed to understand and be able to 
enforce via the interface of his MUA. In the PQC setting the situation 
changes, the verbal signal "send it encrypted" just doesn't seem to 
suffice as it implies too many alternatives the security implications of 
which the average user will not be able to oversee (he only understands 
the difference "encrypted / unencrypted") – that is, if he is given any 
control over these alternatives by his MUA at all. This is specifically 
relevant if Bob uses a legacy MUA that does not even have a chance to 
interpret the signalled capability for multi-algorithm encryption at all.

Consequently we would consider it worthwhile to think about introducing 
the possibility for signalling the *requirement* for using an encryption 
key only in combination with another. That would simply mean that a 
conforming client would have to respect that requirement when encrypting.

> *requirement*  signal seem pretty ambiguous to me.

I think the actual decision has, if any, only a limited side effect on 
other design aspects. So I think postponing the decision and using 
either of the two for now should be fine for us.

Best regards,
Falko

(FYI: I am on vacation for two weeks now, so further responses may be 
delayed)

-- 

MTG AG
Dr. Falko Strenzke

Phone: +49 6151 8000-24
E-Mail:[email-masked]
Web:www.mtg.de

Data protection information:www.mtg.de/en/privacy-policy

---

From: Andrew Gallagher <[email-masked]>
Date: Fri, 15 Apr 2022 10:30:45 +0100

On 15/04/2022 09:44, Falko Strenzke wrote:
> In the PQC setting the situation changes, the verbal signal "send it 
> encrypted" just doesn't seem to suffice as it implies too many 
> alternatives the security implications of which the average user will 
> not be able to oversee (he only understands the difference "encrypted / 
> unencrypted") – that is, if he is given any control over these 
> alternatives by his MUA at all. This is specifically relevant if Bob 
> uses a legacy MUA that does not even have a chance to interpret the 
> signalled capability for multi-algorithm encryption at all.

If Bob is using legacy software that doesn't understand the new flags, 
then all bets are off. He may be using software that doesn't understand 
PQC at all. There is also the issue of how to order the encryption 
stages - flags are too inflexible to be useful in definind complex 
workflows. Must we then define an ordering in the standard? For all 
possible combinations?

The most reliable method IMO to protect against misinterpretation by 
legacy software is to define a novel subkey type for multi-algo 
encryption keys. Legacy software will then see an unknown key type and 
should always throw "no usable keys". The multi-algo subkey type would 
contain a list of keys in the order they should be applied. If we want 
to make use of multi-algo encryption optional, then we can bind another 
subkey.

-- 
Andrew Gallagher

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 15 Apr 2022 14:22:33 -0700

Hi Falko and Andrew--

thanks for your considered and thoughtful replies.

Falko, your description of an out-of-band ("verbal") signal for
"encryption required" is pretty interesting regardless of PQC, and makes
me wonder whether we want to think about formalizing such a signal.  I
can't tell in your description whether you're imagining that signal as a
one-off ("please just send this one message encrypted") or as a uniform
policy from the keyholder.

The closest i've seen to a uniform policy from the keyholder is
Autocrypt's "prefer-encrypt=mutual" setting [0], which has semantics of
"as long as the other person also has this setting, messages between us
should default to being encrypted."  But that's still pretty far from
"you must not send cleartext to this address".

[0] https://autocrypt.org/level1.html

Is anyone interested in publishing such a strong uniform policy signal
for any e-mail address they control?  If so, this seems like an
orthogonal issue to PQC, and worthy of a separate thread.

If we're talking about a one-off request for a must-be-encrypted
message, and the recipient's tooling is able to detect the capability
for and make use of a hybrid scheme, then it seems like the capability
signalling is all that is necessary. (i guess i'm imagining encouraging
any implementation that can detect the capability and use it to prefer
the hybrid scheme over either scheme individually or in parallel)

So the only use case left for "requirement" signalling is the case where
the recipient's tooling can't understand or make use of the hybrid
scheme, *can* encrypt to the ECDH subkey, but would rather that their mailer
refuses to send at all, rather than just sending encrypted with ECDH.
Seems pretty niche!

I agree with Andrew that one straightforward way to enforce the use of a
hybrid scheme would be with a dedicated public key ID.  The only risk
there is that we might then end up allocating some kind of combinatorial
explosion of codepoints in the pubkey id table if there are multiple
schemes of each type that might want to hybridize.

Another approach that doesn't overallocate those codepoints would be to
add a subpacket to the ECDH subkey binding signature that says "you can
encrypt to this subkey in hybrid combination with this other subkey".
That handles "capability" -- and you could include a field in the
subpacket that means "don't encrypt to this without using hybrid scheme
X".  To make that requirement stick even for implementations that don't
understand the hybrid scheme, you could set the critical bit on such a
subpacket.

Most implementations are pretty good about rejecting subkeys that have
an unknown critical subpacket in their binding signature, at least when
verifying signatures from the subkey:

   https://tests.sequoia-pgp.org/#Binding_signature_subpackets

But the interop test suite doesn't have any test yet for how well
implementations respect critical subpackets in the subkey binding
signatures for encryption:

  https://gitlab.com/sequoia-pgp/openpgp-interoperability-test-suite/-/issues/28

If either of y'all (or anyone else) wants to try to contribute to the
test suite, maybe try to write that test?

This would be a great bit of data to have available when we get around
to discussing how the hybrid scheme should be signalled in the
certificate.

        --dkg

---

From: Andrew Gallagher <[email-masked]>
Date: Sat, 16 Apr 2022 22:51:58 +0100

> On 16 Apr 2022, at 14:39, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

I was thinking more along the lines of having one codepoint for “hybrid encryption scheme” and put all other details in the contents. This would be similar to your subpacket idea, except that both/all of the atomic keys would be contained in subpackets, and the order of application of the atomic schemes would be reflected in the subpacket order.

A

---

From: Greg Maxwell <[email-masked]>
Date: Sun, 17 Apr 2022 00:47:06 +0000

> The end user wants to see the cleartext!

Under that basis one could argue that whenever unsupported ciphers are
requested the system ought to send cleartext embedded in an pgp
binary/ascii-armored message. ... Silently failing to insecure or less
secure than believed behavior isn't great. :)

I apologize for the potentially ignorant question-- but why are these
hybrid cryptosystems not just treated as a single cryptosystem e.g.
"classic mceliece xyz + ed448" or whatever?  In analyzing the security
and performance of a hybrid scheme and in maintaining it long term
(e.g. announcing concerns about failures in its components costs) it
would be much easier to do so if it were treated as a single atomic
unit.

"Your messages are secure, unless some of them happened to be
encrypted without function-bar in parallel, which you wouldn't know
because these messages were silently accepted in spite of your key
requesting otherwise."

One doesn't generally allow users to request and initialize the
discrete log cryptosystems under every conceivable combination of
field/group/parameters though openpgp certainly could have been
designed with that kind of build your own cryptosystem approach.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sun, 17 Apr 2022 21:02:02 -0700

> secure than believed behavior isn't great. :)

That's not my argument (at least it's not the one that you're quoting)
:) I wasn't saying anything about what the *sender* should do.

The argument was: if the user receives data and they *can* decrypt it,
it's very hard for an implementation to justify refusing to show the
user the available cleartext, regardless of what the user's stated
policy has been.

If the message was weakly encrypted, it has already leaked -- the damage
has been done, and not-decrypting it at that point seems like just
gratuitously antagonizing the user.  I grant that some parts of E-fail
make good arguments for how overeager decryption can be dangerous.  We
should definitely defend against those use cases.   But if we just show
the user ciphertext, we're basically forcing them into trying to decrypt
it themselves, with whatever unergonomic tools they have available,
which itself can generate knock-on security issues.

> because these messages were silently accepted in spite of your key

I think "your message is secure" should be a distinct signal to the user
from "here is the cleartext of your message".  I'm not claiming that
every MUA does this properly right now, but if it doesn't, it seems like
a bug worth reporting.

If anyone interested in this kind of nuance, I recommend reviewing the
e2e-mail-guidance document over in the LAMPS WG, for example this part
seems relevant:

https://www.ietf.org/archive/id/draft-ietf-lamps-e2e-mail-guidance-02.html#reply-to-errant-encryption

(the doc is framed as mosty S/MIME, but it should be generally
applicable to PGP/MIME).

Regards,

   --dkg