Algorithms can’t be patched

Heartbleed was a disaster, but at least the software could be patched to eliminate the vulnerability. Most of the time, like with Heartbleed, vulnerabilities in crypto software can be patched—dedicated hardware can’t be patched, though.

Crypto algorithms are a bit like hardware: if a standardized algorithm has some vulnerability yet isn’t totally broken, you can’t do much about it except avoid using it, or try to minimize the vulnerability’s exploitability.
The best example is something called “PKCS #1 v1.5” (a.k.a “PKCSv1.5”), a standardized construction to encrypt with RSA.

In 1998, then-Bell-now-Google researcher Daniel Bleichenbacher found a clever attack against PKCSv1.5 The so-called Bleichenbacher attack allows an attacker to decrypt a given ciphertext, after sending a bunch of carefully crafted ciphertexts to the vulnerable system and learning whether these are valid ciphertexts. Indeed, PKCSv1.5 decryption will reject as invalid ciphertexts whose underlying plaintext doesn’t match a specified format. And many systems will behave differently upon receiving such an invalid ciphertext, for example by aborting their operations, sending an error message, and so on.

The Bleichenbacher attack is bad, but not Heartbleed-bad, so PKCSv1.5 wasn’t totally eliminated but instead cryptographers recommended the most recent standard, OAEP, not vulnerable to Bleichenbacher’s attack.

Obviously, and for a variety of more or less valid reasons, people kept using the not-so-secure PKCSv1.5 RSA encryption. And of course, many systems were found to be vulnerable to Bleichenbacher’s attack; among many others,

• TLS implementations, in 2003
• Payment smart cards, in 2009
• Various hardware tokens and HSMs, in 2012
• More TLS implementations in 2014
• TLS implementations again, this time in the DROWN attack, in 2016
• And again TLS implementations, in the ROBOT attack, in December 2017

And that’s only the tip of the iceberg. Security auditors and labs have all found and exploited vulnerable PKCSv1.5, sometimes in creative ways. I bet you that next year, to celebrate the 20th anniversary of Bleichenbacher’s attack, we’ll still find critical systems to be vulnerable.

So, seriously, stop using PKCSv1.5. If you need RSA encryption, just use OAEP, a.k.a. PKCSv2.1.

Oh but wait… OAEP implementations can also be vulnerable to an attack very similar to Bleichenbacher’s.

Should we just avoid RSA encryption altogether? Or use RSA in CBC mode? (WARNING: this is a joke don’t do it)