8 ms·
Biggest image in the smallest space
- michaelmior 11y agoActually, it decompresses to a 5.8MB PNG. However, many graphics programs may choose to use three bytes per pixel when rendering the image and because it has incredibly large dimensions, this representation would take up 141GB of RAM.
- fla 11y agoAnd almost every program that tries to display it.
- wiredfool 11y agoSome image programs will allocate space based on the metadata in the file. The actual image data isn't actually required. So, if there's corrupted image data, say a byte or two (or even missing), there's nothing stopping the reported size being in the gigapixel range.
- jerf 11y agoOne of the rules of secure programming is that any program that is used in an even remotely security-sensitive context, and anything displaying a Portable Network Graphic is likely to be used in such a context, must be able to specify resource usage limits. In this case that could be dimensions or a limit on the total RAM allowed to be used. Limits need not be hard, either, but could produce a query, for instance, the way very long-running scripts in the browser ask you if they should continue. Now, go find an API/library for dealing with PNGs that allow you to pass in such a limit, let alone pass in a callback for dealing with violations. Go ahead. I'll wait. (The Internet being what it is, if there is one, someone will pop up in a reply in five minutes citing it. If so, my compliments to the authors! But I think we can all agree that in general image APIs do not offer this control. In fact, in general, if you submit a patch to allow it, it would probably be rejected from most projects as unnecessarily complicating the API.) This is the sort of thing that I mean when I say that we are so utterly buried by insecure coding practices that we can't hardly even perceive it around us. I should add this as another example in http://www.jerf.org/iri/post/2942 http://www.jerf.org/iri/post/2942 .
- phkahler 11y agoUltimately it's going to require a malloc to get the space for all those pixels. That is where things should fail. If not, how is one to specify what the image size limits should be? Ever try to open the Blue Marble images from NASA? In a web browser? Back in 2001?
- to3m 11y agoAny decent library (of any sort) should already be providing hooks for its memory allocation. This isn't necessarily provided as a security feature, and it's common for your callbacks not to get much in the way of information about what's going on, but it will allow you to at least crudely put a cap on the library's memory usage.
- silon7 11y agoulimit may help. Perhaps it could (maybe already is) be added to Chrome per-tab process. Not sure of Windows equivalent, Microsoft has deprecated Windows System Resource Manager, not sure of a good equivalent (except going fully to Linux).
- pierrec 11y agoYou're overdoing it a bit. I believe the most popular API/library for server-side manipulation of images is ImageMagick, and it has a few options for specifying limits that will easily protect against decompression bombs. That being said, even with these limits, it's undeniable that something like ImageMagick still has a very large attack surface (especially since it uses many third-party libraries), so it should run in its own heavily unprivileged or sandboxed process.
- jerf 11y agoI should have added my "no credit for showing the existence of limits if your code doesn't use them" criterion in advance. Now it looks like I'm moving the goal posts. Oh well; you can see a similar point in my linked post from several months ago which at least adds credence to the idea that this isn't a new reaction of mine. As you can see by reading that post as well, I'd also contend it really ought to be in the core API, not an optional thing that defaults to no limits. A sensible default could be imposed, too, though that turns out to be tricky to define the closer you look at it.
- userbinator 11y agoBetter graphics programs will not attempt to put the whole image into RAM, but only decompress the pieces needed for processing it. I remember working with multi-megapixel images on systems with far less than 1MB of RAM, many years ago. Perhaps this is a good example of how more hardware resources can lead to them being wasted - the fact that RAM has grown so much that most images fit completely in it, has also meant programmers assuming they can do this for all images without a second thought when often all that's needed is a tiny subset of all the data. Even if the image data is compressed, there's absolutely no need to keep all of it in memory - just decompress incrementally into a small, fixed-size buffer until you get to the "plaintext" position desired, ignoring everything before that. The fact that it's compressed also means that, with suitable algorithms, you can skip over huge spans at once - this is particularly easy to do with RLE and LZ - and the compression ratio actually boosts the speed of seeking to a specific position. Currently, (hopefully...) no application is attempting to read entire video files into memory before processing them, but I wonder if that might change in the future as RAM becomes even bigger, and we'll start to get "video decompression bombs" instead?
- dahart 11y agoThis! Command line programs have no excuse, they should never need to decompress the entire file to memory. GUI image editors and web browsers probably generally do need to, but there definitely are such options for dealing with more pixels than you can display. Anyway, do you know some of these "better" graphics programs that actually behave this way, especially command line processing? I am interested in finding more of them. EDIT: Okay, I have to add & admit that by "no excuse", I actually mean somewhat the opposite. ;) I mean that its possible to do streaming image processing on compressed formats, not that its trivial to do or as easy as decompressing the file in a single call. I just wish that programs would handle very large images more, and it sucks when they don't even though I know its possible. Especially programs intended for dealing with large images like Hugin. Now, I know its a PITA to tile & stream compressed formats because I've done it, but I'm sure I've written image I/O that decompresses the entire file to RAM 100x more frequently than anything that tiles and/or streams, because I've only handled tiling or streaming myself once, and it was harder. :P
- ctdonath 11y agoLooks handy for large image processing tests, thanks.
- JosephRedfern 11y agoThat's cool. Presumably the same "attack" could be applied to any file format that uses DEFLATE. From a legal stand-point, I'd be wary about following through with the authors suggestion of "Upload as your profile picture to some online service, try to crash their image processing scripts" without permission. Sounds like a good way of getting into trouble.
- cnvogel 11y agoYes, but on the other hand it's a good reminder for everyone processing user provided files to sanity check or convert them to a canonical format in a sandboxes and resource limited process.
- atom_enger 11y agoWhat about responsibly disclosing the bug you found with steps to reproduce, the impact and the solution? As long as you only timed out the backend without entirely crashing it, I can't imagine any sane company would prosecute you for trying to improve their service with this level of detail.
- JosephRedfern 11y agoHow do you know that you're only going to time out the backend without entirely crashing it, without actually attempting it? It's a kinda Schrödinger's cat scenario. It's all good and well saying that you had good intentions, but if you can't prove it, and they didn't invite you to test it (via a responsible disclosure policy), then I would steer clear. While I wouldn't personally attempt to prosecute anyone for responsibly disclosing a bug to me, it doesn't meant to say that BigCorp™ wouldn't.
- wiredfool 11y agoPNGs also have optional compressed text metadata chunks, and it's possible to sneak a decompression bomb into one of those as well. You can get about a factor of 1000 in the compression -- 1MB of 'a' winds up being about 1040 bytes. You can have multiple itxt chunks, and it appears that the chunk size is only limited to 2^31-1. See https://github.com/python-pillow/Pillow/blob/master/Tests/check_png_dos.py https://github.com/python-pillow/Pillow/blob/master/Tests/ch... for a quick way to generate some of these.
- 0x0 11y agoThat's neat, but I still think the self-reproducing r.zip from "zip files all the way down" is the best compression trick I've seen: http://research.swtch.com/zip http://research.swtch.com/zip
- dmit 11y agoThere's also dynamic generation of output by specifying a custom filter in a RAR archive that is executed during decompression: http://blog.cmpxchg8b.com/2012/09/fun-with-constrained-programming.html http://blog.cmpxchg8b.com/2012/09/fun-with-constrained-progr...
- DanBC 11y agoThat's impressive. Here are some other compression curiosities. http://www.maximumcompression.com/compression_fun.php 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.
- sulami 11y agoThe file that decompresses to itself is a work of art. How does one even go about to create something like this?
- quarterto 11y agoLike this: http://research.swtch.com/zip http://research.swtch.com/zip. Fascinating read.
- Cyph0n 11y agoWritten by THE Russ Cox?
- DanBC 11y agoI 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/ http://prize.hutter1.net/ It's a bit old now. > Restrictions: Must run in <10 hours on a 2GHz P4 with 1GB RAM and 10GB free HD I'd be interested to see what can happen without those restrictions.
- ars 11y ago> 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.
- inglor 11y agoThis does wonders when used in favicons :D
- feld 11y agoYou just made my stomach turn at the thought
- raffomania 11y agoI just tried it on a locally served page, and my browser handles it quite well (although it won't really display it).
- inglor 11y agoOnly on firefox and chrome since they fixed it https://github.com/benjamingr/favicon-bug https://github.com/benjamingr/favicon-bug
- andersthue 11y agoReminds me of how you could crash a fido node by sending them some big empty files, so when they got automatically unzipped the filled of the harddrive :)
- fizgig 11y agoI think this kind of thing was common even a few years ago in DoS'ing mail gateways that uncompressed and scanned various archive formats. Things like really huge files when uncompressed or ridiculously deep nested directory structures. I think most software these days is immune to such tricks, or at least has tunables to reduce the chance of such tricks causing harm.
- dingaling 11y agoThere was also the trick of infinitely recursive zips that kept decompressing to a copy of themselves. Zip-bombing was such a problem for our corporate network in the late 1990s that inbound e-mail attachments were deliberately discarded for a while. Chaos ensured.
- digi_owl 11y agoZip bombs, a relative of the fork bomb. https://en.wikipedia.org/wiki/Zip_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 https://en.wikipedia.org/wiki/Billion_laughs
- Koahku 11y agoI was doing a presentation about various bombs last year and crashed PowerPoint by copy-pasting billion laughs in a slide. Simple but extremely effective.
- digi_owl 11y agoNot sure what is worse: that MS has Powerpoint interpreting randomly pasted XML, or that they do not have handling for excessive memory usage beyond crashing the whole program.
- andrewstuart 11y agoIs there a way to check for decompression bombs? I'd like my software to be able to unzip zip files safely.
- MatthewWilkes 11y agoA python example: def decompress(data, maxsize=262144): dec = zlib.decompressobj() data = dec.decompress(data, maxsize) if dec.unconsumed_tail: raise ValueError("Possible zip Bomb") del dec return data
- ZenoArrow 11y agoMonitor zip files as they decompress. Halt decompression process if the size ratio between zip file and decompressed file exceeds a fixed ratio (for example, if ratio between the file sizes is something like 10:1).
- Ambroos 11y agoIf you do that, pick something a little more extreme. When using BEM, for example, your CSS becomes pretty repetitive and you easily get better than 10:1 ratio with GZIP, for example.
- wglb 11y agoYes. A method whose only purpose is to answer the question 'is this file larger than <parameter>'. If it is don't go further.
- wiredfool 11y agoYou can do it in zlib -- there's one call that effectively does the whole thing, and one that fills a buffer. You can check to see how much input has been consumed, if there's more, then you know you're getting large. It's up to the friendly programmer to decide when large is too large.
- bluedino 11y agoSandbox them. We once created a 1024MB, 6GB disk single-core VM and built a tiny API around image decompression and scaling. Never had any issues with it, but it was a simple way of preventing things from filling up the regular web servers.
- _hhff 11y agorighto pied piper
- raffomania 11y agoFun fact: When trying to upload this as a profile picture (on a site I host myself), chromium crashes.
- pvdebbe 11y agoCool, but most web sites wouldn't allow to upload a 5-MB picture as a profile picture. Or do they, these days?
- eli_gottlieb 11y agohttp://jeremykun.com/2012/04/21/kolmogorov-complexity-a-primer/ http://jeremykun.com/2012/04/21/kolmogorov-complexity-a-prim... http://c2.com/cgi/wiki?KolmogorovComplexity http://c2.com/cgi/wiki?KolmogorovComplexity Here be rabbit-hole.
- semi-extrinsic 11y agoIf you follow the "related reading" link on the bottom of TFA, you come to a page by Glenn Randers-Pehrson discussing how libpng deals with decompression bombs. On the bottom of that page you find the following curious note; anyone know what to make of it? """ [Note for any DHS people who have stumbled upon this site, be aware that this is a cybersecurity issue, not a physical security issue. Feel free to contact me at <glennrp at users.sourceforge.net> to discuss it.] """
- saalweachter 11y agoHe's presumably had problems with people confusing "decompression bombs" with the blowy-up kind and sending him panicky e-mails.
- semi-extrinsic 11y agoAh, of course. That didn't even cross my mind, for some reason; bomb in this context was so obviously not a physical device.
- cperciva 11y agoAnother possibly apocryphal case of linguistic collisions resulting in governmental interest: When the MIT Media Lab started doing work on intelligent kitchen counters, they found that a lot of shadowy government agencies wanted to talk to them about their research into "counter intelligence".
- fennecfoxen 11y agoWhat to make of it? Seems clear enough; he's (half-jokingly?) afraid that someone in the federal government will see the page and think "oh no! bombs! explosions! TERRORISM!" and identify more clearly that this is only a computer analogy.
- nerdy 11y agoI think it is related to the word "bomb" existing on the page
- octatoan 11y ago
- logicallee 11y ago>The image is almost entirely zeroes, with a secret message in the center. too pressed for time, did anyone look? What is it?
- sgdread 11y agoIt is "SORRY, OUR PRINCESS IS IN ANOTHER PIXMAP"
- AndrewStephens 11y agoI used to work on a scanning SMTP/HTTP proxy and even back then it wasn't unknown for people to send crafted decompression bombs to attempt to crash the services. We handled it by estimating the total uncompressed size upfront (including sub archives) and throwing out anything with a suspiciously large compression ratio. I imagine that .pdf files are another avenue for mischief. They contain lots of chunks which may be compressed in varying ways.
- hadeharian 11y agoThis is a very easy form of attack in security circles.
- dahart 11y agoHaving dealt with and printed a lot of very large images, e.g., 60k x 60k pixels, I have been on the lookout for image processing software that never decompresses the entire image into ram, but instead works on blocks or scan lines or blocks of scan lines, but stays in constant memory and streams to and from disk. For example, the ImageMagick fork GraphicsMagick does a much better job of this than ImageMagick. What other software is out there that can handle these kinds of images?
- phkahler 11y agoThe key is not to store it in raster form in RAM. Either tiles (like GIMP) or I prefer Z-ordering. Then a user can zoom in and pan around easily - you let the system swap and it won't be bad at all. If they zoom out though, you probably want to store MIP maps of it. Swap works well for this as long as your data has good locality. huge raster images don't. But no, I'm not aware of any software that handles stuff like that well - except the GIMPs tiling, but that's not going to help when zoomed out.
- dahart 11y agoWhat does Z-ordering mean in this context? I definitely want to avoid swap at all costs and find things that are designed to tile & stream instead. The difference between GraphicsMagick resizing an image by streaming and ImageMagick resizing an image that hits swap is orders of magnitude - seconds versus hours.
- phkahler 11y ago>> What does Z-ordering mean in this context? You divide the image into quarters and store each quarter as a continuous block of memory. Do this recursively. Normally we'd index into the pixel data using pixel[x,y]. You can get Z-ordering by using pixel[interleave(x,y)] where the function interleave(x,y) interleaves the bits of the two parameters. This works fantastically well when the image is a square power of two, and gets terrible when it's one pixel high and really wide. I think a combination of using square tiles where each one is Z-ordered is probably a useful combination. For my ray tracer I use a single counter to scan all the pixels in an image. I feed the counter into a "deinterleave" function to split it into an X and Y coordinate before shooting a ray. That way the image is rendered in Z-order. That means better cache behavior from ray to ray and resulted in a 7-9 percent speedup from just this one thing. Once you have data coherence, swapping is not a big deal either in applications where you're zoomed in.
- ak2196 11y agoIt's probably using middle-out.
- atom_enger 11y agoTrying to run the program and create my own image, however a few questions, what did you use for secret.png? Any old png? Are you using PIL or pillow?
- tetrep 11y agoNeat. I needed to make very large PNG bombs recently and toyed with the idea of doing it "manually." In the end I decided to take the lazy route and use libpng[1]. [1]: https://bitbucket.org/tetrep/pngbomb/src/03dfc95065d78562c156c056abc3d5f1fd7047b8/pngbomb.c?at=master https://bitbucket.org/tetrep/pngbomb/src/03dfc95065d78562c15...
- x0 11y agoThis works wonderfully! With an image size 123456x123456, I made this happen: http://i.imgur.com/2Dgrazj.png http://i.imgur.com/2Dgrazj.png I killed it at about 25GB memory usage, who knows how high it would have climbed otherwise.
- __mp 11y agoPhotoshop was able to show it: http://i.imgur.com/7EdBySv.png http://i.imgur.com/7EdBySv.png (Macbook Pro, 16GB RAM)
- userbinator 11y agoPhotoshop is an example of a graphics program that doesn't attempt to read the entire image into memory. How much RAM did it actually use?
- __mp 11y agoDifficult to say. I don't completely understand the activity monitor RAM column: http://i.imgur.com/QS3NPQQ.png http://i.imgur.com/QS3NPQQ.png Looking at the activity monitor details we see that it uses something in the order of 2.54 GB of real memory. I suspect the rest is mostly compression.
- anilgulecha 11y agoTells you why it's a solid image application. Kudos to them.
- hnpc123 11y agoThe title was changed and is now more opaque and less descriptive.
- fekberg 11y agoYeah, I agree. The original title was a lot more descriptive.
- javajosh 11y agoEveryone'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 probably be a trivial patch to bzip2. But I like the idea in general of passing an "max input/output ratio" to any process or function that might yield far more output than input.
- ctdonath 11y agoThe 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 nothing about it (including the subsequent attempt to process a 141GB uncompressed image) which cannot be handled appropriately in software. Flagging such ratio limits is arbitrary, and setting an arbitrary limit is usually a sign the software is incorrect, not the data.
- javajosh 11y agoA ratio limit is a hueristic. 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.
- mridulmalpani 11y agodoes anybody tried to upload it on facebook as profile picture?
- MrKristopher 11y ago"Your photo couldn't be uploaded due to restrictions on image dimensions. Photos should be less than 30,000 pixels in any dimension, and less than 41,000,000 pixels in total size."
- TurplePurtle 11y agoI wonder what the ratio would look like if the equivalent was done with a JPEG instead of a PNG.
- tiler 11y agoI realize that this is besides the point but going on the title alone we could write a script that could generate an 'infinite' (max out available memory) sized image.