Legacy Encryption Downgrade Attacks against LibrePGP and CMS: Some Comments

Understanding parts of this discussion require knowledge of how PGP does authentication. There is an article for that: The Why of PGP Authentication.

This is the paper under discussion here:

• Legacy Encryption Downgrade Attacks against LibrePGP and CMS

What is discussed in the paper is not the sort of thing someone familiar with, say, TLS would consider a downgrade attack. That would involve some sort of trickery during the negotiation phase. PGP doesn't and can't have a negotiation phase. Instead the PGP related parts of the paper are about using the SED encryption mode in aid of either:

• Detecting a small number of possible plaintexts in a message encrypted via LibrePGP OCB mode.
• Adding or changing some plaintext in a message encrypted via LibrePGP OCB mode.

LibrePGP is a proposal for the modification/extension of the existing OpenPGP standard (RFC-4880, RFC-6631). The SED (Symmetrically Encrypted Data) mode is completely unrelated to the LibrePGP OCB mode and comes from the existing OpenPGP standard. I refer to the SED encryption mode as OCFB (OpenPGP Cipher Feed Back) in other articles but will call it SED (the name of the OpenPGP packet) mode here to be compatible with the paper under discussion.

We want to be able to encrypt things in a way compatible with the OCB encryption mode. This is a simplified depiction of OCB¹⁾:

_{OCB encryption mode}

So each block of plaintext gets scrambled with the Δ (delta) value with an exclusive OR function (⊕), is encrypted with the encryption key and is again scrambled with the Δ value to produce a block of ciphertext. Note that the Δ value is the same at the input and output of the block cipher encryption in the OCB case. OCB is an instance of exclusive OR, encrypt, exclusive OR XEX.

The goal is to use the SED decryption mode to create a OCB message out of the intercepted OCB message that can be used to determine aspects of the intercepted OCB message. We will ignore the OpenPGP prefix here so we end up considering the generic CFB (Cipher Feed Back) mode that is left:

_{CFB decryption mode without the SED header}

CFB mode uses the block cipher encryption operation for decryption, which is why this can possibly work in the first place. Here is the same diagram with the labels changed to represent our ultimate goal:

_{CFB decryption mode (renamed inputs and outputs)}

That looks promising but the plaintext from the next stage is getting exclusive ORed into our ciphertext. This is what we can do:

_{CFB decryption mode (modified to perform OCB encryption)}

Let's consider just the leftmost column for the explanation. First we exclusive OR Δ0 with Plaintext0 for OCB. Then we feed that into the CFB function. The CFB function helpfully does a block cipher encryption operation for OCB but unhelpfully exclusive ORs Plaintext1 and Δ1 into the returned output. We know what Plaintext1 and Δ1 are as we provide them. If you exclusive OR in a value and then later exclusive OR in the same value then the two values cancel out. So we fix up the output of the CFB function by exclusive ORing in Plaintext1 and Δ1. We finish by exclusive ORing in the correct Δ value for OCB (Δ0).

We have created a encryption function for a particular block encryption mode by using the decryption function from an entirely different mode. I have to say, that's pretty cool. This example is only representative. There is a lot of omitted detail. I will not be discussing the actual attack further so you are encouraged to refer to the paper for those details. Going into the following discussion, the only thing you need to take from here is that access to the SED mode is critical for the attack.

It might not be clear how being able to encrypt in a particular mode could lead to an exploit. The general idea is that the attacker might be able to trick the victim into decrypting a message and then sending the decrypted message back to the attacker. One suggested approach is to make it so that the decrypted message is some sort of gibberish so that, say, an email user might send the gibberish back to the attacker with a query²⁾. Another suggested approach is to trick the user's client software into decrypting the attacker submitted message before sending the decrypted message back to the attacker. The attacker might, say, send an encrypted HTML formatted email message to the victim that would load an image link with the decrypted material embedded in the link³⁾.

The abstract of the paper states (irrelevant bits removed):

The attacks thus demonstrate that CCA2 security is not achieved by the LibrePGP … encryption in the presence of a legacy cipher mode decryption oracle.

“CCA2” means adaptive chosen-ciphertext attack which is a particular attack model. In this case, “legacy cipher mode decryption oracle” means the SED decryption mode we talked about in the previous section.

The CCA2 attack mode is well defined in practice. The CCA2 attack model assumes, among other things, that the attacker can get a copy of the encrypted material and that the attacker can then get the victim to decrypt a large number of modified versions of that encrypted material for them.

My complaint is that this is an odd way to describe the weakness here. If someone hears that a particular encryption mode has not achieved CCA2 security they will assume that it is an inherent weakness with the mode itself. Adding on the provision that an entirely different mode is involved somehow would not produce understanding of what is actually going on here; that the extra mode is actively required to perform the exploit.

One of the paper's significant references ⁴⁾ uses the term “backwards compatibility attacks” to describe the sort of thing described in the paper. The use of that term would have been less confusing. Something to the effect of: the combination of the LibrePGP OCB mode and the OpenPGP SED mode can result in a backwards compatibility attack.

The structure of the statement in the abstract also causes the risk that the requirement for the legacy cipher mode might be dropped in retellings. This statement showed up in a random report found on the web⁵⁾:

Formally, LibrePGP AEAD-encrypted messages do not achieve IND-CCA2 security.

The reader was expected to figure out the rest by context. The fact that the report was written by the same authors as the paper under discussion I think supports my point. It is best to not make statements that are very likely to be taken out of context or misinterpreted. There is no proof presented in the paper that “LibrePGP AEAD-encrypted messages” (LibrePGP OCB encryption mode) do not achieve CCA2 security, particularly under the indistinguishability model implied by the use of the “IND” and “formally” terms. It is fairly clear from context that the rules of the indistinguishability game do not allow the use of entirely different modes. Otherwise, it would be possible to prove that any mode did not achieve CCA2 security simply by proposing a new mode for that purpose. It would be in a sense cheating the game. So the statement would seem to be invalid by itself.

This vulnerability requires the availability of a second encryption mode to work. So the question of the severity of the vulnerability and even if it is a vulnerability hinges on that availability.

As has been pointed out⁶⁾ some (most?) implementations don't really make the SED mode available in the first place. But let's ignore that aspect for now and assume it is available.

The vulnerabilties here are stacked. You have to get though one before you can attempt the other. When considering stacked vulnerabilities the first vulnerability can't be too serious by itself and should be less serious than the second. If, for example, you had a case where the first vulnerability had to decrypt the ciphertext and supply it to the attacker then would not even bother to consider the second. The second vulnerability would be irrelevant.

That is literally what is happening here. The attack from the paper requires that the user or the user's client receive a message, decrypt it and then send it back to the attacker. For this case there is no point in worrying about the second vulnerability before resolving the first. Once you have resolved the first then the second goes away. All that cool stuff about using an decryption function as a encryption function never has a chance to be meaningful. So it seems that there is no attack here against the LibrePGP OCB mode that could ever be considered significant in some way.

From the paper:

However, note that conducting this attack against LibrePGP-based email encryption is not realistic, since an email client that is vulnerable against our attacks would also expose the vulnerability of SEIPD packets being downgradeable to SED Packets, which was exploited in the Efail attack ⁷⁾. This vulnerability can be exploited much more straightforwardly, i.e., with only a single modified ciphertext. Accordingly, for any application that also supports OpenPGP SEIPD packets, which clearly is the case for current email clients, the vulnerability of SEIPD packets would be the much greater problem.

This states that a “downgrade” from SEIPD to SED is something that the maintainer of an email client would have to be concerned with. I do not believe that to be true. SEIPD (Symmetrically Encrypted Integrity Protected Data, OCFB-MDC) is from the existing OpenPGP standard. The resistance designed into SEIPD against a modification to SED reduces the probability of success to 0.000015 (1/(2^16)). That would not be a potential problem for the medium of email. In the presence of the “quick check” (the most common case) this sort of modification is not known to be possible at all. Of course, email client maintainers might not know this and as a result the argument concerning practically could still be valid.

This in turn triggered the second peeve. The paper's attack involves sending unauthenticated SED encrypted messages to a victim. The paper at no point addressed the effect of PGP authentication. It was not even mentioned in passing. That seems to be very common for this sort of discussion and is fairly inexplicable.

If a client gets an unauthenticated message then that is suspicious to the extent that the receiver can't be sure if they know the sender. If that message is unauthenticated and encrypted then that is particularly suspicious in that the sender is hiding the message from things like malware detectors but is still anonymous. Here is a list of different incoming message configurations ordered from least suspicious to most suspicious:

1. authenticated, unencrypted or encrypted with either SED or SEIPD
2. unauthenticated, unencrypted (e.g. regular email)
3. unauthenticated, encrypted with SEIPD (provides an integrity check)
4. unauthenticated, encrypted with SED (provides no integrity check)

At this point in time, use of the SEIPD mode is fairly ubiquitous. So seeing the SED mode is a bit odd in any case. The SEIPD mode was specifically created to provide an integrity check for unauthenticated (unsigned, anonymous) messages. So it is very suspicious to see a unauthenticated SED mode encrypted message. Rather than any unwarranted concern about messages modified from SEIPD to SED, a client should instead deal with the unauthenticated SED encrypted messages critical to this attack simply on the basis of suspicion. Any unauthenticated but encrypted email messages should be noted as suspicious. The forwarding of such messages should be done with the greatest care or even prevented entirely. The opening of any attachments from such messages should be discouraged or prevented. The suspicious message should not be passed along to a complex decoder such as a generic HTML interpreter.

… Or less complicated, a client could simply ignore unauthenticated but encrypted with SED messages as being not worth the bother to support. That would prevent the attack from the paper and some others at a slight cost in interoperability.

I strongly suspect that the cause of my peeves originally came from some misleading legends caused by EFAIL.

By the way, I am not aware of any place in EFAIL where “the vulnerability of SEIPD packets being downgradeable to SED Packets” was actually shown to be usable for the EFAIL attack. There were merely references to discussion that it might be possible.

The attack described in the paper has implications for the unfortunate OpenPGP standards schism. One of the factions (RFC9580) is proposing an extra operation specifically intended to prevent this sort of attack. The other faction (LibrePGP) considers this extra operation to be pointless complexity. While both proposals have the OCB mode, the extra operation prevents interoperability.

If you end up believing that the attack from the paper is a valid vulnerability then you might think that the extra operation is worth the cost. Otherwise you might not.

In Reference A (Insecurity of OpenPGP SEIPD packets under adaptively chosen ciphertext attacks) the paper states:

A second shortcoming of SEIPD packets is that they do not achieve CCA2 security, i.e. are vulnerable to adaptively chosen ciphertext attacks, even when not considering downgrade attacks to SED.

This is actually what first caught my attention. SEIPD has been around for something like a quarter of a century. A successful attack on the fundamental security would be a huge deal.

My excitement was short lived however. From the reference:

LIT-hdr||message||MDC(LIT-hdr, message)

This is incorrect as shown. It omits the MAC (Message Authentication Code) secret key. It should be (with the MAC secret key denoted as “K2”):

K2||LIT-hdr||message||MDC(K2||LIT-hdr||message)

I don't get any great amount of credit for spotting this. That is because I know that this exact same misunderstanding has happened before. When the security of the SEIPD encryption mode was being evaluated it turned out that the specification omitted the MAC key. So there was more discussion about the attack engendered by this omission than there might have been otherwise⁸⁾. Perhaps the specification still needs some work to make this clearer.

A definite statement is required here: this paper does not show that the SEIPD encryption mode does not achieve CCA2 security⁹⁾.