Earlier quoted context omitted.
Zip bombs, a relative of the fork bomb. https://en.wikipedia.org/wiki/Zip_bomb The billion laughs XML attack is also lovely in its simplicity. https://en.wikipedia.org/wiki/Billion_laughs
I was doing a presentation about various bombs last year and crashed PowerPoint by copy-pasting billion laughs in a slide. Simple but extremely effective.
Biggest image in the smallest space
101–106 of 106 posts
Re: Biggest image in the smallest space
#102Earlier quoted context omitted.
The file that decompresses to itself is a work of art. How does one even go about to create something like this?
I have no idea. There are people who take special interest in compression. The Hutter Prize would be a good place to find them. http://prize.hutter1.net/ It's a bit old now. > Restrictions: Must run in I'd be interested to see what can happen without those restrictions.
If you did not have time limits you could exhaustively search through Pi looking for your data, then store just the offset into Pi.
Or if the offset got too large then Pi to the power of lots of random numbers. One of those numbers will, somewhere, have your data. But it's infeasible to search for it.
Re: Biggest image in the smallest space
#103Everyone's focusing on this being a PNG problem but actually if my server unzips a 420 byte file into a 5M file of any kind, I'd say that's the first red flag. Assuming some sort of streaming decompression, you could write an output filter that shuts off the decompressor when it's seen a factor of X bytes. A reasonable factor would be 10 - which in this case would have halted bzip decompression at 4kB. This would pro…
The real problem is image handling libraries that blindly render images into too-large objects where unnecessary. While full-res uncompressed images are very convenient under the hood, the image library should inherently handle anything "too big" gracefully. Instead we're often prone to apps crashing when someone feeds in a ridiculously large image. A 420B > 5MB expansion should not be a "red flag" because there is n…
There is an upper-limit to how much information you can compress into a given space. (Note that we may want to write a pathological program that is very small and allocates a lot of information-free memory. But that's not decompression.)
If we accept the premise then we can look at another approach to solving this problem, once and for all! I like examining memory allocation because it's so general. But there may be another way. We can examine the input to estimate compression ratio.
The problem here is that image decompression is apparently giving strangers the ability provide an arbitrary N and say "Please loop N times and/or allocate N bits". A modern CPU is overwhelmed by an N 12 bits long or longer. This is a root cause of many problems! You know, I'm going to go out on a limb here and make a bold assertion: I assert there is a very safe upper bound on the decompression ratio, and that for any real algorithm you can indeed examine the input to determine whether N exceeds your allowable threshold. 10x might be a bit low (although I doubt it) so let's be generous and say 100x. (Which seems crazy. Nothing that I know of, not even text, compresses that well.) This means that I believe that any image format, for example, has a trivially calculable N (for example, width*height in pixels). I would argue that in the general case (unless you are doing some sort of compsci research) the image file should be related to N. That is if the image is 10 bits wide, 10 bits high, we should expect a roughly 20bit file-size.
Re: Biggest image in the smallest space
#104Earlier quoted context omitted.
I have no idea. There are people who take special interest in compression. The Hutter Prize would be a good place to find them. http://prize.hutter1.net/ It's a bit old now. > Restrictions: Must run in I'd be interested to see what can happen without those restrictions.
> I'd be interested to see what can happen without those restrictions. If you did not have time limits you could exhaustively search through Pi looking for your data, then store just the offset into Pi. Or if the offset got too large then Pi to the power of lots of random numbers. One of those numbers will, somewhere, have your data. But it's infeasible to search for it.
There is no universal compression algorithm, by the pigeonhole principle.
And your compression scheme won't work by the simple fact that the offset of where in Pi your data lies will, on average, take the same number of bits to store as the data itself. Ditto, with pi to the power of lots of random numbers, the offset and the power will, on average, take the same number of bits to store as the data itself.
Re: Biggest image in the smallest space
#105That's impressive. Here are some other compression curiosities. http://www.maximumcompression.com/compression_fun.php A 24 byte file that uncompresses to 5 MB; another file with good compression under RAR but almost no compression under ZIP; and a compressed file that decompresses to itself.
Malware scanners that search inside archives really love zips that decompress recursively forever.
It should be possible to write an archive file that decompresses to a slightly different archive file. Say, the original archive file plus a zero byte. (Things get hairy because of the checksum in most archive file formats, but it still should be possible.)
Then a malicious party writes an archive file that decompresses to two slightly different archive files. And sets it up so that, say, 128 levels in iff you follow a specific path in said tree you get to the actual malicious content. You can't get to it unless you follow the specific path, and you can't find it unless you do substantially more than just naively decompressing files (as you won't be able to decompress 2129-1 files).
Re: Biggest image in the smallest space
#106That's impressive. Here are some other compression curiosities. http://www.maximumcompression.com/compression_fun.php A 24 byte file that uncompresses to 5 MB; another file with good compression under RAR but almost no compression under ZIP; and a compressed file that decompresses to itself.
Maybe someone takes the recursive file to a new level and creates one that generates to n new identical files. So decompress to a tree.