CRIME Attack (Compression Oracle Side-Channel)
- •
What it is
- •
When attacker-controlled plaintext is compressed together with a secret before encryption, the compressor's redundancy elimination (DEFLATE/zlib's LZ77-style back-references) makes the compressed — and therefore encrypted — output shorter whenever the attacker's input shares a substring with the secret. Guessing the secret byte-by-byte and watching the resulting ciphertext length reveals which guess was correct: a correct guess lets the compressor reference the matching text that occurs later in the real secret via a cheap back-reference instead of encoding fresh literal bytes, so the output grows less than it does for a wrong guess. This is the real-world CRIME/BREACH vulnerability class against TLS compression.
- •
- •
When to apply
- •
A network service compresses (zlib/gzip/DEFLATE) attacker-controlled input together with a secret before encrypting it in a mode that doesn't hide plaintext length (e.g. a stream mode like CTR), and returns ciphertext whose length you can measure.
- •
- •
Math
- •
Informal: for a wrong guess byte, grows by roughly one full literal-encoding's worth over the baseline. For the correct guess, the growing prefix of now matches an equally-growing prefix of , so DEFLATE can encode more of it as a cheap back-reference — the length increase is smaller (or the length doesn't grow at all).
- •
- •
Worked example
- •
Secret
crypto{dummy_flag_dummy_}. Compressing an empty prefix + secret gives a 33-byte baseline. Compressing"crypto{a" + secret(a wrong guess for the 8th character) gives 36 bytes (+3). Compressing"crypto{d" + secret(the correct guess) gives only 35 bytes (+2) — one byte shorter than the wrong guess, because that repeated"crypto{d"prefix can now be partially referenced against its real occurrence in the secret.
- •
- •
Python
- •
baseline = len(encrypt_oracle(b"")) best_guess, best_len = None, None for b in range(256): trial_len = len(encrypt_oracle(known + bytes([b]))) if best_len is None or trial_len < best_len: best_guess, best_len = b, trial_len known += bytes([best_guess])
- •
- •
- •
Cards
- •
What makes a correct byte guess produce shorter compressed output than a wrong guess?
- •
The compressor can encode the matching substring as a cheap back-reference to its real occurrence later in the secret, instead of paying full price for fresh literal bytes.
- •
- •
What's the real-world name for this attack class against TLS?
- •
CRIME (and its HTTP-response variant, BREACH).
- •
- •