in attacks, TLS/SSL 1,334 Words

Attack of the week: RC4 is kind of broken in TLS

Update: I’ve added a link to a page at Royal Holloway describing the new attack. 

Listen, if you’re using RC4 as your primary ciphersuite in SSL/TLS, now would be a great time to stop. Ok, thanks, are we all on the same page?

No?

I guess we need to talk about this a bit more. You see, these slides have been making the rounds since this morning. Unfortunately, they contain a long presentation aimed at cryptographers, and nobody much seems to understand the real result that’s buried around slide 306 (!). I’d like to help.

Here’s the short summary:

According to AlFardan, Bernstein, Paterson, Poettering and Schuldt (a team from Royal Holloway, Eindhoven and UIC) the RC4 ciphersuite used in SSL/TLS is broken. If you choose to use it — as do a ridiculous number of major sites, including Google — then it may be possible for a dedicated attacker to recover your authentication cookies. The current attack is just on the edge of feasibility, and could probably be improved for specific applications.

This is bad and needs to change soon.

In the rest of this post I’ll cover the details in the usual ‘fun’ question-and-answer format I save for these kinds of attacks.

What is RC4 and why should I care?

RC4 is a fast stream cipher invented in 1987 by Ron Rivest. If you like details, you can see this old post of mine for a longwinded discussion of RC4’s history and flaws. Or you can take my word: RC4 is old and crummy.

Despite its age and crumminess, RC4 has become an extremely popular ciphersuite for SSL/TLS connections — to the point where it accounts for something absurd like half of all TLS traffic. There are essentially two reasons for this:

  1. RC4 does not require padding or IVs, which means it’s immune to recent TLS attacks like BEAST and Lucky13. Many admins have recommended it as the solution to these threats.
  2. RC4 is pretty fast. Faster encryption means less computation and therefore lower hardware requirements for big service providers like Google.

So what’s wrong with RC4?

Like all stream ciphers, RC4 takes a short (e.g., 128-bit) key and stretches it into a long string of pseudo-random bytes. These bytes are XORed with the message you want to encrypt, resulting in what should be a pretty opaque (and random-looking) ciphertext.

The problem with RC4 is that the above statement is not quite true. The bytes come out of the RC4 aren’t quite random looking — they have small biases. A few of these biases have been known for years, but weren’t considered useful. However, recent academic work has uncovered many small but significant additional biases running throughout the first 256 bytes of RC4 output. This new work has systematically identified many more.

At first blush this doesn’t seem like a big deal. Cryptographically, however, it’s a disaster. If I encrypt the same message (plaintext) with many different RC4 keys, then I should get a bunch of totally random looking ciphertexts. But these tiny biases mean that they won’t be random — a statistical analysis of different positions of the ciphertext will show that some values occur more often.

By getting many different encryptions of the same message — under different keys — I can tally up these small deviations from random and thus figure out what was encrypted.

If you like analogies, think of it like peeking at a picture with your hands over your eyes. By peeking through your fingers you might only see a tiny sliver of the scene you’re looking at. But by repeating the observation many times, you may be able to combining those slivers and figure out what you’re looking at.

Why would someone encrypt the same message many times?

The problem here (as usual) is your browser.

You see, there are certain common elements that your browser tends to send at the beginning of every HTTP(S) connection. One of these values is a cookie — typically a fixed string that identifies you to a website. These cookies are what let you log into Gmail without typing your password every time.

If you use HTTPS (which is enforced in many sites by default), then your cookies should be safe. After all, they’ll always be sent over an encrypted connection to the website.Unfortunately, if your connection is encrypted using RC4 (as is the case with Gmail), then each time you make a fresh connection to the Gmail site, you’re sending a new encrypted copy of the same cookie. If the session is renegotiated (i.e., uses a different key) between those connections, then the attacker can build up the list of ciphertexts he needs.

To make this happen quickly, an attacker can send you a piece of Javascript that your browser will run — possibly on a non-HTTPS tab. This Javascript can then send many HTTPS requests to Google, ensuring that an eavesdropper will quickly build up thousands (or millions) of requests to analyze.

Probability of recovering a plaintext byte (y axis) at a particular byte position in the RC4-encrypted stream (x axis), assuming 2^24 ciphertexts. Increasing the number of ciphertexts to 2^32 gives almost guaranteed plaintext recovery at all positions. (source)

Millions of ciphertexts? Pah. This is just crypto-wankery.

It’s true that the current attack requires an enormous number of TLS connections — in the tens to hundreds of millions — which means that it’s not likely to bother you. Today. On the other hand, this is the naive version of the attack, without any special optimizations.

For example, the results given by Bernstein assume no prior plaintext knowledge. But in practice we often know a lot about the structure of an interesting plaintext like a session cookie. For one thing, they’re typically Base64 encoded — reducing the number of possibilities for each byte — and they may have some recognizable structure which can be teased out using advanced techniques.

It’s not clear what impact these specific optimizations will have, but it tends to reinforce the old maxim: attacks only get better, they never get worse. And they can get a lot better while you’re arguing about them.

So what do we do about it?

Treat this as a wakeup call. Sites (like Google) need to stop using RC4 — before these attacks become practical. History tells us that nation-state attackers are already motivated to penetrate Gmail connections. The longer we stick with RC4, the more chances we’re giving them.

In the short term we have an ugly choice: stick with RC4 and hope for the best, or move back to CBC mode ciphersuites — which many sites have avoided due to the BEAST and Lucky13 attacks.

We could probably cover ourselves a bit by changing the operation of browsers, so as to detect and block Javascript that seems clearly designed to exercise these attacks. We could also put tighter limits on the duration and lifespan of session cookies. In theory we could also drop the first few hundred bytes of each RC4 connection — something that’s a bit of a hack, and difficult to do without breaking the TLS spec.

In the longer term, we need to move towards authenticated encryption modes like the new AEAD TLS ciphersuites, which should put an end to most of these problems. The problem is that we’ll need browsers to support these modes too, and that could take ages.

In summary

I once made fun of Threatpost for sounding alarmist about SSL/TLS. After all, it’s not like we really have an alternative. But the truth is that TLS (in its design, deployment and implementation) needs some active help. We’re seeing too many attacks, and they’re far too close to practical. Something needs to give.

We live in a world where NIST is happy to give us a new hash function every few years. Maybe it’s time we put this level of effort and funding into the protocols that use these primitives? They certainly seem to need it.

41 thoughts on “Attack of the week: RC4 is kind of broken in TLS”

  2. Or better yet, the first few thousand. The problem here is that you need to make this change on every client /and/ every server. And that means a fundamental change to the TLS spec (or some nasty, nasty hack).

  3. It just doesn't really help. Plaintext recovery works no matter how much you skip. Sorry for repeating this, but that's just how it is. 🙂

  4. Yikes. And here I was about to recommend going RC4 only due to BEAST.

    What would the world look like if, one day, we woke up and TLS was completely broken…? Actually quite a scary thought without something else to go to.

    We do seem to need a new protocol – SSL/TLS only seems to be hanging on by its fingertips. Do you know of any alternatives in development out there?

  5. Both TLS 1.1/1.2 supposedly account for BEAST, and let us switch to a different cipher.

  7. Crap, and of course SMTP client authentication is most commonly done with SMTP AUTH PLAIN over TLS. So the AUTH PLAIN sends one unchanging base64-encoded string as the authenticator, with the only preceding text from the client being an EHLO line that doesn't change much (in practice).

    So it's worse than in HTTPS.

  9. The problem is not really TLS, it's the cypher (RC4) what's failing us here. A new cypher algorithm would help us fix this.

  10. Regarding the image at the top: ECDHE_ECDSA as the key exchange algorithm? Did you modify the image? I don't see that when I try it.

  14. SSL and TLS support zero length records which can be inserted randomly, moving the cipher state forward by at least the number of bytes in the MAC. This is within spec but breaks certain old implementations. AES-GCM is slow compared to even AES-SHA without HW acceleration. While it would be nice if TLS could hide whatever it transports, this specific issue like the last few, are more about the session cookie in HTTPS or SMTP hello.

  15. The problems with that:

    1) You would need to change all the clients, and if you do that, why not just upgrade to TLS 1.2 instead

    2) You increase the setup time for rc4, making it take longer to the point that its performance advantage either disappears completely, or becomes even slower than more secure alternatives.

    RC4 was amazing. There is no way that a stream cipher invented in the late 80s and published in the mid 90s should still be as strong as it is today, but there are better alternatives now and we should be using them.

  17. “History tells us that nation-state attackers are already motivated to penetrate Gmail connections.”

    Hilarious. Worrying about some state collecting and analyzing a million SSL connections of you, but then upload all this mail in plaintext to private company, where it gets screened and evaluated for targeted advertisement and is subject to various lawful interception laws.

  18. Google uses ECHDE for all it's services, if supported by the browser (afaik Chrome and FF, but not IE).

  19. The problem is rooted to TLS. If encrypt-then-mac was used, there would not be BEAST, Lucky 13 attacks, and RC4 could have been easily replaced.

  20. That has actually been done for ssh, discarding the first 1536 bytes of keystream: http://tools.ietf.org/html/rfc4345
    But as other people have already said, getting a new cipher suite accepted and widely used in TLS is harder, and if you are going to do that, you are probably better off with AES-GCM, especially if you have a processor and library that support the AES-NI instruction set.

  21. The weakness of the first bytes of the RC4 stream has been known for years, if I'm not mistaken it's the way WEP was broken. Is this the same vulnerability or a different one? It seems to me that if it's the same, then the obvious fix would be to discard the first N bytes of the stream.

  23. No, actually the key scheduling was the main issue. The same key was used too often and in a predictable manner (concatenation of secret and a counter).

  24. “Treat this as a wakeup call. Sites (like Google) need to stop using RC4 — before these attacks become practical.”

    The reason major sites do this is that best practice currently states that you should prioritize RC4, e.g. see:
    https://www.ssllabs.com/downloads/SSL_TLS_Deployment_Best_Practices_1.0.pdf

    The problem is the broken nature (due to BEAST) of block ciphers in SSL3 and TLS1.0. Until major browsers start supporting something better that TLS1.0 we are stuck with RC4. My reading of your article suggests that no one has made this a practical attack – whereas attacks against the block ciphers ARE practical TODAY.

    Its not the major sites that need to change…its the browser makers.

  25. What is the attack key strength? Does this attack succeed on ridiculously large keys (e.g. 1024 bits symmetric)?

  26. But it would be considerably harder to implement an attack. The point of attacking HTTPS is the scenario where the attacker can run JavaScript in any unrelated browser tab.

  29. Sine it doesn't seem practical (or possible at all) to perform BEAST or Lycky13 kind of attacks in SMTP connection then why bother with RC4 that would gradually leak AUTH out to passive eavesdropper? Who sane would recommend that? Just use regular AES-CBC until it's phased out in favour of GCM.

  30. There were no nice plots of probabilities earlier and it's not the way WEP was broken, but it *was* widely known that initial portion of keystream is biased.

  31. Firefox has a feature where you can disable all the RC4 type ciphers, to force websites that don't prioritize AES type ciphers (about:config), gmail is one of them. You can even disable the Triple-Des ciphers.

    But, fireox doesn't have TLS 1.1 OR 1.2. IE 10 defaults to TLS 1.2 with AES in gmail. You can also remove “weak ciphers” in Opera browser as well. Google Chrome doesn't have this feature, and that is the biggest negative, since it is better on almost every other function compared to Firefox, IE, or Opera.

  32. I've seen Google Docs and Youtube with ECC certificates too. Google must be trying some new things, the certificate was issued ‎Friday, ‎8 ‎March ‎2013 3:28:01 a.m. and has a 256bit ECC public key

  33. Exactly, and I don't even think anyone is actually working on getting it done either.

  35. I believe that RSA upgraded the recommendation to 512 in the true RC4 spec back in the 90's. The problem is that people implemented based on the ARC4 papers which didn't include that proviso.

    This is part of the reason that WEP has been so completely broken.

  36. It just doesn't really assist. Plaintext data recovery really works regardless of how much cash you skip. Sad for repeating this particular, but that's how it will.

    Haccp

Comments are closed.