Why PKCS#1v1.5 Encryption Should Be Put Out of Our Misery

Graham Steel
May 19, 2014

RSA Encryption with padding as described in PKCS#1v1.5 has been known to be insecure since Bleichenbacher's CRYPTO 98 paper revealed a chosen ciphertext attack. PKCS#1 version 2.0, published September 1998, proposed a new padding scheme based on OAEP and recommended the old scheme not be used in any new implementations.

This hasn't stopped PKCS#1v1.5 padding from being used just about everywhere. Take a look at this table of Smart Card support for example. One reason might be that Bleichenbacher's attack was though to be impractical: the worst-case analysis of the attack in the paper tells us that 2^20 chosen ciphertexts are needed, which gave rise to the name "the million message attack".

In fact the median case is much easier than that. And like all attacks, the attack algorithm has only got better. Building on advances by Klima, Pokorny and Rosa in 2003, our work published at CRYPTO 2012 showed that the median case for the standard oracle requires less than 15 000 messages.Still, there seems to be widespread belief that PKCS#1v1.5 is somehow ok if you use it carefully. For example, in this debate on the W3C crypto API bugzilla, one comment suggests that because TLS still uses RSA PKCS#1v1.5 then it must be possible to make secure protocols with it.

Let's look more carefully at how TLS "fixes" the attack. PKCS#1v1.5 encryption is used to encrypt a seed for the final session key, known as the "pre-master secret" (PMS), when it is sent from the client to the server. If the behaviour of the server decryption reveals padding errors, we can make the attack and so learn the session key.

The fix as proposed in RFC 3281 is that if a padding error occurs, we ignore it, generate a random PMS, and carry on. TLS also requires that both the client and the server demonstrate knowledge of the value of the PMS in order to create a signature that concludes the key establishment handshake. This is where the trick is effective: whether the PMS is a real one obtained from a tampered ciphertext, or a random one created after a padding error, it is unknown to the attacker, so the protocol fails in the same way. It is this "poor man's plaintext awareness" that has allowed security proofs for this mode of operation of TLS to be constructed by Jonnson and Kaliski and more recently by Krawczyk, Paterson and Wee.

Just because TLS does it, doesn't make it right

The debate on including PKCS#1v1.5 in the W3C Crypto API centred on its use as a mechanism for the Unwrap command that receives a ciphertext containing an encrypted key, decrypts it, and creates a new key on the client ready for use. If we make a "TLS-style fix" and substitute a random key in the case of a padding error, this won't necessarily prevent the attack: if the attacker can cause the resulting key to be used to, say, encrypt a known value, he can call the command twice and see if the resulting key is the same. The attack has been slowed down but not prevented.It might be possible to make a secure protocol, by using some kind of hash construction to demonstrate plaintext-awareness - but leaving in an explicit PKCS#1v1.5 decryption step means you're still open to an attack by some other side channel, for example by timing if you don't generate the random PMS in the case of a correct decryption (see this fix in ocaml-TLS) or if you screw up your buffer sizes for accepting the result (see this April 2014 security update to the Java TLS library).Since it's so easy to get wrong, and since we have OAEP which does plaintext awareness properly anyway, doesn't it make sense just to put OAEP in the API and leave out PKCS#1v1.5?

Matthew Green put it nicely: "PKCS#1v1.5 is awesome -- if you're teaching a class on how to attack cryptographic protocols. In all other circumstances it sucks."

The IETF seems to agree: from version 1.3, even TLS is dropping support for RSA.

By the way, if you're wondering whether your applications or hardware are using PKCS#1v1.5 and how secure it is, that's one of the many things we test with Analyzer.