42.zip (2004)
unforgettable.dk
unforgettable.dk
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.
Could this be used as DoS against anti-virus such as the one that GMail uses?
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 ...)
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.
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.
It's not just archive formats, anything which uses standard compression algorithm could be a compression bomb (e.g. PNG)
[1]: ftp://ftp.aerasec.de/pub/advisories/decompressionbombs/pictures/picture-1G-19000x19000.png
This looks like an annoying attack vector for people that, say, resize image uploads to make thumbnails.
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).
Modern computers don't choke on ten million X's on a page, but the fans do spin up wildly. Maybe smartphones die with this.
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.
Ah, I almost forgot we are not spied on. Tried via local email client.
what the fuck?
I posted a link earlier, but here it is again with a quote:
http://www.maximumcompression.com/compression_fun.php
> '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.
[2] What is the most compressed file ever?
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.