Compression-Ratio Side Channel

Question

I'm working through the matasano crypto challenges, and I'm onto set 7, where they describe an attack on encryption/compression oracles. I am having trouble understanding the attacks, more so the logic behind the attack and am having difficulty finding any papers on it. If anyone knows about this type of attack and how it works, it would be much appreciated if someone could explain it.

For reference, here is the link to the challenge: http://www.cryptopals.com/sets/7/challenges/51

Compression Ratio Side-Channel Attacks

Internet traffic is often compressed to save bandwidth. Until recently, this included HTTPS headers, and it still includes the contents of responses.

Why does that matter?

Well, if you're an attacker with:

1. Partial plaintext knowledge and
2. Partial plaintext control and
3. Access to a compression oracle

You've got a pretty good chance to recover any additional unknown plaintext.

What's a compression oracle? You give it some input and it tells you how well the full message compresses, i.e. the length of the resultant output.

This is somewhat similar to the timing attacks we did way back in set 4 in that we're taking advantage of incidental side channels rather than attacking the cryptographic mechanisms themselves.

Scenario: you are running a MITM attack with an eye towards stealing secure session cookies. You've injected malicious content allowing you to spawn arbitrary requests and observe them in flight. (The particulars aren't terribly important, just roll with it.)

So! Write this oracle:

oracle(P) -> length(encrypt(compress(format_request(P))))

Format the request like this:

POST / HTTP/1.1
Host: hapless.com
Cookie: sessionid=TmV2ZXIgcmV2ZWFsIHRoZSBXdS1UYW5nIFNlY3JldCE=
Content-Length: ((len(P)))
((P))

(Pretend you can't see that session id. You're the attacker.)

Compress using zlib or whatever.

Encryption... is actually kind of irrelevant for our purposes, but be a sport. Just use some stream cipher. Dealer's choice. Random key/IV on every call to the oracle.

And then just return the length in bytes.

Now, the idea here is to leak information using the compression library. A payload of "sessionid=T" should compress just a little bit better than, say, "sessionid=S".

There is one complicating factor. The DEFLATE algorithm operates in terms of individual bits, but the final message length will be in bytes. Even if you do find a better compression, the difference may not cross a byte boundary. So that's a problem.

You may also get some incidental false positives.

But don't worry! I have full confidence in you.

Use the compression oracle to recover the session id.

I'll wait.

Got it? Great.

Now swap out your stream cipher for CBC and do it again.

Answer 1

Here's the basic idea. Encryption ideally hides all information about the encrypted data. But in practice, that isn't completely true: encryption reveals the size of the encrypted data, at least within a few bytes. For example, suppose that you know that the answer is “yes” or “no”, and you see the following message encrypted with AES-CTR:

82a801950ca7aaeea0685afc86b44b70 15c0

You know it's a two-byte message (plus 16-byte IV) so it's “no”.

Now suppose that you have a fixed-size message (or more generally a message where the attacker knows the approximate size anyway, because it is given by the protocol), but it's compressed before encrypted. Compression exploits redundancy in the message. So if the encrypted message is a lot smaller than the expected size of the plaintext, that means a highly redundant message; if the encrypted message is about as large as the expected size of the plaintext, that means a message with low redundancy.

Low/high repetition, on its own, is typically not meaningful to an attacker. But what if the attacker can inject some text into the message? Then the size of the encrypted compressed message reveals redundancy between the part that's injected by the attacker and the confidential part. Now there's room for a damaging attack.

In cryptography, and more generally in the study of computation, an oracle is a black box which receives inputs and produces outputs. The oracle's outputs may not be possible to obtain without the oracle. In cryptography, a common kind of oracle is one that knows a secret key that the attacker does not have, but the oracle will only respond in certain specific ways, it won't just reveal the key. For example, a basic encryption oracle is willing to encrypt any plaintext but won't decrypt anything, allowing attempts to perform chosen-plaintext attack.

In this challenge, you're asked to study a particular kind of encryption oracle which combines the submitted plaintext with some fixed confidential text, and compresses the whole message. By submitting a lot of different partial plaintexts, and measuring how the length of the whole message varies depending on the submitted plaintext, the attacker gains information about the fixed confidential part. For example, submit aaaaaaaa, bbbbbbbb, cccccccc, etc. and see how the compressed length varies to get a rough ideas of how many a's, b's, c's, etc. there are in the confidential part. Repeat with digrams, trigrams, etc. If the confidential text is some kind of password $P$, that can turn an exponential attack (try all possible passwords of the known length) into a linear attack (figure out the first character because it's the character $c$ for which $c^n P$ gives the best compression, then repeat for each subsequent character).

The basic principle has been well-known for a long time. It's mentioned in John Kelsey's 2002 paper “Compression and Information Leakage of Plaintext”. But few people thought about the concrete applications until it was widely publicized as the CRIME attack on TLS. CRIME exploits compressed TLS streams which contain both a fixed confidential part (cookie for a web page) and a varying attacker-chosen part (e.g. an injected ad that makes callbacks). If you look around CRIME, you'll find a lot of literature on the topic, including Thomas Pornin's detailed write-up before the attack was published.