DEFLATE, gzip and zlib

programmingweb devsecurity

The compression algorithm inside ZIP, PNG, Git and most of the web; the file format that wraps it; and the library that implements both.

The compression algorithm inside ZIP, PNG, Git and most compressed web traffic; gzip is the file format wrapping it, zlib the library nearly everything calls.

Three names for closely related things, and separating them is the first step to not being confused by them. DEFLATE is the algorithm. gzip is a file format wrapping DEFLATE with a header, a checksum and a length. zlib is both a slightly different wrapper and, more importantly, the library almost everything actually uses to do any of it. DEFLATE itself is two old ideas stacked. First LZ77: as you read the input, replace anything you have seen before with a short reference back to where you saw it, so the second occurrence of a repeated phrase costs a few bytes instead of its full length. Then Huffman coding: having produced that stream of literals and back-references, count how often each symbol occurs and give the common ones short codes and the rare ones long codes. Neither half was new when DEFLATE was specified in 1951 - the RFC number is a coincidence worth enjoying - and the combination is not clever so much as extremely well balanced: fast enough to run on everything, good enough that improving on it rarely justifies the change. The result is probably the most-executed compression algorithm in history, and almost nobody can name it. It is inside every ZIP file, every PNG image, every Git object, and every HTTP response served with content-encoding gzip, which is to say most of the web. The reason gzip exists at all is a patent, and this is the part worth knowing. Unix had a compression tool called compress, which used LZW - an algorithm covered by Unisys patents, the same patents that made GIF legally uncomfortable for years and eventually pushed the web toward PNG. Jean-loup Gailly and Mark Adler wrote gzip specifically to be a free replacement that infringed nothing, and zlib followed as the reusable library. Both outlived the patents, the tool they replaced, and the format the patents damaged. A patent intended to capture a market instead motivated the free thing that replaced it - which is the same shape as the lawsuit that produced ZIP, in the same decade, in the same corner of computing. One security consequence deserves stating because it surprises people who understand both halves separately. Compression leaks information about what it compressed. If an attacker can inject text into something that is compressed and then encrypted, they can learn whether their guess appears elsewhere in the plaintext by watching the compressed length change - guessing a secret one character at a time without breaking any cryptography. That is the mechanism behind the CRIME and BREACH attacks, both of which have their own entries here. Encryption hides content; it does not hide size, and compressing before encrypting turns size into a channel. The practical rule is unglamorous and absolute: do not compress attacker-influenced data together with secrets in the same encrypted stream.

Also known as: deflate, gzip, zlib, gz, content-encoding gzip, rfc 1951, rfc 1952

← All glossary entries