Some thoughts on the CRIME attack

By this point, some people have started to ask me about the Rizzo and Duong's new CRIME attack on TLS.

The short version is the same as with BEAST last year: Tor is not affected. TorBrowser is not affected. Other applications may be affected; please consult your app vendor.

Here's the longer version, in case you're more curious. This is going to assume a little technical background, but not too much.

The attack: CRIME exploits TLS compression to learn secret cookies. (Approximate description follows.) The attacker uses JavaScript (or some other means) to cause a client to make an encrypted, compressed request to a webserver. Part of that request (for example, the URL) is under the attacker's control. Part of that request (for example, the cookie) is secret. TLS does not hide the length of what it's transmitting[*], so the attacker can learn the length of the compressed request. The length of the compressed request will depend on how much redundancy there is between the attacker-controlled data and the rest of the request (including the secret). By learning how much redundancy there was, the attacker can learn how many bytes of attacker-controlled information were shared with the secret, and thereby how many bytes.

You can imagine it as something like a sophisticated game of Mastermind: the attacker gets to guess a cookie, and they learn something how much of the cookie they guessed right. With enough guesses, they can learn the cookie, which lets them impersonate the client to the server.

[*] (Okay, not all TLS implementation reveal the exact length of what they're encrypting. If they're using CBC, they'll round up to the nearest 16 bytes. But that's still enough information about the compressed data's length for this attack to work.)

Is Tor vulnerable? Tor isn't vulnerable because Tor (mostly!) never compresses anything secret before encrypting it. Tor doesn't use TLS compression at all. The only compressed data in Tor are pieces of directory information; and nearly all directory information is public knowledge, and downloaded by all clients.

The only non-public pieces of directory information in Tor are bridge descriptors and hidden-service descriptors. But these are only transmitted compressed on their own, and never compressed along with something adversary-controlled.

What about TorBrowser? TorBrowser isn't affected by CRIME as it stands either: It has disabled SPDY, and it has never enabled TLS compression.

Other browsers are probably affected; please check your browser vendor for updates.

So, what about the rest of the internet?

If you write, maintain, or use an application that uses TLS compression, you should probably just turn off the TLS compression until you figure out whether it's safe for your application.

The CRIME attack exploits a few key properties of HTTPS (the encrypted web protocol that uses the TLS encryption protocol). These properties are:

  • The TLS protocol doesn't hide the length of what it's encrypting. (It hides it not at all with stream ciphers, and not at all well with block ciphers.)
  • TLS has an optional compression feature where data can be compressed before it's encrypted.
  • The length of the compressed record depends on the value of what is being compressed. (This is inevitable with lossless compression.)
  • The same secret is sent over and over.
  • The attacker can make the client generate compressed requests that contain attacker-controlled data in the same stream with secret data.

So it doesn't look the internet is out of the woods yet here: I don't believe we've seen the end of the CRIME attack. Even when TLS compression is disabled, we'll still need to worry about other compression: HTTP transfer encodings, for example. If an HTTPS page contains both an a secret part (like an anti-XSS token) and an attacker-controlled part, that's possibly enough for the attack to succeed. I predict that we'll be finding vulnerabilities of this type for a while, in nearly anything complicated that uses compression.

So, what can be done for programs and protocols in general (not just HTTP)?

  1. Don't use compression.
  2. Never compress anything containing a secret.
  3. Never compress secret data and attacker-controlled data in the same compression stream without flushing the compression state between the two.
  4. Don't send the same secret over and over.

Option 1 won't please the engineers: bandwidth savings from compression are real.

I hear some advocacy for options 2 or 3, but they're pretty fiddly. They require programmers to do something that programmers have historically been pretty bad at: tagging all of the tainted or the sensitive data in their programs, without exception. I predict that among people who take this approach with complex programs or websites, it's going to be pretty common to miss at least one secret or at least one attacker-controlled data vector.

Option 4 is what I like most, but it's going to require more crypto and engineering. It's the 21st century, after all. Cookies are a stupid way to authenticate; we have had better authentication protocols for decades.

Oh, and one more thing to worry about: Predictable data compressed along with a secret can be pretty bad too. Suppose for example that there's a fine-grained timestamp that gets compressed over and over along with the same secret, and the attacker can view the length of each compresed stream, and make a good guess about the timestamp's value. This leaks some information about the secret to the attacker, and with enough measurements, is probably enough to attack some systems.

In Summary:

The CRIME attack is very clever indeed. I'm looking forward to seeing the authors' talk/code in full once they're public.

CRIME is very bad against HTTPS, and makes TLS compression also look risky. Make sure your browser is updated.

Tor is not affected. TorBrowser's HTTPS is not affected. TorBrowser doesn't do SPDY.

And despite what you're hearing, this is not a TLS-specific or HTTPS-specific attack. All compress-and-encrypt combinations could probably use some attention, and should probably be considered suspect until they can get evaluated. This is going to be hard, since you can't just look at the encryption layer: you need to look at the compressed data stream itself, to see whether it's going to compress the same secrets secrets together with attacker-controlled or attacker-known values over and over.

So, who wants to have a crack at X11-over-compressed-SSH? Anybody know any fun automated systems built on top of PGP?

And y'know, while you're looking for places that compress secrets, it's probably a good idea to think about timing side-channels from your compression too.

Acknowledgements: my thanks to Juliano for explaining the attack to me and helping me understand its ramifications. Lots of the analysis above is due to a conversation with him. Thanks also to Juliano and Thai for coming up with the attack. Thanks to Robert Ransom for feedback and corrections on the first draft of this post.

Anonymous

September 14, 2012

Permalink

It appears to me that no official release build of Firefox has ever supported TLS compression, through sheer dumb luck (NSS has all the necessary code, but it's disabled at compile time, at least in official builds, because of symbol conflicts between multiple embedded copies of zlib, that nobody wanted to disentangle). I would rate it as unlikely that any downstream rebuilder ever bothered to do the additional plumbing required to fix the symbol conflicts and turn it on.

I certainly hope SPDY grows intrinsic defenses for this sort of attack; it has enough application-layer knowledge that it could do something clever to preserve compression but prevent the attack, e.g. maintaining a per-connection dictionary of entire previously used HTTP headers. It's going to take a protocol revision though.

"Send the same secret over and over" has nice engineering properties that I think will make avoiding it a hard sell; people like idempotence and not having to track state server-side.

Anonymous

September 14, 2012

Permalink

> Don't send the same secret over and over.

This requires very careful taint tracking and decision making about what constitutes a secret. A bank account number? An email address? If they are transmitted over HTTPS, I expect them to be kept confidential. I think breaking the compression stream is the only feasible solution. There will be a lot of vulnerabilities relying on this attack discovered over the next few years.

Anonymous

September 18, 2012

Permalink

Another option would be for websites to add additional decoy cookies. If your normal request has:

Cookie: sessionid=1234abcd1234abcd

Then add additional cookies:

Cookie: decoy1=sessionid=12346543221345234
Cookie: decoy2=sessionid=2ababa23213345234
Cookie: decoy3=sessionid=32bdcdbdbdb345234
Cookie: decoy4=sessionid=42bdcdbdbdb345234
...

The CRIME attack, which is looking for redundancy with the string 'sessionid=' could 'lock on' to the wrong one.

Anonymous

September 18, 2012

Permalink

Or, just introduce a new header on every http request: 'Nonce'

Nonce: random-string-of-bytes-of-random-length

So long as the variation in the length of the nonce header is greater than the observed difference in length between compressed versions, that should eliminate the information leak (with high probability).

Anonymous

September 18, 2012

Permalink

Hmmm, if only TLS supported some kind of fancy client authentication so we didn't need to use DIY cookie auth...

Anonymous

September 27, 2012

Permalink

Sounds to me like a good case for making use of such as client certificates though I am unsure with such as security parameters caching etc would that even help or would it require the public key renegotiation stages at every to happen more frequently than in the average caching situation. It seems to me though from the article that this affects *every* encrypted communication which could potentially carry compressed data at the encryption level or bellow so presumably all email (Though emails bigger issue is lack of support for TLS on too many servers in the first place) as an email can be crafted with compressed file attachments, any service allowing the attacker to transmit a file or pipe any kind of binary data for that matter, SSH, SCP, SFTP etc, HTTPS where it allows any form of file upload or binary payload on that note does it even have to be binary or would this attack still work if say specially crafted compressed JPG data was converted to base64 to allow it to be slipped into any web form I guess I can't see a reason why it wouldn't be possible to create an equivalent representation depending on the constraints of character encoding etc probably difficult without including at least some malformed bytes though which if it happens every request would give the server adiquite cause to cease serving your IP address

Anonymous

October 20, 2012

Permalink

Sorry, I don't know where else to ask about something strange: while reading this blog (both this post and another post), I noticed what appears to be a 1x1 pixel red dot which keeps the same location as I scroll up or down. When I visit another blog with another certificate, I also see a 1x1 red dot, but in a different place, which maintains its position as I scroll up or down. Could this be an indication of some kind of tracking (maybe by my ISP)?

I usually configure FF/IW/TBB to disable Javascript entirely, so it is quite possible that this is something I am seeing only because as I write I have Javascript enabled in order to use this blog.

Anonymous

October 20, 2012

Permalink

Red dots: After further checking, an update: nothing to do with browsing per se since the dots are visible (just barely) in the desktop background. I think what I am seeing is a possibly unique pattern of red dots which appear in various specific places on my screen. Reminds me visually of the scary paper a few years ago in which researchers reported finding that laser printers print out unique patterns of tiny dots. The vendors responded by saying this is an anti-counterfeiting measure, but the researchers responded by saying that the dots appear even in black and white laser printers (which are physically incapable of currency counterfeiting). I checked mine and sure enough the dots were there, consistently in the same place with each test page on that printer, but not the same pattern as the one in the images provided by the researchers for one of the printers they tested.

If you are trying to track someone's web-browsing using a unique pattern of 1x1 dots, presumably injected using some browser exploit, why use a noticeable color like red? Maybe this is some hardware issue and not a crypto-tracking exploit at all. Sorry for wasting band-width if so, but I'd sure like to know what is going on here.

Anonymous

October 20, 2012

Permalink

Red dots 3: sorry, will understand if moderators decide not to post my questions about this. Messing about with a live CD shows the red dots appear even when running off a presumably untainted live CD, and are not seen on another computer. So whatever it is, nothing to do with browsing, and nothing to do with Tor. Sorry, sorry, sorry...

I can see that asking about "red dots" might sound like a troll to a paranoid mind, but if you read the paper on uniquely identifying a laser printer from a unique barely noticeable pattern of dots printed with every document, you'll probably agree that it is not inappropriate for me to try to figure out why I am seeing this pattern of red dots on the screen of one particular (used) computer. Unfortunately I've never heard of anything like this before and don't know where to begin.