In Secrets & Lies (2000), Schneier describes a chosen ciphertext attack on the public key under PGP:

"Since RSA and ElGamal are malleable, known changes can be made to the symmetric key that is encrypted. This modified (encrypted) key can then be sent along with the original message. This opens up the possibility of related-key attacks on the symmetric algorithms. OR, a weak ciphertext can be found whose decryption under the symmetric key algorithm reveals information about the modified key, which then leads directly to information about the original key." [P. 327-328. Schneier, Bruce. Secrets & Lies. 2000]

Could you explain (a) how this attack works and (b) whether it's still feasible in 2016?

  • 1
    $\begingroup$ You might also wonder if the attacks are really that practical for PGP. PGP is often used to directly convey messages from one person to another. This makes statistical analysis over many messages tricky; after a few falsified messages I'd guess that the persons you want to attack would raise an alarm. That leaves fully automated systems. For those the fact that in general no ciphertext authentication is performed in the first place is much more of an issue. That's at least what I suspect is the most dangerous part about (Open)PGP. $\endgroup$
    – Maarten Bodewes
    May 22 '16 at 10:51

TL;DR: This attack extends the standard chosen ciphertext attacks on RSA and ElGamal to the hybrid encryption setting, but requires some huge IFs which no longer even have a slight possibility of being fulfilled.

To understand this attack, one first needs to understand how data is encrypted for PGP according to this snippet. Let's assume you have a recipient key $pk$, a message $m$, an encryption function $E_{pk}( \cdot )$ (either textbook RSA or textbook ElGamal), a random, symmetric key $K$ and a well-known symmetric cipher $E_K( \cdot )$. Now form the ciphertext $C$ as $C=E_{pk}(K)||E_K(m)$ with $||$ denoting reversible pairing (e.g. you can extract both parts later on).

The next step is to note that you can arbitrarily, multiplicatively modify the message in textbook RSA and textbook ElGamal, by performing specific (simple) operations on the ciphertext - only knowing the public key. Note that you can apply the two linked attacks on the encrypted "header" $E_{pk}(K)$ from above.

Now you use these attacks and change the $K$ value to $K'$, preferably in a clever fashion. If the cipher is suceptible to related-key attacks you generate the related keys for this attack this way and then apply your attack on it, possibly by abusing the user as a decryption oracle. Now it also may be, that you stumble across something a ciphertext that looks weak under the new key and allows you to deduce some information from the cipher text about the key, thus easing a brute-force attack.

Is this attack still feasible nowadays? As always, it depends.
The similar encryption mechanisms RSA-KEM and ECIES use a hashing function in between the symmetric cipher and the public key encrypted symmetric key, so they are immune.
If you use RSA-OAEP or an IND-CCA2 secure variant of ElGamal, you're also safe, as the malleability property no longer applies.
Additionally, authenticated (symmetric) encryption also makes this sort of attack much harder, as you first need to find a related key, that doesn't yield an invalid tag and thus reduces you amount of information from "a full decryption under this related key" to "a message whether decryption succeeded under this related key" which is likely not enough for a recovery attack.

If your cipher is (sufficiently) resistant to related-key attacks and doesn't have "weak ciphertexts", you're also safe. Most decent modern ciphers are "sufficiently safe" against related-key attacks, even AES which had some devestating experiences with these attacks is still safe enough.

It's especially the last mitigation that applies nowadays. Nearly everybody is using AES or a comparably strong cipher and thus the required related key attacks do not exist and this is more of a theoretical weakness, than a practical one.

  • $\begingroup$ Thank you for taking the time to write this answer; it seems to me this attack is nigh unfeasible since no PGP implementation will use textbook RSA or ElGamal encryption (or allow malleability in general) $\endgroup$
    – Marcel
    May 22 '16 at 19:29
  • $\begingroup$ @Marcel, I do actually think implementations used to use malleable RSA / ElGamal variants in the past (notice how hard it is to find a IND-CCA2 secure ElGamal variant?), I don't know whether they still do it, but it doesn't matter anyways if they use half-way decent ciphers / hash the encoded value and if you textbook-RSA-encrypt only short keys, you also have other problems at hand. $\endgroup$
    – SEJPM
    May 22 '16 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.