Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Can you give me an example of a short data string that, when decompressed using Zlib's DEFLATE method, expands to something much much longer?

More precisely: what is the nastiest decompression bomb that one can build for Zlib's DEFLATE? The figure of merit here is the compression ratio. If the compressed file is n bytes long, and after decompression it yields something m bytes long, then the compression ratio is m/n. I am looking for something that maximizes the compression ratio, where hopefully the compressed data is very short. Can anyone give me an example of such a decompression bomb?


Related: This post claims that DEFLATE can asymptotically approach a compression ratio of 1032; is that the best one can do, or can one achieve a higher compression ratio if we pick a carefully chosen sequence of compressed bytes? Libpng defends against decompression bombs by imposing resource limits, but they don't give a concrete example of a specific decompression bomb. See also zip bombs, the corresponding attack but for the ZIP file format.

share|improve this question

2 Answers 2

zlib deflate is used by gzip. To create ab 10k bomb out of 10M input you might use

dd if=/dev/zero  bs=1024 count=$((10*1024)) | gzip -9 > bomb.gz

And I think the post is right in claiming that you have a maximum ratio of about 1000. More information are at http://www.aerasec.de/security/advisories/decompression-bomb-vulnerability.html (old) but http://blog.cyberis.co.uk/2013_08_01_archive.html shows that most modern browsers still no have protection against it.

share|improve this answer

The source of the "1032:1" figure is given on the zlib site where it is told that:

The limit comes from the fact that one length/distance pair can represent at most 258 output bytes. A length requires at least one bit and a distance requires at least one bit, so two bits in can give 258 bytes out, or eight bits in give 1032 bytes out. A dynamic block has no length restriction, so you could get arbitrarily close to the limit of 1032:1.

This is a quote from Mark Adler, one of the two designers of zlib. Having myself implemented a library for Deflate, I can confirm that, given how the algorithm works, this asymptotic limit is indeed true (you cannot go beyond, but you can get as close as you wish). Deflate works by encoding "copies": each element is either a new byte, or a copy of a past sequence; copies can overlap (i.e. you can copy a sequence of length 30 at distance 4, yielding 15 times the past sequence of 4 bytes); Huffman codes are applied on the sequence of elements. To get a minimal length "copy" you need it to overlap a lot, and each copy is worth at most 258 bytes. So the data which is to be compressed will have to be a long string of identical bytes.

As @Steffen says, compressing with gzip a long sequence of zeros will yield a more than 1000:1 compression ratio. It does not have to be zeros; any sequence consisting of the same byte value over and over will do the trick; but a Linux machine has a /dev/zero, not a /dev/fortytwo.

"Compression bombs" were already active quite a long time ago; I saw it employed to kill Netscape back in 1996 (at that time, Netscape handled background pictures, but Mosaic did not; a very small GIF file could encode a huge background, which Netscape allocated as a single big pixmap in the X11 server).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.