I wonder if it might be possible to prove the existence of fixed points of compression programs using only general assumptions (which would be satisfied by the Lempel-Ziv implementations the author discusses so well).
Such a fixed-point theorem would probably not tell us how to find solutions but it would be illuminating if the assumptions could be made weak enough.
A 42 byte file that expands to 5 MB; a file that compresses in one compression software but not another; a file that compresses to itself; and some extreme compression software.
10 years ago most virus scanners were vulnerable to it.
actually you can build your own collection of files with cat /dev/zero >foo.txt ... then zip all those into a final collection of zip's -> n-levels deep ... resulting individual zip files will be tiny, but once extracted the file eats massive space (idea is to fill disk on scanning server up and create I/O errors or keep the server busy with a DOS). Also servers usually limit now the depth they are willing to scan in a zip to avoid this type of attack (workaround: only use up to 4 levels ...)
Here's an information-theory question: would there be a way to estimate the size of the decompressed output, just given the raw zip data and no size metadata, without attempting to extract it (i.e. without spending time or space proportional to the compression factor)?
It's trivial if you know the zip file contains just a single file. A zip file starts with a "local file header" (see [1]) that contains the compressed and uncompressed size metadata.
So you can decompress the first n bytes of the first file (where n = enough to get a complete header), look at the header, seek past it, then decompress the header of the next file, and so on, recursively.
Unless you meant how to do this without reading the size information from the headers at all, in which case I don't think it would be possible without actually decompressing. There wouldn't be any need to spend "space proportional to the compression factor", though; you would decompress recursively with a pipelined function, but it would just count, not emit, any data. For a 42 KB zipfile, the time required would be near zero.
I don't know whether it's possible with ZIP, but there are definitely compression schemes for which this can be done in time proportional to the size of the compressed file.
So long as it used the usual deflate algorithm, and you don't need to deal with recursive compression as in the article, yes. The size counter program would be structured similarly to the decompression algorithm, but there are some points where the compressed file says "repeat this many bytes from this location" where a decompressor would have to copy that many bytes, where the counter would only have to add the number.
Your answer is wrong. He says "Just given the raw zipped data and no size metadata".
The page calculates it using exactly that size metadata he excluded.
The question, as I see it, is if that size metadata (the 4.3 gigs at the bottom) can be determined from the zip file without unzipping a rather lot of data.
It would be interesting if someone who knew the exact details of the zip format could comment.
There's this[1]. eog doesn't choke on it, but it takes 4GB of RAM during processing. After it return to 2GB.
WARNING: Will decompress to potentially 5GB of RAM.
> So, do we need to change our file uploaders and whatnot to autokill after a certain amount of time? Or just set `ulimit -m` or whatever judiciously?
Most image formats specify the size before providing any data, you can just check that w*h is below whatever limit you deem fit before loading the image data. The file upload size should already have a "sane" limit so people don't upload truckloads of data, the problem with compression bomb is that you can upload a very small amount of data and it eats the target's RAM on decoding.
> This looks like an annoying attack vector for people that, say, resize image uploads to make thumbnails.
It is, although for JPEG you don't need to decode the image to resize it (depending how whatever you're using is implemented it may still do so regardless).
The halting problem only applies to full Turing machines, and their equivalents. So, a compression algorithm based on x86 assembly is uncheckable, but one based on a restricted format like .zip would be fine. Or, you could just give it a time limit.
I made the file DanBC referred to above, and wondered about how much computation you could do with iterated decompression (specifically, deflate-type decompression). Could you make a zip file representing a Turing machine, so that after unzipping it it represented the machine after one step of processing, and after unzipping the result, represented the machine after a second step, etc.
Or if not a direct translation of a Turing machine, then some other Turing complete system.
As far as I know, no one has done this, but if it is possible, one implication would be that you couldn't prove whether the process of recursively unzipping a file could continue forever, or would halt.
Yes. And Google isn't blocking all zip files; or even all password protected zip files. Google just blocks password protected zip files that contain another zipfile.
> Mac users, sending a zip file which also contains another zip file increases your chances of file corruption. We recommend that you de-compress all files first and create only one zip file.
All files at the same "level" are identical. The 4GB file contains zeros only. I think these "data" could be compressed into even smaller size using some different methods.
> 'What is the best compressor to get really extreme compression?' is a question often asked on the internet. The achieved compression ratio of course depends on the quality of the compressor used, but the type of data that is being compressed is much more important. To show this I created a tiny 115 byte rar file. When you decompress it, it will turn into a textfile of almost 5 MB (a compression ratio of 99.998%). Here it is: test.rar. Note: Turtle 0.07 compresses the same file to 49 bytes, Hook09c (with switches 3 1 1 1) to 36 bytes and UHBC (with switches -b128m -m3) to 24 bytes!!.
I enjoy watching this "code golf" style competing to optimise one feature of something.
There's this old discussion about zip bombs:
https://news.ycombinator.com/item?id=4616081
A certain Caspian Maclean published a gzip quine on the Web in 2004, but I cannot seem to find it.
It's rather a pain in the ass for antivirus products, which tend to have a nesting limit to prevent these kind of shenanigans.
There are much weirder things you can do. With knowledge of what's packing it and if the packer doesn't bail out on expanded files (like, say, LZMA2 used in XZ does, but the older LZMA doesn't), you can make a small file which tickles every worst-case performance/size wrinkle in the cruncher and comes out very large!
I thought executable compressors had reached a plateau until Mentor/TBC & Blueberry/Loonies came up with crinkler - http://crinkler.net/ - which is a compressing linker specialised for demoscene 4ktros, and cheats like a motherfucker.
http://research.swtch.com/zip