(In)security of ElGamal in OpenPGP

OpenPGP is a popular standard for end-to-end encrypted email, supported by many email applications for both PCs and mobile devices including Outlook, Thunderbird and Apple Mail. While popular, turns out that it is also insecure.

Here is why—and what can be done about it.

In a paper accepted for publication¹ in the proceedings of CCS 2021: ACM Conference on Computer and Communications Security, November 15-19, 2021, we describe a way OpenPGP’s encryption can be easily hacked. We communicated our results to the main OpenPGP vendors, who have patched or are in the process of patching their products in response. Be sure to timely install security updates of your PGP client to protect yourself against this vulnerability.

Lack of clarity leads to insecurity

The reason for weak security is that one of OpenPGP’s possible encryption mechanisms is ElGamal encryption. First described in 1985² by Taher Elgamal, it is one of the oldest and best studied algorithms used in public-key cryptography.

While ElGamal encryption can be reasonably well implemented using different parameter configurations, there is no clear standard on which configurations to use. For example, if two implementations with different parameter configurations interact with each other, in the best case scenario, from the security point of view, the two implementations will be incompatible and the communication will just not work. In the worst case scenario, the implementations will work together, but possibly in an insecure way.

We started inspecting OpenPGP code about nine months ago. Our aim has been to investigate a side-channel leakage condition—a subtle programming oversight that can be exploited in some scenarios, such as when a hacker and a victim are co-located on a cloud node. This led us to an unsettling truth: that independent of side-channel attacks, different parameter configurations used in the implementations of different vendors could lead to devastating attacks.

Specifically, some combinations of sender and receiver software effectively offer no security at all. The encrypted messages turn out to be easily decryptable by any mathematically skilled hacker with modest resources.

In such an attack, the hacker only requires the interception of ciphertexts—say, by snooping on a public network—and this is precisely what OpenPGP is meant to defend against. We refer to such attacks as cross-configuration attacks. Importantly, however, whether ElGamal encryption is secure or not depends on the implementation details. For some pairs of vendors, we could break the ciphertexts directly, for others we could break them if supported by side-channel leakage. And for the last group, it seems that the security is fine.

Taking action

To assess how many OpenPGP users were affected, we checked more than two million publicly registered keys. The good news is that only a couple thousand keys were affected—about one per thousand. The bad news, though, is that not all OpenPGP keys are publicly registered, meaning the owners of those keys should pay extra attention.

To mitigate this risk, we recommend that you update to the latest version of GPG. If you are a user of a different OpenPGP client, IBM provides a tool to check whether your software is affected.

And if you use an ElGamal key, the messages you receive or have received may also be at risk. As there is currently no scalable way to reliably test the security of ElGamal keys, we suggest revoking them and generating fresh RSA or ECC keys instead. Public keys generated by GPG are not at risk, so you do not need to revoke your ElGamal keys if you know they were generated by GPG or one of its derivatives.

Several weeks ago, our IBM Research team notified the main OpenPGP vendors about this issue and they have been working on fixing their implementations.