Easter Hack: Even More Critical Bugs in SSL/TLS Implementations

It's been some time since my last blog post - time for writing is rare. But today, I'm very happy that Oracle released the brand new April Critical Patch Update, fixing 37 vulnerabilities in our beloved Java (seriously, no kidding - Java is simply a great language!). With that being said, all vulnerabilities reported by my colleagues (credits go to Juraj Somorovsky, Sebastian Schinzel, Erik Tews, Eugen Weiss, Tibor Jager and Jörg Schwenk) and me are fixed and I highly recommend to patch as soon as possible if you are running a server powered by JSSE! Additional results on crypto hardware suffering from vulnerable firmware are ommited at this moment, because the patch(es) isn't/aren't available yet - details follow when the fix(es) is/are ready.

To keep this blog post as short as possible I will skip a lot of details, analysis and pre-requisites you need to know to understand the attacks mentioned in this post. If you are interested use the link at the end of this post to get a much more detailed report.






 
Resurrecting Fixed Attacks
Do you remember Bleichenbacher's clever million question attack on SSL from 1998? It was believed to be fixed with the following countermeasure specified in the TLS 1.0 RFC:

“The best way to avoid vulnerability to this attack is to treat incorrectly formatted messages in a manner indistinguishable from correctly formatted RSA blocks. Thus, when it receives an incor- rectly formatted RSA block, a server should generate a random 48-byte value and proceed using it as the premaster secret. Thus, the server will act identically whether the received RSA block is correctly encoded or not.” – Source: RFC 2246

In simple words, the server is advised to create a random PreMasterSecret in case of problems during processing of the received, encrypted PreMasterSecret (structure violations, decryption errors, etc.). The server must continue the handshake with the randomly generated PreMasterSecret and perform all subsequent computations with this value. This leads to a fatal Alert when checking the Finished message (because of different key material at client- and server-side), but it does not allow the attacker to distinguish valid from invalid (PKCS#1v1.5 compliant and non-compliant) ciphertexts. In theory, an attacker gains no additional information on the ciphertext if this countermeasure is applied (correctly).

Guess what? The fix itself can introduce problems:

1. Different processing times caused by different code branches in the valid and invalid cases
2. What happens if we can trigger Excpetions in the code responsible for branching?
3. If we could trigger different Exceptions, how would that influence the timing behaviour?

Let's have a look at the second case first, because it is the easiest one to explain if you are familiar with Bleichenbacher's attack:


Exploiting PKCS#1 Processing in JSSE
A coding error in the com.sun.crypto.provider.TlsPrfGenerator (missing array length check and incorrect decoding) could be used to force an ArrayIndexOutOfBoundsException during PKCS#1 processing. The Exception finally led to a general error in the JSSE stack which is being communicated to the client in form of an INTERNAL_ERROR SSL/TLS alert message. 
What can we learn from this? The alert message is only send if we are already inside the PKCS#1 decoding code blocks! With this side channel Bleichenbacher's attack can be mounted again: An INTERNAL_ERROR alert message suggests a PKCS#1 structure that was recognized as such, but contained an error - any other alert message was caused by the different processing branch (the countermeasure against this attack).

The side channel is only triggered if the PKCS#1 structure contains a specific structure. This structure is shown below.
  

If  a 00 byte is contained in any of the red marked positions the side-channel will help us to recognize these ciphertexts.

We tested our resurrected Bleichenbacher attack and were able to get the decrypted PreMasterSecret back. This took about 5h and 460000 queries to the target server for a 2048 bit key. Sounds much? No problem... By using the newest, high performance adaption of the attack (many thanks to Graham Steel for very the helpful discussions!) resulted in only about 73710 queries in mean for a 4096 bit RSA key!

This time JSSE was successfully exploited once. But let's have a look on a much more complicated scenario. No obvious presence of a side channel at all :-( Maybe we can use the first case...
 


Secret Depending Processing Branches Lead to Timing Side Channels
A conspicuousness with respect to the random PreMasterSecret generation (you remeber, the Bleichenbacher countermeasure) was already obvious during the code analysis of JSSE for the previous attack: The random PreMasterSecret was only generated if problems occured during PKCS#1 decoding. Otherwise, no random bytes were generated (sun.security.ssl.Handshaker.calculateMasterSecret(...)). 

The question is, how time consuming is the generation of a random PreMasterSecret? Well, it depends and there is no definitive answer to this question. Measuring time for valid and invalid ciphertexts revealed blurred results. But at least, having different branches with different processing times introduces the chance for a timing side channel. This is why OpenSSL was independently patched during our research to guarantee equal processing times for both, valid and invalid ciphertexts.


 

Risks of Modern Software Design

To make a long story short, it turned out that not the random number generation caused the timing side channel, but the concept of creating and handling Exceptions. Throwing and catching Exceptions is a very expensive task with regards towards the consumption of processing time. Unfortunately, the Java code responsible for PKCS#1 decoding ( sun.security.rsa.RSAPadding.unpadV15(...)) was written with the best intentions from a developers point of view. It throws Exceptions if errors occur during PKCS#1 decoding. Time measurements revealed significant differences in the response time of a server when confronted with valid/invalid PKCS#1 structures. These differences could even be measured in a live environment (university network) with a lot of traffic and noise on the line.

Again, how is this useful? It's always the same - when knowing that the ciphertext reached the PKCS#1 decoding branch, you know it was recognized as PKCS#1 and thus represents a useful and valid side channel for Bleichenbacher's attack.  The attack on an OpenJDK 1.6 powered server took about 19.5h and 18600 oracle queries in our live setup!

JSSE was hit the second time....


OAEP Comes To The Rescue
Some of you might say "Switch to OAEP and all of your problems are gone....". I agree, partly. OAEP will indeed fix a lot of security problems (but definitely not all!), but only if implemented correctly. Manger told us that implementing OAEP the wrong way could have disastrous results. While looking at the OAEP decoding  code in sun.security.rsa.RSAPadding it turned out that the code contained a behaviour similar to the one described by Manger as problematic. This could have led to another side channel if SSL/TLS did already offer OAEP support....

All the vulnerabilties mentioned in this post are fixed, but others are in the line to follow... We submitted a research paper which will explain the vulnerabilities mentioned here in more depth and the unpublished ones as well, so stay tuned - there's more to come.


Many thanks to my fellow researchers Juraj Somorovsky, Sebastian Schinzel, Erik Tews, Eugen Weiss, Tibor Jager and Jörg Schwenk all of our findings wouldn't have been possible without everyones speical contribution. It needs a skilled team to turn theoretical attacks into practice!
 


A more detailed analysis of all vulnerabilities listed here, as well as a lot more on SSL/TLS security can be found in my Phd thesis: 20 Years of SSL/TLS Research: An Analysis of the Internet's Security Foundation.