(No Ratings Yet)

Loading...

• Facebook
• Twitter
• LinkedIn
• Mail

December 4, 2018 Comments closed

Stop using RSA key exchange

in Everything Encryption

“The safest counter-measure is to deprecate the RSA key exchange and switch to (Elliptic Curve) Diffie-Hellman…”

Today we’re going to talk about why you should stop using RSA key exchange. One of the biggest weaknesses in the SSL/TLS ecosystem is its backward compatibility. While the rest of the internet moves forward a few stragglers can put the entire internet at risk. Last week, a group of six researchers published a paper that details a new variant of an old exploit called Bleichenbacher’s CAT, which highlights that weakness.

So, let’s spend a little time unraveling the paper, its implications and then we’ll talk about why you should definitely not be using RSA key exchange.

Let’s hash it out.

Who is Bleichenbacher and why should I care about Bleichenbacher’s CAT?

Let’s start by discussing one Daniel Bleichenbacher, a Swiss cryptographer whose name is affixed to several exploits. Normally, that would make him one of SSL/TLS’s greatest enemies, but this is cybersecurity and he was using his powers for good so now he’s famous. Or, at least as famous as cryptographers get.

In 1998, at 24 years of age, Bleichenbacher demonstrated a viable attack against RSA encryption implementations that were using the PKCS#1 v1.5 encoding function. 19 years later, the ROBOT attack, which stood for the Return of Bleichenbacher’s Oracle Threat, made slight variations on the original exploit and threatened sites’ TLS implementations again.

Both of these exploits – as well as the modifications that came between them – targeted the RSA cryptosystem, and while the 1998 attack was addressed and RSA continued being widely used, by 2017 the writing was on the wall: stop using RSA key exchange.

And as if you needed anymore reason, now we have Bleichenbacher’s CAT (Bleichenbacher’s Cache Attacks on TLS Implementations), a newly announced exploit that plays on the same concepts and further undermines RSA. Even one of its creators, Adi Shamir – the S in RSA – who contributed to the paper, agrees you should stop using RSA key exchange.

Tell me more about Bleichenbacher’s CAT

Bleichenbacher’s CAT is a variation on the original exploit published by Daniel Bleichenbacher.

As each related exploit has been presented there have been attempts to address the issue and try to fix RSA, but the only surefire way to prevent this exploit from continuing to return is to stop using RSA key exchange completely.

The issue stems from PKCS #1 v1.5, we wrote an entire article about encoding and the various formats of SSL/TLS certificates, which I suggest reading, but the abridged version is that PKCS1 stands for Public-Key Cryptography Standards #1, which provides the definitions and recommendations for the RSA cryptosystem.

Version 1.5 is actually outmoded, we’re on version 2.2 now, unfortunately a small number of websites are still using v1.5 for SSL/TLS. That’s why the Bleichenbacher attacks keep coming back. When you’re encrypting something using RSA as defined in v1.5, before data is encrypted it’s padded. The padded value is then converted into an integer and factorized. The RSA cryptosystem is based on the factorization of the product of two large prime numbers, unfortunately there is a range of insecure plaintexts that needs to be avoided, hence the padding to harden the encryption.

We’re not going to go too far off the beaten path on the mathematical aspects of encryption – just far enough that you’ll understand what I’m talking about. Let’s start with a theoretical explanation and then I’ll apply it to SSL/TLS.

Decryption is a much more expensive process in terms of computing resources than encryption—that’s actually why a lot of enterprises offload their SSL/TLS functions to load balancers and other edge devices. We’re talking about thousands of requests to negotiate connections on the server side, whereas the client may only be negotiating a handful simultaneously—at most.

So, to avoid devoting resources to decrypting worthless requests some implementations use something called an Oracle to determine whether or not what’s being transmitted should be decrypted or not. It’s worth noting that the Oracle in the Bleichenbacher attacks does not refer to the company. It refers to the Oracle in the context of RSA encryption.

The Oracle makes a determination based on the padding. If the message has the correct amount of padding the Oracle figures decryption will yield something, if it doesn’t the Oracle will ignore it, or, in some cases, respond with a fail message.

What Bleichenbacher’s exploits really represent are a method to guess the padding, which can then be used to try to guess the key. If that seemed a little confusing, it won’t once we apply it to SSL/TLS.

Bleichenbacher’s CAT vs. SSL/TLS

Let’s look at Bleichenbacher’s CAT in action. Before a secure connection can take place the client and server must perform the TLS handshake. This is a set of steps wherein the client authenticates the server certificate, negotiates the cipher suite to be used in the connection and then exchanges symmetric session keys that will be used during the connection itself.

Again, at scale, the processing power needed to perform what can sometimes be tens of thousands of handshakes simultaneously can necessitate offloading those functions entirely. But, to help mitigate some of the garbage requests, an Oracle determines whether a message needs to be decrypted or not.

This exploit occurs during the key exchange. The pre-master secret is used to compute the session keys that will be used during the connection. As we discussed, using RSA as defined by PKCS1 v1.5, when the smaller pre-master secret (which may be 128- or 256-bit) is placed into the large public key it’s padded to make up the difference in size.

The issue is with the padding, there is a “non-negligible” probability that by bombarding the Oracle with random sequences of bytes that eventually you’ll send a message that looks properly padded.

Most of the time the server will return a message that tells the client it couldn’t decrypt the message because it didn’t have the right padding.”

But, when the correct sequence is guessed, the server will send a different message. If everything goes smoothly, the Oracle lets the server decrypt the pre-master secret, the server deduces the symmetric key and then sends back a Finished message.

But in this case, because the attacker was able to guess the padding but didn’t send the correct pre-master secret, the Finished message won’t be encrypted properly.

This is what the attackers want, because it starts to narrow down the possible values for the pre-master secret. And if you can guess that value, you can guess the key.

Initially, this exploit was triaged by adding additional safeguards to RSA, like limiting the number of requests allowed or not sending a response when the message failed. But the exploit was refined in 2003, then again 2012, 2014, it was a key component of the DROWN attack and in 2017 the ROBOT attack—at this point it’s one of the most prolific threats SSL/TLS and PKI in general have seen.

Bleichenbacher’s CAT has found a way to amplify the attack by sending queries to multiple servers that use the same public key. This is not an uncommon use case for Wildcard SSL certificates. In fact, that’s one of the biggest drawbacks to deploying a Wildcard, that multiple sites using the same key increases the chances of a compromise.

Stop using RSA key exchange

When the creator of a given cryptosystem is telling you to stop using it for something—it’s typically with good reason. And that’s what’s happening with this report:

Supporting this small fraction of [RSA] users puts everyone at risk, as it allows the attacker to perform a downgrade attack by specifying RSA as the only public key algorithm supported by the server.

Here’s why backwards compatibility is so dangerous.

The vast majority of businesses and organizations do their best to keep the SSL/TLS implementations at least somewhat up-to-date. It took a little longer to say goodbye to TLS 1.0 than it probably should have, but overall things are headed in the right direction.

And TLS 1.3 completely solves this issue by deprecating support for RSA key exchange (it also refines the handshake we discussed earlier). Unfortunately, all of that is rendered moot as long as we still have to support a small fraction of clients and servers still using RSA. If you fall into that category, it’s advisable you deprecate support for RSA and switch Elliptic Curve Diffie-Helman for key exchange.

Now, a quick word of caution. This is a viable exploit, but not an easy one to pull off. So don’t expect to hear about a rash of Oracle padding attacks hitting the web anytime soon.

In order to pull off a Bleichenbacher’s CAT attack (that really doesn’t roll off the tongue very well), you would need to target the server from another virtual machine that’s running on the same system. You couldn’t use some remote shell. You would also need a certain permission level to execute the attack, that would need its own compromise to achieve. Oh yeah, and you would also need to avoid detection.

So, this is probably not something we’re going to see in the wild anytime soon.

But, much like with the original Bleichenbacher attack, this exploit will likely continue to be refined until maybe, one day, it will be a real threat.

Or maybe we could just move on from RSA.

As always, leave any comments or questions below…

• #Bleichenbacher's CAT
• #RSA