The Spider I Promised

A little over a year ago when I gave the Designer Compression talk at HOPE, I made a few promises. This post is about one of them, others are soon to follow.

DeflateDefector is a script that pops the hood of deflate data and warns you about anything suspicious or out of spec that it finds. It was a naive PoC that was only tested on anything artificially out of spec that I could create and throw at it. And most of it was crazy out of spec. I wouldn’t expect to find any “normal” DEFLATE show up as suspicious with this tool. But I did promise to spider a portion of the web and try to find anything truly crazy. What I found instead was a bunch of out of spec DEFLATE that was that way for legitimate reasons. This was interesting in its own right. Half of this post is about that. The other half is about the features I bolted on to the tool in this process.

For reference, this is the tool: github.com/XlogicX/DeflateDefector

The Hunt

I first directed my corpus scanning locally; on my own filesystem. So this was file types of gz, png, zip, whl, jar, epub, and office.

files scanned: 44,618
"suspicious" files: 23,028

So this is where I found that I fucked up and needed to do some tuning. Of all of my individual heuristics the quantity triggered were:

underutil: 34,682
split: 2,782
repeat: 818
empty: 478
sussymbol: 214

This was all stock zlib. It’s not that the heuristics were conceptually wrong, just my thresholds. Tuning these thresholds substantially changed the results to:

files scanned: 44,614
suspicious files: 2

Those last two where in the ‘split’ heuristic and I accepted them as being unusual enough to not tune.

Local was a good start, but it was really only made up of zlib and libpng as the encoders, so I needed to reach out to the web for diversity, which was my promise more than a year ago. I turned to Tranco for the top 1 million domains and saved the raw deflate. Of course almost half of them were unreachable, but about half a million is still good.

files scanned: 533,634
suspicious files: 195 (153 of those were just malformed though)

I would categorize the remaining suspicious files (after above said tuning) into 4 buckets. Again, none of them suspicious or stego laden, but most of them interesting in my point of view.

Google Fuckery

When it comes to optimization, this one is actually pretty cool

Zopfli, and every PNG optimizer built on it, does not build a Huffman tree from the symbol counts. It builds one from counts it deliberately falsified first. The function is OptimizeHuffmanForRle in zopfli’s deflate.c. It walks the count array, finds stretches of 4 or more similar counts, and averages them down to a single value.

Why? Because the code-length table itself gets RLE-compressed in the block header. Flat stretches of equal lengths pack into repeat codes; jagged ones don’t. So zopfli distorts the frequencies to make its own header smaller, and eats the small loss in the data section. The compressed payload nets as smaller overall. So yes Google is going against the RFC1951 spec, but because it creates a smaller compressed payload.

The tree it emits is optimal for counts that are a lie. Judged against the true frequencies, it contains inversions: a rarer symbol coded shorter than a commoner one.

A frequency inversion is exactly the signature of a table stuffed to hide data in cheap codes on rare symbols. It’s the tell I built sussymbol around. So benign optimized PNGs looked like stego to my tool, about 5.7% of them.

The fix was to stop guessing and port OptimizeHuffmanForRle into the detector (Apache 2.0, Copyright 2011 Google Inc.; it’s attributed in NOTICE and on the function itself, since this is a GPLv3 project). statcheck() now builds two reference codes: the canonical Huffman code for the real counts, and the code for zopfli’s distorted counts. A symbol only gets flagged if it’s at least 2 bits shorter than both.

To be suspicious now, your table has to beat what an honest encoder produces while that encoder is lying on purpose.

There’s a second gate stacked on it, because the first one alone is still too fickle. A stuffed table buys its cheap codes with real waste; coding the block under the transmitted table costs meaningfully more than the optimal table for its own counts. A benign encoder’s mild inversion is paid back elsewhere and stays near optimal. So if the table is within 1.7% of optimal, whatever looks too short is redistribution, not stuffing. My unbalancedhuff2 PoC wastes 8% and clears that.

Zopfli was truly interesting to learn about and now DeflateDefector sees it as normal (normal enough to not flag it).

A New Fixed Mode

While fingerprinting tables across the crawl, one fingerprint kept coming back. Internally, I named it 36c05df387732013 (I was hashing them). 286 coded symbols. gzip with XFL=4 and MTIME=0. 12,731 unique domains had the identical Huffman table regardless of content.

Some CDN fast path has a precomputed table compiled in and serves it to everyone. I still don’t know whose it is (I have my guesses, none of them confirmed, so I’m not naming anyone). You can look at it and tell what it’s for; len258 gets a 3 bit code, and the 6 bit codes are NL SP a e i l o r s t. It’s tuned for HTML and nothing else.

Structurally this is a dynamic block header carrying a table that has nothing to do with the data underneath it. This of course triggers my underutil heuristic that checks the statistics of the un-encrypted content to make sure it agrees with the Huffman Table (which has the statistics implicitly baked in)

So I made a registry (called static_tables.json) for this common fixed table and for future ones I might find (…of which I never did find any new ones beyond this one). The idea is that anything in this registry is allow-listed past my suspicion heuristics.

Depth Caps

libdeflate and igzip cap how tall their Huffman trees get, so decoding stays fast. The side effect is that a rare symbol that a by-the-book code would bury deep gets pulled up to the cap instead, and comes out shorter than it “should” be. That short code is exactly the heuristic I’m hunting for in a stuffed table, so I had to work out how to tell the two apart.

My known-good sample for this is a plain text file run through libdeflate: the 1986 Phrack “Hacker Manifesto” (The Mentor’s “Conscience of a Hacker”), nothing hidden in it, just an honest encoder doing its job. Its distance tree caps at 7 bits, and a distance that shows up exactly once gets coded in 7 bits where an uncapped code wants 9. Two bits short, carrying nothing. mollie.com does the same thing out in the wild with an 11 bit distance tree.

Here’s the tell. A cap can only make codes shorter than ideal. What it can’t do is flip the ordering: in any honest table, a symbol that shows up more often never gets a longer code than a rarer one. More common, shorter or tied, always. A cap respects that; a stuffed table breaks it, handing a rare symbol a short code while something more common still carries a longer one.

So a short code on its own isn’t a finding. I only flag it when a more-common symbol above it carries a longer code. unbalancedhuff2’s 3 bit codes sit under commoner 5 bit codes, which no real encoder would ever produce. The manifesto’s cap-pinned rares have no commoner-yet-longer symbol above them, so they walk.

The Honest Envelope

The other half of the tool measures waste rather than table shape, and my first version measured it against zlib-9. That’s useless on the real web. Fast and streaming encoders sit 20 to 40 percent off zlib-9 completely legitimately, and I was calling all of them wasteful. Which makes for a shit detector; “this site uses a fast encoder” is not a finding.

So the question got inverted. Not “how far is this from the best?” but “is this bigger than even the worst honest encoder could have produced?” And the profiles it gets compared against have to be earned by evidence in the stream:

• zlib-1 single shot; always granted, it’s the floor of standard tooling
• plus sync-flush replay, only if the stream actually carries flush markers, and replayed at the stream’s own offsets. The stream declares its cadence
• plus full-flush replay, only if additionally no match crosses a marker (that’s what a real window reset means)
• small-window replay, at the smallest legal window that covers the largest distance the stream actually used

That last one exists because encoders in the wild really do this. gla.ac.uk caps at 762 bytes. Something else in the Tranco top 20k caps at 3,834. Those streams run 48 to 71 percent bigger than a full-window zlib-1 replay they never had access to, and claiming a small window costs you every longer back-reference, so it isn’t a free allowance.

Calibrated: benign-weak tops out around +39%. Crafted true positives measure +93% to +1500%. The margin sits at +45%, in the empty band between.

Two more corrections from the same corpus. The ‘repeat’ detector has to measure the 32K window in decompressed bytes, not literal token offset; matches between the two copies advance the real distance, so a repeat that looks close in the token stream can be well past 32K where no back-reference can reach. That single fix explained about 95% of naive repeat hits on a 9,000 file corpus. And the split detector was grouping same-distance matches while ignoring literals between them, which read as a 0.87 over-split fraction on stock PNG icons. A literal shifts the copy source, so a run breaks on any literal now.

New Flags

The research end pushed some features out the other side.

–rip reconstructs a payload out of the under-allocated blocks and hexdumps it. That was there before, and it was useless, because a hexdump isn’t a file. So now –rip-out PATH writes the raw reconstruction, all ripped blocks concatenated.

One of my other promises from the HOPE talk was to release the ‘encoding’ tool side of all of this; the tool that creates the nonsense that DeflateDefector is intended to catch. This tool is called DeepFlate. When it embeds data in a DEFLATE stream it is helpful to give it a little bit of metadata at the start so the decoding side (DeflateDefector) knows how much data to carve out (to the file). Of course you could still just view raw data and not encode metadata like many of my PoCs before DeepFlate. However, the new –deframe argument will interpret the frame for this information and remove the frame on the output file. The frame starts with the ‘magic’ number of ‘DF’ (DeepFlate), a version byte, a 32 bit big-endian length, and then zero pads on the last block.

A–data now takes an http(s) URL and analyzes what the server actually put on the wire. This matters more than it sounds. urllib doesn’t transparently decode the way requests does, so resp.read() hands back the exact compressed bytes. It advertises gzip and deflate only, never brotli or zstd. It de-chunks transfer encoding and nothing else. HTTP error bodies get analyzed too, because a 404 body is still a compressed body and nobody looks at those (right?).

Under all of it, extract_streams() is the one place that knows how to open a container: gzip, zlib, PNG, the ZIP family (.zip/.whl/.jar/.apk/.docx), PDF /FlateDecode objects, git packfiles, SWF, WOFF, TIFF, Minecraft .mca region files, pcap. scan.py imports the same function, so bulk scanning and single-file analysis can’t drift apart.

There’s also –deep, which recompresses the sample with every encoder on the box (zlib 1/6/9, pigz -11 for zopfli, libdeflate-12, gzip-9) and reports the range. Being worse than zopfli is normal; most things are. Being bigger than the weakest tool present means no standard compressor makes output that large. It’s context, not a verdict, and it can’t tell hand-crafted from a weak unknown encoder.

PoC

xlogicx.net, I wont say any more than that. And if you do get more data than just the html…are you done yet?