Analysis of EME PKCS1 v1_5 padding bug in OpenPGP.js in the case of Mailvelope

Thomas Oberndörfer edited this page Apr 8, 2014 · 1 revision

by Trevor Perrin, OTF Red Team

IMPACT:

If a Mailvelope user sent different encrypted mails to Bob and Charlie in the same "session" (i.e. without closing the browser in between), Bob can decrypt Charlie's email (or vice versa) if Charlie's PGP key satisfies a specific "at-risk" condition.

Probably fewer than 1/1000 PGP keys are "at-risk". An RSA encryption key is at risk if its modulus size is >= 256 times its public exponent. At-risk keys mostly have very large moduli (>4096 bits) or small exponents (e.g. 3).

ANALYSIS:

Suppose Alice sends RSA-encrypted messages to Bob and Charlie. Chrome does not provide a cryptographically-strong PRNG for Math.random. So by looking at the RSA padding he receives, Bob could recover the Chrome PRNG state being used for the Mailvelope context, and then calculate it forwards (or backwards) to figure out the RSA padding Alice used for Charlie.

An attack due to Coppersmith [1] makes it possible for an attacker to decrypt an RSA message with known EME-PKCS1-v1_5 padding if the size of the RSA modulus (N) is greater than the RSA public exponent (e) times the size of the encrypted symmetric key (256 bits since the relevant versions of OpenPGP.js always choose AES-256).

This condition is not met by most PGP keys. According to [2], 99% of RSA keys from PGP keyservers have e >= 17, so are safe even with 4096-bit RSA keys. To make a better estimate, I looked at 12823 RSA keys from a PGP keyserver dump [3]. Only 9 were at-risk, 5 of them 8192-bit keys with e=17. Of the 9 at-risk keys, only 2 had been generated after the year 2000, suggesting that modern software prefers larger exponents. The majority of PGP encryption keys in the data were Elgamal, not RSA.

All this suggests that the prevalence of active, "at-risk" PGP keys is less (perhaps much less) than 1/1000.

Nonetheless, this is still a serious risk, since the attack against "at-risk" keys is likely to be practical (see the efficiency analysis in [4]).

[1] http://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf

[2] http://eprint.iacr.org/2012/064.pdf

[3] http://keyserver.borgnet.us/dump/

[4] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.8495&rep=rep1&type=pdf

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.