Subject: [Openpgp-dt] GCM in OpenPGP, and cross-algorithm attacks

From: Daniel Huigens <[email-masked]>
Date: Tue, 23 Nov 2021 16:47:58 +0000

Dear Design Team,

I've talked with Lara Bruseghini about GCM in OpenPGP, and she pointed
to this paper: [1], which introduces a "backwards compatibility"
attack. The idea is that if you have a decryption oracle for CCM or OFB
(in their case) or CFB (in our case), you also have a decryption oracle
for GCM. The former can happen if an implementation still supports
Symmetrically Encrypted Data packets, or has an insecure implementation
of MDC, e.g. [2] (this is not intended to call anyone out, but to point
out that MDC is a bit fragile), and in general we may not want to rely
on the security of MDC for the security of GCM.

This attack only works if you can convert a GCM encrypted message to
look like a CFB encrypted message, which I believe is possible for
example with a SKESK, but not with a PKESK.

The paper proposes in section 3.2 two general countermeasures: proper
key separation to ensure that a given key can only be used with one
encryption mode, or passing the key through a KDF together with an
algorithm identifier, to ensure the same thing.

One way to do the former (and additionally prevent converting encrypted
messages between different AEAD modes, which may be advantageous if
additional similar attacks are found) would be to move the AEAD mode
identifier (and symmetric algorithm identifier?) into the encrypted
session key, similar to what was done for the symmetric algorithm
identifier for CFB. Even though I used to think that that was quite
ugly, it does seem to have some security advantages in this case.

So this would mean, for example:

V4 SKESK: Enc(symmetric algorithm || session key)
V5 SKESK: Enc(symmetric algorithm || AEAD mode || session key) -- currently doesn't exist
V4 PKESK: Enc(symmetric algorithm || session key)
V5 PKESK: Enc(symmetric algorithm || AEAD mode || session key) -- currently Enc(session key)

For the V5 SKESK, we may also need to adjust the input to the S2K
algorithm (e.g. pass the "outer" symmetric algorithm and AEAD mode), to
properly separate the keys, since we don't have a reliable way to know
whether the passphrase-derived key was meant to be used with CFB or AEAD
(I'm not 100% sure about this part, will have to look into it further).

---

Then, regarding the IV, GCM's IV length of 12 octets is quite short, and
if we use 8 octets of that as counter, one could argue that the entropy
becomes quite low, and collisions more likely. One way to counter (ahem)
this at the spec level, would be to limit the amount of chunks to 2^32
for GCM messages, and/or say that a session key must not be reused too
often for GCM messages, for example.

If the above seems reasonable to you, I'd be happy to create a series of
merge requests to that effect.

Best regards,
Daniel Huigens

[1]: https://www.ndss-symposium.org/wp-content/uploads/2017/09/10_4_0.pdf
[2]: https://gitlab.com/sequoia-pgp/sequoia/-/issues/693

---

From: Daniel Huigens <[email-masked]>
Date: Tue, 23 Nov 2021 16:57:17 +0000

Sorry, I wrote that from memory and mixed up the packets, that should be:

V4 SKESK: Enc(symmetric algorithm || session key)
V5 SKESK: Enc(symmetric algorithm || AEAD mode || session key) -- currently Enc(session key)
V3 PKESK: Enc(symmetric algorithm || session key)
V5 PKESK: Enc(symmetric algorithm || AEAD mode || session key) -- currently doesn't exist

---

From: Justus Winter <[email-masked]>
Date: Wed, 24 Nov 2021 11:42:42 +0100

Hi,

> So this would mean, for example:

[I inserted the fixed snippet.]

> V5 PKESK: Enc(symmetric algorithm || AEAD mode || session key) -- currently doesn't exist

I can see how that helps for the SKESKv5 because it uses AEAD, but I'm
not entirely convinced that it helps for PKESKv5 because I don't think
PK algorithms ensure integrity.

> often for GCM messages, for example.

Note that in general, session keys are not re-used in OpenPGP, so I
don't think this is a big concern.

Session key re-use can be used to implement robust reply-to-all:  If you
receive a message encrypted for N recipents, but you don't have
everyone's certificate, you can re-use the PKESK packets and session key
to reply.

But, if we're tossing around the idea of introducing PKESKv5, we can
improve upon that: instead of re-using the session key as-is, we ratchet
it.  We have some ideas on how to do that, but I need to find the notes
again.  Iirc it involved adding some kind of counter or nonce to the
PKESK packet that is used to frob the session key.

Justus

---

From: Daniel Huigens <[email-masked]>
Date: Wed, 24 Nov 2021 12:27:11 +0000

Hi :)

> PK algorithms ensure integrity.

I believe the idea is to take an existing message (including PKESK), and
modify only the AEAD encrypted data into CFB encrypted data. If the
(decrypted) PKESK indicated that it should be used with AEAD, that
would prevent it, I think (unless you're saying that due to insufficient
integrity, the PKESK could be modified as well - I'm not sure if that's
actually possible, we'd have to look into it. It does have two bytes of
checksum, at least, thought that's indeed not very impressive.)

> PKESK packet that is used to frob the session key.

Yeah, I wouldn't be opposed to this, though at that point we might also
want to think about providing forward secrecy, e.g. using a double
ratchet? Though that would be a larger undertaking, so perhaps both of
these should be done in the next iteration of the spec?

Best,
Daniel

---

From: Justus Winter <[email-masked]>
Date: Wed, 24 Nov 2021 13:37:09 +0100

> checksum, at least, thought that's indeed not very impressive.)

That is precisely what I'm saying.  I'm not saying it is easy or
possible, but we shouldn't be relying on a property that the PK
encryption algorithms simply don't provide.

> these should be done in the next iteration of the spec?

shameless plug:
https://gitlab.com/sequoia-pgp/openpgp-dr/-/tree/wip-openpgp#signals-double-ratchet-algorithm-for-use-in-openpgp

Having said that, forward secrecy is quite a paradigm shift, but simple
ratcheting seems way less complicated and fix a real problem.  In fact,
I've gone ahead and opened an issue for that:

https://gitlab.com/openpgp-wg/rfc4880bis/-/issues/57

Justus

---

From: Paul Wouters <[email-masked]>
Date: Wed, 24 Nov 2021 09:41:16 -0500 (EST)

> https://gitlab.com/openpgp-wg/rfc4880bis/-/issues/57

It is an interesting question on whether this is in scopr for the
crypto-refresh, or if this is a separate document with an extension.

If it changes many existing bits, it might be better to pull it into the
core spec. If it is a less invasive add-on change, it could also be put
into a seperate RFC. If possible, I probably prefer a seperate RFC, as
we also have some operational issues with PFS. What to do if the
recipient no longer has their ratchet material and you need to fall back
to the regular key? And how to prevent this being used as a downgrade
attack?

Paul