Comment by fracus

> He found out later (after a defrag) that the "compressor" was just hiding data in unused disk sectors and storing references to them

So you could access the files until you wrote more data to disk?

Ha ha, that compressor is some evil genius.

Brings to mind this 30+ year old IOCCC entry for compressing C code by storing the code in the file names.

https://www.ioccc.org/1993/lmfjyh/index.html

man, a comment that brings back memories. you and me both.

The reason why the discussion in this thread centers around gzip (and brotli / zstd) is because those are standard compression schemes that HTTP clients will generally support (RFCs 1952, 7932, and 8478).

As far as I can tell, the biggest amplification you can get out of zstd is 32768 times: per the standard, the maximum decompressed block size is 128KiB, and the smallest compressed block is a 3-byte header followed by a 1-byte block (e.g. run-length-encoded). Indeed, compressing a 1GiB file of zeroes yields 32.9KiB of output, which is quite close to that theoretical maximum.

Brotli promises to allow for blocks that decompress up to 16 MiB, so that actually can exceed the compression ratios that bzip2 gives you on that particular input. Compressing that same 1 GiB file with `brotli -9` gives an 809-byte output. If I instead opt for a 16 GiB file (dd if=/dev/zero of=/dev/stdout bs=4M count=4096 | brotli -9 -o zeroes.br), the corresponding output is 12929 bytes, for a compression ratio of about 1.3 million; theoretically this should be able to scale another 2x, but whether that actually plays out in practice is a different matter.

(The best compression for brotli should be available at -q 11, which is the default, but it's substantially slower to compress compared to `brotli -9`. I haven't worked out exactly what the theoretical compression ratio upper bound is for brotli, but it's somewhere between 1.3 and 2.8 million.)

Also note that zstd provides very good compression ratios for its speed, so in practice most use cases benefit from using zstd.

In general, this theoretical problem is called the Kolmogorov Complexity of a string: the size of the smallest program that outputs a the input string, for some definition of "program", e.g., an initial input tape for a given universal turing machine. Unfortunately, Kolmogorov Complexity in general is incomputable, because of the halting problem.

But a gzip decompressor is not turing-complete, and there are no gzip streams that will expand to infinitely large outputs, so it is theoretically possible to find the pseudo-Kolmogorov-Complexity of a string for a given decompressor program by the following algorithm:

Let file.bin be a file containing the input byte sequence.

1. BOUNDS=$(gzip --best -c file.bin | wc -c)

2. LENGTH=1

3. If LENGTH==BOUNDS, run `gzip --best -o test.bin.gz file.bin` and HALT.

4. Generate a file `test.bin.gz` LENGTH bytes long containing all zero bits.

5. Run `gunzip -k test.bin.gz`.

6. If `test.bin` equals `file.bin`, halt.

7. If `test.bin.gz` contains only 1 bits, increment LENGTH and GOTO 3.

8. Replace test.bin.gz with its lexicographic successor by interpreting it as a LENGTH-byte unsigned integer and incrementing it by 1.

9. GOTO 5.

test.bin.gz contains your minimal gzip encoding.

There are "stronger" compressors for popular compression libraries like zlib that outperform the "best" options available, but none of them are this exhaustive because you can surely see how the problem rapidly becomes intractable.

For the purposes of generating an efficient zip bomb, though, it doesn't really matter what the exact contents of the output file are. If your goal is simply to get the best compression ratio, you could enumerate all possible files with that algorithm (up to the bounds established by compressing all zeroes to reach your target decompressed size, which makes a good starting point) and then just check for a decompressed length that meets or exceeds the target size.

I think I'll do that. I'll leave it running for a couple days and see if I can generate a neat zip bomb that beats compressing a stream of zeroes. I'm expecting the answer is "no, the search space is far too large."

It’s a zip bomb, so does the creator care? I just mean from a practical standpoint - overflows and crashes would be a fine result.

> There's literally no machine on Earth today that can deal with that (as a single file, I mean).

Oh? Certainly not in RAM, but 4 PiB is about 125x 36TiB drives (or 188x 24TiB drives). (You can go bigger if you want to shell out tens of thousands per 100TB SSD, at which point you "only" need 45 of those drives.)

These are numbers such that a purpose-built server with enough SAS expanders could easily fit that within a single rack, for less than $100k (based on the list price of an Exos X24 before even considering any bulk discounts).

That's far from the ultimate zip bomb.

42.zip has five layers. But you can make a zip file that has an infinite number of layers. See https://research.swtch.com/zip or https://alf.nu/ZipQuine

Do must unzip programs work recursively by default?

I mean, if I make a new compression algorithm that says a 10GB file of zeros is represented with a single specific byte, that would technically be compression.

All depends on how much magic you want to shove into an "algorithm"

No lossless algorithm can compress all strings; some will end up larger. This is a consequence of the pigeonhole principle.

But of course there is. Imagine the following compression scheme:

    0-253: output the input byte
    254 followed by 0: output 254
    254 followed by 1: output 255
    255: output 10GB of zeroes

Of course this is an artificial example, but theoretically it's perfectly sound. In fact, I think you could get there with static huffman trees supported by some formats, including gzip.