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?
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.
What is RC4 and why should I care?
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:
- 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.
- 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.
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?
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.
|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.
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.
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”
Why not just patch RC4 by discarding the first 256 bytes of the keystream?
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).
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. 🙂
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?
Both TLS 1.1/1.2 supposedly account for BEAST, and let us switch to a different cipher.
Another good article. Thanks!
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.
seems like SSL/TLS is always getting owned some way or another…
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.
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.
Why not utilise AES-GCM? Would this not be a much better alternative to both rc4 and CBC?
I didn't do anything. That's what I get in my (stock) version of Chrome.
…and “some day soon” Firefox will start supporting TLS 1.1
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.
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.
Because a lot of software doesn't support it yet. Most of software in fact.
“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.
Google uses ECHDE for all it's services, if supported by the browser (afaik Chrome and FF, but not IE).
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.
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.
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.
Thanks for the article! This blog has been my new obsession!
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).
“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:
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.
What is the attack key strength? Does this attack succeed on ridiculously large keys (e.g. 1024 bits symmetric)?
If it's so easy, why do states bother using fake SSL certificates or infecting people with trojans?
Isn't AES CTR mode supported in TLS?
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.
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.
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.
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
Exactly, and I don't even think anyone is actually working on getting it done either.
what do you guys think about the higher grades of RSA? 2048 4028 etc?
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.
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.
Home Wellbeing has a wide range of One Stop Home Essentials products that care for the wellbeing of You and Your Loved Ones.
nice…… computer tricks
Home Lifestyle has a wide range of One Stop Home Essentials products suited for the Active, Busy, Mobile and City Living People, bringing the Quality of Life to a different level.
I feel your blog post is without a doubt dazzling. Several quite interesting opinions in your web log. Weve saved this specific page but will keep returning once again.
Dreambox Cccam | Dreambox Cardsharing
This is great information
Comments are closed.