Proposed New OpenPGP Cipher Block Modes Could Cause an Interoperability Disaster

There are currently 2 block cipher modes in the OpenPGP standard. There are serious proposals out there for 4 more which could bring the total to 6. Those interested in the details can refer to my editorial/rant: About the "OpenPGP Schism" (2023 Dec).

This article is specifically about the block cipher mode situation because I am sure I understand the possible implications in that case. The examples and arguments likely also apply to the introduction of any new incompatible mode. At the creation time of this article there where serious proposals for new incompatible signatures, keys and encryption methods.

This article is specifically about why this could lead to a bad result. There is a tendency to think in terms of the sort of negotiation possible with connection oriented protocols like TLS. Since negotiation is not possible in the OpenPGP problem space it is helpful to my point to use TLS as the counterexample here.

TLS negotiates the cryptography to be used at the start of a connection between two endpoints:

_{TLS connection}

So first the negotiation. Then an indeterminate period while the connection exists. A number of encrypted messages are transferred. After the encrypted messages are decrypted the encrypted version of the messages are thrown away. The message exists in the encrypted state for a very short time. On the order of milliseconds. After the connection ends there is no encrypted material remaining

The negotiation works like this:

_{TLS negotiation}

Program/app implementation instances 1 and 2 compare the lists of methods they support and identify any they have in common. Methods C, E and F here. So in this case the two instances have three separate possibilities available for interoperability.

Let's consider what happens to interoperability when a TLS implementation adds a new method. If that method is not supported anywhere else then the new method will produce no change in interoperability. If that method is supported by other implementations, then the odds of a successful encrypted connection are increased. In no way can the addition of another method in the TLS case decrease interoperability. The addition of another TLS method requires no consideration of interoperability at all. The worst that can happen is that interoperability will not change.

In the OpenPGP case an implementation decides on an encryption method from the methods it supports and then generates a message/file using that method. Method B in this example:

_{OpenPGP message creation}

After that the encrypted message/file takes on an independent existence. It might be put in an email and then spend time on an email server. It might be saved on a disk. It might be pasted into a web form. Those into old school spy craft might put it on a microSD card and stick it to the bottom of a park bench using used chewing gum.

_{The OpenPGP formatted message having an adventure in the Big City}

Eventually someone might attempt to decrypt the message/file:

_{Decryption time}

The encryption methods that a particular OpenPGP implementation supports will change over time. So there are two dimensions to interoperability here. We have to consider implementation instances available to the decrypting user at a particular time in the future. That might be decades from when the message/file was encrypted.

So implementation 1 (top row of the diagram) can decrypt a message encrypted with method B at t1 and t2. implementation 1 can no longer decrypt that message at t3. Perhaps the implementation dropped support or the user had to use an old, pre method B version of the implementation. Implementation 2 can only decrypt the message at t3. Perhaps implementation 2 gained support in a new revision. Implementation 3 has never supported method B and perhaps never will. It possibly is in maintenance mode and is not accepting new features.

Notice that the methods supported by implementation 1 at encryption time and implementation 2 at t1 have been chosen to be the same as the corresponding implementations in the TLS example. Where the TLS example provided 3 chances for interoperability, the OpenPGP example provides none.

Let's consider what happens to interoperability when an OpenPGP implementation adds a new method. If that method is not universally or close to universally supported everywhere else then the chances of interoperability decrease. As opposed to the TLS case, adding a new method in the OpenPGP case can and in most cases will decrease interoperability. The best that can happen is that interoperability will not change.

_{Range of possible interoperability change after the addition of a new method}

An OpenPGP implementation has the difficult task of predicting what methods the decrypting implementation supports when choosing a method to encrypt something. The OpenPGP standard has provisions for embedding cryptographic preferences in the PGP identity (PGP PUBLIC KEY BLOCK). There are proposals to extend the existing preferences to cover the block cipher modes we are discussing here.

The preferences are added to the PGP identity when the identity is created. As a result they are based on the methods that the creating implementation instance supports. In our example, the creating implementation was implementation 1 at t1. For this example we will assume that the supported methods were B A C E F. So the encrypting implementation picked a supported method from the list of preferences and ended up with method B. That turned out to be a not very good choice.

It's as if a web server continued to provide a list of supported TLS methods from the time it was first created 20 years ago. Interoperability problems would be inevitable. At the time this article was created, all 24 examples on my list of examples of interoperability problems caused by new modes existed in spite of the use of the preferences system. In theory a user could keep the preferences in their PGP identity up to date with the use of what would in practice be the GnuPGP key editor. In practice few could use that editor even if they could somehow come up with the intersection of the set of all modes used by their implementations.

For the common use of symmetrical single key encryption there is no identity. So OpenPGP preferences do not exist for this case. An implmentation has no guidance at all when deciding what method to use to encrypt a message/file.

This is the editorial section. This is what I think this all means…

1. The addition of a new mode should be avoided absent a strong and compelling reason for such an addition.
2. In the case of a cryptographic weakness it is preferable to find a way to resolve that weakness in a way that preserves compatibility.
3. It is OK to unilaterally implement a new method for decryption at any time.
4. It is not OK to unilaterally start encrypting messages using a new method at any time.
5. It is necessary to wait until there is widespread decryption support, as close to 100% as practically feasible, before emitting messages encrypted with a new mode. This will normally be years. It is necessary to at least wait for the old implementations to be updated everywhere.

Adding a new, incompatible mode, to the OpenPGP ecosystem turns out to be a difficult political problem that greatly overshadows any mere technical issues.