A couple of days ago I wrote about universal ElGamal ciphertexts and about the importance of digital signatures. Although the story of a rather unremarkable piece of malware served us well as an example, it was not an example a reader could easily relate to or get their hands on. This time, I provide real-world examples in the form of actual messages and keys made of genuine bits.

ElGamal encryption is a mandatory part of OpenPGP, a comprehensive cryptographic standard also used to secure electronic mail. Until about 2009, ElGamal was the default public-key encryption method of GNU Privacy Guard, a free software implementation of OpenPGP. This text is about universal OpenPGP ciphertexts, fake encryption keys silently disabling encryption and about the importance of digital signatures.

Encrypted broadcast

This file can be decrypted by any OpenPGP ElGamal private key with a 2048-bit modulus. The message uses the integer one as the first component of the ElGamal ciphertext. Let us call such a ciphertext degenerate. It is independent of any ElGamal parameters, a degenerate ciphertext really is a rather clumsy way to send plaintext around.

The above ciphertext is built with an all-zero "wild card" recipient key ID. This optional OpenPGP feature allows to omit the recipient key ID from the message. The recipient would then try all the available secret keys until one decrypts the message. This feature is not always enabled by default. Some versions of GnuPG, for example, require the switch --try-all-secrets.

The eight-byte zero ID can easily be replaced by a specific ElGamal subkey ID that belongs to a particular recipient.

Introducing Alice

Alice wishes to start using OpenPGP. She generates fresh keys for DSA signatures and ElGamal encryption and exports her public key in order to share it with her friends. For illustration purposes, I am able to share her private key, too.

Knowing that the ID of her ElGamal encryption subkey is 0xB4F970E9525E326C, anybody can easily create degenerate encrypted messages for Alice, such as this one. Her OpenPGP software will successfully decrypt the message, Alice will not be informed that the ciphertext is degenerate and the message was in fact readable for everybody.

It is not much of an issue that anybody could read the message content, the problem is that Alice does not know. Observe that there is little she can do to prevent others from sending her plaintext messages. Even if she receives a message that is properly encrypted under her key, the sender is able to simply publish the plaintext. Yet, upon receipt of an encrypted message, Alice should be able to expect that the message has remained secret. A degenerate ciphertext does not stand a chance. OpenPGP software probably should not indicate that a message is encrypted when in fact it is not.

The woman in the middle

Alice wishes Bob could send her encrypted messages, she therefore hopes to share her public key with him. Eve wants to read the encrypted messages Bob sends to Alice. Eve could try to mount the usual (wo)man in the middle attack. She would generate a fresh encryption key and convince Bob that the key belongs to Alice. Whenever Bob would send an encrypted message to Alice, it would actually be encrypted under Eve's key. Eve would decrypt the message and then re-encrypt again for it to decrypt properly after reaching Alice. Eve might have to work rather hard not to get detected, especially if Bob and Alice commonly use several networks or devices. If a single message slips past Eve, Alice and Bob will likely find out.

The lazy woman in the middle

If Eve could swap Alice's encryption subkey for a key that only generates degenerate ElGamal ciphertexts, she could still read what Bob sends to Alice without the need to re-encrypt anything. For this to work transparently, Eve needs an ElGamal encryption subkey with \(g=y=1\) and an ID equal to that of the actual Alice's ElGamal key. Eve might need to try up to \(2^{64}\) degenerate keys to get a match. The task does involve some computation, but the complexity should be manageable for a determined attacker. I have helped Eve to come up with the subkey, note that the ID is equal to the one Alice uses, i.e. 0xB4F970E9525E326C.

Eve wants Bob to import the real Alice's DSA signing key. That way, Bob will be able to verify genuine signatures by Alice. Eve therefore strips the real ElGamal encryption subkey from Alice's public key to obtain alice_primary.asc.

She then generates a fresh primary DSA key, copies Alice's user ID and adds the degenerate ElGamal subkey, getting eve_public.asc. She may then combine the two primary keys into a single file for Bob to import. If Bob falls for it, all the messages he sends to Alice will be degenerate. Neither Bob nor Alice will notice anything. Eve has succeeded in disabling encryption for all the messages from Bob to Alice.

The parallel collision

The above approach leaves Bob with two distinct primary DSA keys assigned to Alice. Bob can get suspicious about the two distinct key IDs and he might want to investigate the matter with Alice. For good measure, Eve can generate her DSA primary key to have the same key ID as the original key by Alice and combine all the keys in a single file. Now Bob still sees two DSA keys belonging to Alice. The keys differ, but their IDs match. If Bob wanted to check the IDs with Alice, she would be happy to confirm that all the IDs Bob imported do indeed correspond to her keys.

Support in software

I have tested degenerate ElGamal ciphertexts with GnuPG version 2.1.17, OpenKeychain version 4.1 and the non-free Symantec Encryption Desktop 10.4.0. All three implementations were happy to decrypt degenerate ciphertexts.

All the programs can also import a degenerate encryption subkey. GnuPG and OpenKeychain are then able to encrypt with that key, producing degenerate ciphertexts. In Symantec Encryption Desktop, the encryption fails.

Symantec Encryption Desktop and OpenKeychain refuse to import the two different primary DSA keys with identical IDs, GnuPG accepts them.

What the standard says

I was a bit surprised that degenerate ciphertexts are not at least flagged as suspicious during decryption. As it turns out, such a ciphertext would actually be valid according to the OpenPGP specification. The chance that a degenerate ciphertext is produced is very small. It can only happen if \(y=g^x\) within the ElGamal public key generates a proper subgroup of integers modulo \(p\), or equivalently, if the secret exponent \(x\) is not coprime to \(p-1\). GnuPG and OpenKeychain make sure not to generate such keys.

Degenerate keys with \(y=g=1\), on the other hand, do violate the standard and should be rejected as invalid. More so the encryption key I generated for Eve, where \(p\) is not even prime.

Conclusions

Eve's attack has no impact on those who use OpenPGP properly. Bob has to verify that the key he imports does indeed belong to Alice. If he decides to trust any random public key he comes across, he is asking for trouble. The intuition, that a key that works is probably fine, is wrong and dangerous. Fortunately, modern OpenPGP software provides Bob with abundant warnings and encourages him to actually verify keys.

Bob must make sure that the public key he is importing is the same exact key Alice exported. Ideally, they would compare complete keys and all the parameters within. Even comparing key fingerprints is better than nothing. Identical key IDs, short or long, have never been sufficient.

If Bob trusted some reasonable people already, maybe he could rely on the OpenPGP web of trust. This is a strange piece of advice from a person with no signatures on his public key. Let us sign some keys, then.