Overview

TLS is currently the de facto standard for securing HTTP traffic (i.e. most of the internet). In fact you're using TLS when you request this page. TLS basically works in a couple steps. We'll briefly (and by no means thoroughly) cover them here:

Client (browser) pings server, server gives proof of identity to client.

Server and client agree on keys to encrypt traffic with.

All subsequent traffic between server and client is now encrypted.

Usually traffic is encrypted using AES as the cipher (sometimes, unfortunately, also RC4). Your current connection to this site probably uses AES in a fancy mode like GCM, but in this problem we'll be using AES in CBC mode. Assuming all traffic between server and client is encrypted via a secure cipher you shouldn't be able to gain knowledge of any data in the client request right? Turns out, you can if the request is compressed before being encrypted.

The Attack

If you want to read a complete overview of the attack, there's probably no better source than the slides from the original authors of the attack. I'll try to summarize briefly. Assume that there's an attacker who can intercept all traffic on your network. Assume also that this attacker is able to make malicious requests on your behalf where the attacker controls what goes into the body of a request to example.com (without being able to see or modify the headers including the secret cookie). The request will look something like this:

POST / HTTP/1.1
Host: example.com
Cookie: cookie={{some secret token}}
Content-Length: {{length of body}}
{{body}}

If the request is first compressed before being encrypted and the attacker has access to a compression oracle (i.e. has knowledge of how long the compressed and encrypted request is) the cookie can be recovered. This is because the attacker can input arbitrary values into the body and see how well they compress. Take for instance the case where cookie="secret". The attacker can observe that a body of cookie="s" compresses slightly better than all other variants of cookie="{{some byte}}". This means the attacker can byte-by-byte determine the cookie by looking at how well the request compresses. If the cookie is a session token or something else used to identify a logged in user the attacker now has access to your account.

The Compression Oracle

We've given you access to a compression oracle at https://id0-rsa.pub/problem/crime-oracle/{{your request body string}}. We'll simulate the CRIME attack for you by making {{your request body string}} the body of a request with a secret cookie (in the same form as the one above) and in the response tell you the byte size of the request. Use this oracle to recover the secret cookie.

Example Usage (Python)

from urllib2 import urlopen

body = 'somestring'
baseurl = 'https://id0-rsa.pub/problem/crime-oracle/'
size = int(urlopen(baseurl + body).read())

Hints

The cookie is all lowercase letters (8 to be exact). This will reduce the search space for each byte and also means you won't get as bottlenecked by the network.

The size of any ciphertext resulting from encryption in AES-CBC will be a multiple of 16 bytes (the block size of AES). You'll probably have to use some padding to see where the differences in compression size are.

Solution