Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Compress Then Encrypt, Not the Reverse

Two of this site's categories spend their whole existence on the same quantity, pulling it in opposite directions. Every entry in Compression — Huffman Coding, LZ77, DEFLATE — exists to find redundancy in a message and spend fewer bits on it. Every entry in Cryptography that encrypts rather than hashes — AES, RSA Encryption — exists to produce output indistinguishable from uniform noise, which is exactly the one shape a compressor cannot shrink. Neither category's own page states this tension explicitly, and it has a real, nameable consequence once both operations touch the same bytes: which one runs first isn't a stylistic choice. This page reuses DEFLATE's own lzssEncode and AES's own CTR-mode keystream, unmodified, to measure both directions live, then reproduces — in miniature, on this site's own simplified compressor — the exact mechanism behind two real, named attacks from the public record: CRIME (2012) and BREACH (2013).

Entropy, defined twice on this site already

Huffman Coding's own measurement defines a message's Shannon entropy as "the theoretical fewest bits any code could average per symbol" given how skewed its symbol frequencies are — a message with only a few distinct, wildly-uneven symbol frequencies has low entropy and compresses hard; a message where every symbol is equally likely has entropy equal to its own fixed-width cost, and no code, however clever, can beat that floor. Compression is the project of finding and spending exactly that floor, no more.

SHA-256's own live widget measures the opposite property under a different name: flip one input bit and "roughly half" of the 256 output bits change, unpredictably — the avalanche effect. A good cipher or hash is built so its output bytes are, as far as any attacker can tell without the key, drawn uniformly at random: every byte value equally likely, no symbol more common than any other. That is the exact condition under which Huffman Coding's own entropy bound equals the fixed-width cost — maximum entropy, by construction, is the whole design goal of a cipher's output. Compression hunts for skew; encryption's entire job is to leave none behind.

Try it: order, both ways

Type a message and press Run both orders. Compress, then encrypt runs the same LZSS tokenizer and flag-bit cost model DEFLATE's own page measures (window 48, lookahead 20 — reproduced here, not reapproximated) over your plaintext, then encrypts the resulting token stream's byte length under a fresh random AES-128 key using the exact gctr keystream function GCM's own page builds, run here over a flat byte array the same way that page's own GCM mode already uses it. Encrypt, then compress runs the identical two steps in the other order: AES-CTR first, then the identical LZSS tokenizer over whatever bytes come out.

Enter a message with some real repetition and press Run.

Why the reverse direction can't work

The "compress, then encrypt" row above always costs the same as compressing alone, plus a fixed per-byte AES overhead that doesn't care what it's encrypting — encryption has no opinion about structure, so it never undoes a win already banked. The "encrypt, then compress" row tells a different story: LZSS's tokenizer runs over the ciphertext bytes exactly as written, finds almost nothing to match, and still pays its flag bit on every byte it gives up on — the same 1-bit tax DEFLATE's own Pitfalls section measures as the real cost of LZSS's literal/match choice, now spent on a stream designed to have no matches to find. Run the same message through 120 fresh random AES keys and the ciphertext's compressed size lands between 112% and 125% of its own 8-bit fixed-width baseline every single time — never once below 100%. Compressing ciphertext isn't merely useless; on this page's own cost model it is strictly worse than skipping compression and shipping the ciphertext raw.

The cost of doing it the safe way: CRIME and BREACH

Compress-then-encrypt is the right order for size — but it reopens a different door the moment an attacker can put their own guess inside the same compressed buffer as a secret, and then observe the resulting ciphertext's length. This is not a hypothetical: CRIME (2012) exploited exactly this against TLS connections that used protocol-level DEFLATE compression, and BREACH (2013) exploited the same mechanism one layer up, against HTTP responses gzip-compressed before a secret (a CSRF token, a session identifier) was reflected back alongside attacker-controlled input. Both were real, published, named vulnerability classes against real deployed TLS and HTTP stacks — not an abstract puzzle.

The mechanism is the same LZSS back-reference this site's own LZ77 page already explains: a match token is cheaper than the literals it replaces. If a buffer holds a secret once and an attacker-supplied guess once, and the guess shares a prefix with the secret, the compressor finds a back-reference covering that shared prefix — and the longer the correct guess, the longer that match, the shorter the total compressed output. An attacker who can only observe the final ciphertext's length (TLS record size, HTTP response size over the wire) doesn't need to see a single plaintext byte: trying every possible next character and keeping whichever guess compresses shortest recovers the secret one character at a time. That is the entire attack, with no cryptographic weakness in the cipher at all — AES and TLS's own encryption are both working exactly as designed; the leak lives one layer up, in what gets compressed alongside what, before either ever sees a key.

Try it: watching the leak directly

This widget fixes an 8-character secret and lets you move a slider controlling how many of its leading characters your own guess gets right — the same "how much of the prefix matches" control this site's HMAC tag-comparison widget already uses for an unrelated leak. Both get compressed together in one buffer (secret=<secret>&echo=<guess>) through the identical LZSS cost model above — no encryption in this widget at all, because the leak lives entirely in the compression step, before encryption ever starts.

matched characters012345678
compressed bits

What this page draws from

entrywhat this page reuses
Huffman Codingthe Shannon-entropy lower bound, cited as the formal definition of "redundancy left to remove"
LZ77 / DEFLATElzssEncode, economicMinMatch, and the flag-bit cost model, run unmodified over both plaintext and ciphertext bytes
SHA-256the avalanche effect, cited as the formal definition of "no redundancy left to find"
AESthe full AES-128 block cipher and GCM's own gctr CTR-mode keystream function, run unmodified to produce this page's ciphertext bytes

Pitfalls

Neither live widget above is the real CRIME or BREACH attack. Both historical attacks ran adaptively over many real network requests against a live TLS or HTTP server, inferring one byte at a time from ciphertext size alone, with no access to the compressor's internal token counts the way this page's widgets display them directly. What's reproduced here is the underlying mechanism — matching compresses shorter — not the full chosen-plaintext network attack built on top of it.

This page's LZSS is the same simplified model LZ77's and DEFLATE's own pages already use — a single Huffman tree's worth of complexity short of real DEFLATE/zlib, no hash-chain match finder, a flag bit instead of a shared litlen/distance alphabet. The qualitative results generalize (real DEFLATE has the identical floor: ciphertext doesn't compress, a matching prefix does), but the exact bit counts above are this page's own toy cost model, not zlib's.

The leak widget's compressed-bits curve isn't perfectly linear at its very first step — it drops 2 bits from 0 to 1 matched characters, then a steady 7 bits per character from 1 to 8. The reason is the same economicMinMatch threshold DEFLATE's own Pitfalls section already names: this model's cheapest match is 2 characters, so a 1-character match isn't yet worth taking and falls back to a literal, with no separate signal from a 0-character guess. Real DEFLATE has the same floor for a different reason — its own match length range starts at 3 bytes, not 1 — so a real BREACH-style attacker needs a short run of correct guesses before the oracle produces its first visible bit, not a single correct byte.

The 112%-125% ciphertext-compression-ratio range measured above is this page's own window (48), lookahead (20), and flag-bit cost model — not a universal constant. A different window size or a real dual-Huffman-tree format would land on a different number, but the sign never flips: any entropy coder spending bits to flag "literal or match" on a stream with no matches to find pays that flag bit for nothing, the same structural reason DEFLATE's own short-message rows already pay a tree-overhead tax for nothing.