12 ms·

Zip Bomb

342 points by takinola 14y ago

luriel 14y ago
See also Russ Cox's "Zip Files All The Way Down" article: http://research.swtch.com/zip http://research.swtch.com/zip
timdorr 14y ago
While this is out of the range of most consumers, I wonder if any bored sysadmins with a new storage system to test have tried unzipping that file...
- sherjilozair 14y ago
  I've tried it, and I'm no sysadmin. Fortunately, I had a disk quota on, set by my sysadmin, and so the bomb could only take up 2 gb of the space I had in my quota.
- lucian1900 14y ago
  It'd be easier to do something like cat /dev/urandom > big
  - VMG 14y ago
    /dev/zero is probably faster
    - cnvogel 14y ago
      Or $ truncate -s 17TB hugefile.dat ...which is just as pointless.
      - jeltz 14y ago
        I believe truncate creates sparse files in Linux so that would not work.
    - fduran 14y ago
      It is way faster (at least with dd): $ time dd if=/dev/zero of=10MB.dat bs=1M count=10 real 0m0.213s $ time dd if=/dev/urandom of=10MB.dat bs=1M count=10 real 0m8.873s
      - Dylan16807 14y ago
        Or if you want to measure the speed of the source itself: $ dd if=/dev/zero of=/dev/null bs=1M count=100 104857600 bytes (105 MB) copied, 0.0237114 s, 4.4 GB/s $ dd if=/dev/urandom of=/dev/null bs=1M count=100 104857600 bytes (105 MB) copied, 21.501 s, 4.9 MB/s Also dammit Ubuntu with your Gibis.
conductor 14y ago
Web browsers support compressed data, I wonder will they try to decompress something like this?
- TazeTSchnitzel 14y ago
  Gzip could certainly be abused.
- chuppo 14y ago
  Yes they will, there was a post a while back which used this to bomb the browser.
  - conductor 14y ago
    Also one can try to bomb virus scanners (on PC or on a mail server (using e-mail attachment)) or any other service which supports uploading+extracting zip files.
  - asdfs 14y ago
    Do you have a link, by any chance?
    - chuppo 14y ago
      Unfortunately I do not. This is where that project to store all your browsing history "in the cloud" (preferrably your own "cloud" would have been handy. So you never again miss something and go searching for it again, you know youve seen it -> search in your own history which contains the content right then as it was.
  - repsilat 14y ago
    Perhaps more concerning is being able to use this to launch a denial of service attack on a server that accepts zipped data. Gzipped requests are unusual with HTTP (no idea how widespread support for it is), but iirc SPDY is compressed by default.
    - 14y ago
trool 14y ago
Old as fuck.
- EwanToo 14y ago
  Next week on HN, C++ released! :)
  - koffiezet 14y ago
    Was thinking something simular... First time I discovered this I was a teenager still using dial-up. And apparently the virus-scanner on the school-pc's couldn't handle it :)
    - forgivegod 14y ago
      Same here! Except the one I had created a huge amount of folders with weird characters (∆µßßßßçøø∑) in the root of my c drive. Made my dad's computer slow to a crawl. Also took a bitt of scripting to undo it before he came home.
- Achshar 14y ago
  It may be old but i didn't knew about it until it was brought up on a /r/technology thread yesterday. Old =/= everyone knows about it.
  - trool 14y ago
    The fact that you don't do your homework doesn't mean what this guy is doing is righteous.
    - kennywinker 14y ago
      trool is troll. </surprise>
      - trool 14y ago
simoncoggins 14y ago
I've seen something similar with a PNG file for user supplied profile image [1]. The image was a 10000x10000 all black PNG image which compresses to a pretty small file size. Unless you validate the image dimensions as well as the file size it may cause problems, for instance when GD is used to try to resize it exhausted the memory limit. [1] https://bugs.launchpad.net/mahara/+bug/784978 https://bugs.launchpad.net/mahara/+bug/784978
- rorrr 14y ago
  Out of curiosity I just made two images: 15,000 x 15,000: http://i.imgur.com/WzCyE.png http://i.imgur.com/WzCyE.png 50,000 x 50,000: http://i.imgur.com/kgmHu.png http://i.imgur.com/kgmHu.png Both FF and Chrome refuse to open the second one. IE does something weird. Both Opera and Safari figure out the size correctly, but don't display the image.
  - b3tta 14y ago
    With Firefox (15.0.1) I get some really, really strange results with the second image. When I opened it the first time, or everytime I press Ctrl+Shift+R it works, but it shows the URL, and a litte icon in the upper left corner: http://i.imgur.com/B7jFE.png http://i.imgur.com/B7jFE.png If I press F5 or Ctrl+R it doesnt work, just as you said.
  - syassami 14y ago
    Wow, the first one crashed my chrome browser. Thanks for sharing
  - m4rkuskk 14y ago
    In case safari crashes and you won't be able to open it, sudo rm -rf ~/Library/Caches/com.apple.Safari did it for me.
    - mlvljr 14y ago
      seems not working on windows, a bug?
- 14y ago
vog 14y ago
Even more impressive: A zip file that extracts to itself. (That's also shown in the article, as a kind of "Lempel-Ziv quine".)
DanBC 14y ago
Here are some other compression curiosities: (http://www.maximumcompression.com/compression_fun.php http://www.maximumcompression.com/compression_fun.php) It includes a 115 byte rar file that expands to 5 Mb. (That 115 bytes can be squashed down further; one compressor gets it to 39 bytes.); a file that compresses with one software but ends up bigger with another software; etc. some say that file compression is linked to AI - good general purpose compression relies on being able to predict the text and create table; if you can predict something you understand it. The Hutter prize tests this against the 100 Mb of enwiki8. Best attempt so far is a bit less than 16 Mb. (http://prize.hutter1.net/ http://prize.hutter1.net/) I remember zip bombs from early 90s BBSing. I also remember ANSI bombs.
- im3w1l 14y ago
  Very relevant: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomput...
  - DanBC 14y ago
    > By definition, the Kolmogorov complexity K of a string x is defined as the length of the shortest program (self-extracting archive) computing x. K(x) itself cannot be computed, only approximated from above, namely by finding better and better compressions, but even if we reach K(x) will never know whether we have done so. For a text string like enwik8, Shannon's estimate suggests that enwik8 should be compressible down to 12MB. The current record is 15,949,688 bytes.
- wolf550e 14y ago
  Just read this: http://www.mattmahoney.net/dc/dce.html http://www.mattmahoney.net/dc/dce.html
jefffoster 14y ago
I found a similar file to this (a zip file that contains itself) and e-mailed it to a friend at work. He never received it, but I thought nothing of it (I assumed the email filters just destroyed it). A days later the mail server stops working and the sysadmin turns up at my desk. Turns out the anti-virus scanner had been unzipping and scanning repeatedly. It eventually filled up the entire disk and bad things happened.
- deleted 14y ago
  [deleted]
- fromdoon 14y ago
  >> ... eventually filled up the entire disk and bad things happened I can only imagine what would have happened. Can you share more details about that. Also, wonder how the mail servers these days are equipped to handle such attachments. Can someone throw light on that? Is it just plain simple to detect these files?
  - tonyz 14y ago
    A well-known example of a zip quine: http://steike.com/code/useless/zip-file-quine/ http://steike.com/code/useless/zip-file-quine/ Compression quines and bombs are a great way to screw up automated systems. Possessing or transmitting them can easily cause a denial of service. From Wikipedia: A quine is a computer program which takes no input and produces a copy of its own source code as its only output. http://en.wikipedia.org/wiki/Quine_(computing) http://en.wikipedia.org/wiki/Quine_(computing)
  - krenoten 14y ago
    Computational complexity attacks are actually quite rampant in various types of software. A good example is an "evil regex" which is usable on software that accepts regular expressions as input, and similarly costly regexes already contained in software can be exploited by certain crafted input to induce a DOS. http://en.wikipedia.org/wiki/ReDoS http://en.wikipedia.org/wiki/ReDoS
  - omh 14y ago
acd 14y ago
You can also use the same technique to cause a exhaustion on the number of files/inodes. Ie you format a ext4 partition with crazy number of inodes, then create the zip file containing crazy amount of 0-byte files. Then receiving side has a normal formatted ext3,ext4 partition. Exhaustion on number of inodes. This is not nice so don't do it.
- thisaccount 14y ago
  Wonder what would happen if you hid a symlink pointing to root as one of the files. Someone without a doubt would rm-rf.
  - bct 14y ago
    rm -rf doesn't follow symlinks: /tmp $ mkdir -p a/b/c /tmp $ mkdir -p a/d/e /tmp $ cd a/b/c /tmp/a/b/c $ ln -s /tmp/a/d . /tmp/a/b/c $ cd ../../ /tmp/a $ ls */* b/c: d d/e: /tmp/a $ rm -rf b /tmp/a $ ls d It would be pretty stupid for it to.
ctdonath 14y ago
Considering the nature of modern "art" (ex.: "here's a hard drive containing $5M in stolen software!"), and owning a "This T-Shirt is a Munition" (featuring the then-controversial RSA-in-4-lines-PERL code), I'm perversely inclined to find such a "zip bomb" small enough to print the hex or QR code on one business card. The 42kb file is a bit big; any known smaller versions?
- DanBC 14y ago
  (http://www.maximumcompression.com/compression_fun.php http://www.maximumcompression.com/compression_fun.php) This has a 115 byte RAR file that expands to 5 Mb. You can probably experiment to get a file just small enough for QR code, with huge output. (Note that using obscure compressor gives a 24 byte file that expends to 5 Mb.)
swighton 14y ago
I similar attack to mess up XML parsers: http://en.wikipedia.org/wiki/Billion_laughs http://en.wikipedia.org/wiki/Billion_laughs
- vigrant 14y ago
  lol ^ 10,000,000,000
  - DoublePlusWill 14y ago
    lol * 10,000,000,000 lol ^ 10,000,000,000 is an insane amount larger. :)
- tripzilch 14y ago
  Right, you can also do this with SVG images, the <g> group element and something called "xref" (IIRC?) to refer back to other defined groups by their id attribute.
Zenst 14y ago
Detection of compression bimbs has improved alot as apposed to over 10 years ago when they realy did cause problems on mail servers. Home AV software detects them, crazily enough my install of GoLang on a windows box has a file that gets flagged as a compression bomb every full system scan. But examples like this happen in many forms, heck windows on some file types/sizes doing thumbnails has done wonderous things like exponentialy growing the swap file to a ever impending churned slowdown. Even computers have mental farts.
- exch 14y ago
  > crazily enough my install of GoLang on a windows box has a file that gets flagged as a compression bomb every full system scan. This may have something to do with Russ Cox's blog post on recursive zip-archives "Zip Files All The Way Down" in Go: http://research.swtch.com/zip http://research.swtch.com/zip Baseless speculation mode: There is a possibility that the recursive zip file was part of the Go test cases for the gzip package at some point. If it lingers in the mercurial commit history, it may still trigger hits from your AV software.
  - Zenst 14y ago
    I just had to dig out my logs and see what it was - file in question is located in (default install): C:\Go\src\pkg\regexp\testdata\re2-exhaustive.txt.bz2 385KB in size though opening shows a .txt file that is 58MB in size. Basicily Avast being picky and a non-positive. Probably so crompessed that it hit whatever limit on decompressing per file in avast and avast then things its a compression bomb. Opens and extracts fine, though hardly fun reading.
Zelphyr 14y ago
Inception
tokenadult 14y ago
The most authoritative-looking reference http://www.aerasec.de/security/advisories/decompression-bomb-vulnerability.html http://www.aerasec.de/security/advisories/decompression-bomb... in this typically thinly referenced Wikipedia article looks to be several years old. What is the current state of the art? Some of the comments already posted as I post this comment talk about the situation "years ago" and at least one comment suggests that this is largely a solved problem, currently. How many wild vulnerabilities like this are there, really? (I ask questions like this about most "facts" reported in Wikipedia articles, because I am a Wikipedian myself, and I have become painfully aware of how often the "the free encyclopedia that anyone can edit" becomes "the encyclopedia in which every fact is just made up.") From a neutral point of view, is this really much of a problem in day-by-day computer use and online network use?
- diminoten 14y ago
  This seems like a ripe opportunity for an enterprising blogger to examine changes that have been made to how we compress things over the past few years and see if any of these changes impacts the potency of the decompression bomb as a kind of, as you said, 'update to the current state of the art'.
ryanpers 14y ago
Awesome link, but already seen it on reddit yesterday. HUH
jaylevitt 14y ago
Comp sci folks: Is predicting whether a compressed file will produce a finite (or, better, reasonably-sized) output roughly equivalent to the halting problem?
- cheald 14y ago
  No, because run-length encoding encodes the - well - run lengths in the file header. You can read those and know how big the resulting file will be without having to actually decompress the file.
- lmkg 14y ago
  It depends on the decompression algorithm. It's possible for that to be the case, but this can only happen if the compressed binary format is essentially a Turing-complete language, for which your decompresser is the interpreter. I'm not aware of any data formats for which that is the case, but from a theoretical standpoint, eval(s) is a perfectly cromulent decompression algorithm. This fact is essentially the starting point for Kolmogorov complexity. "Reasonably-sized" is actually an interesting problem in itself. If your decompresser is sufficiently advanced, you could embed a busy-beaver function, which terminates but grows faster than any computable function. I have no idea whether such functions could be expressed with less-than-Turing-complete data formats.
  - dsl 14y ago
    RAR has a built in virtual machine for forwards compatibility with new compression algorithms.
mariuolo 14y ago
Welcome to 1988?

342 points by takinola 14y ago

See also Russ Cox's "Zip Files All The Way Down" article: http://research.swtch.com/zip http://research.swtch.com/zip

While this is out of the range of most consumers, I wonder if any bored sysadmins with a new storage system to test have tried unzipping that file...

sherjilozair 14y ago
I've tried it, and I'm no sysadmin. Fortunately, I had a disk quota on, set by my sysadmin, and so the bomb could only take up 2 gb of the space I had in my quota.
lucian1900 14y ago
It'd be easier to do something like cat /dev/urandom > big
- VMG 14y ago
  /dev/zero is probably faster
  - cnvogel 14y ago
    Or $ truncate -s 17TB hugefile.dat ...which is just as pointless.
    - jeltz 14y ago
      I believe truncate creates sparse files in Linux so that would not work.
  - fduran 14y ago
    It is way faster (at least with dd): $ time dd if=/dev/zero of=10MB.dat bs=1M count=10 real 0m0.213s $ time dd if=/dev/urandom of=10MB.dat bs=1M count=10 real 0m8.873s
    - Dylan16807 14y ago
      Or if you want to measure the speed of the source itself: $ dd if=/dev/zero of=/dev/null bs=1M count=100 104857600 bytes (105 MB) copied, 0.0237114 s, 4.4 GB/s $ dd if=/dev/urandom of=/dev/null bs=1M count=100 104857600 bytes (105 MB) copied, 21.501 s, 4.9 MB/s Also dammit Ubuntu with your Gibis.

conductor 14y ago

Web browsers support compressed data, I wonder will they try to decompress something like this?

TazeTSchnitzel 14y ago
Gzip could certainly be abused.
chuppo 14y ago
Yes they will, there was a post a while back which used this to bomb the browser.
- conductor 14y ago
  Also one can try to bomb virus scanners (on PC or on a mail server (using e-mail attachment)) or any other service which supports uploading+extracting zip files.
- asdfs 14y ago
  Do you have a link, by any chance?
  - chuppo 14y ago
    Unfortunately I do not. This is where that project to store all your browsing history "in the cloud" (preferrably your own "cloud" would have been handy. So you never again miss something and go searching for it again, you know youve seen it -> search in your own history which contains the content right then as it was.
- repsilat 14y ago
  Perhaps more concerning is being able to use this to launch a denial of service attack on a server that accepts zipped data. Gzipped requests are unusual with HTTP (no idea how widespread support for it is), but iirc SPDY is compressed by default.
  - 14y ago

trool 14y ago

Old as fuck.

EwanToo 14y ago
Next week on HN, C++ released! :)
- koffiezet 14y ago
  Was thinking something simular... First time I discovered this I was a teenager still using dial-up. And apparently the virus-scanner on the school-pc's couldn't handle it :)
  - forgivegod 14y ago
    Same here! Except the one I had created a huge amount of folders with weird characters (∆µßßßßçøø∑) in the root of my c drive. Made my dad's computer slow to a crawl. Also took a bitt of scripting to undo it before he came home.
Achshar 14y ago
It may be old but i didn't knew about it until it was brought up on a /r/technology thread yesterday. Old =/= everyone knows about it.
- trool 14y ago
  The fact that you don't do your homework doesn't mean what this guy is doing is righteous.
  - kennywinker 14y ago
    trool is troll. </surprise>
    - trool 14y ago

simoncoggins 14y ago

I've seen something similar with a PNG file for user supplied profile image [1]. The image was a 10000x10000 all black PNG image which compresses to a pretty small file size. Unless you validate the image dimensions as well as the file size it may cause problems, for instance when GD is used to try to resize it exhausted the memory limit. [1] https://bugs.launchpad.net/mahara/+bug/784978 https://bugs.launchpad.net/mahara/+bug/784978

rorrr 14y ago
Out of curiosity I just made two images: 15,000 x 15,000: http://i.imgur.com/WzCyE.png http://i.imgur.com/WzCyE.png 50,000 x 50,000: http://i.imgur.com/kgmHu.png http://i.imgur.com/kgmHu.png Both FF and Chrome refuse to open the second one. IE does something weird. Both Opera and Safari figure out the size correctly, but don't display the image.
- b3tta 14y ago
  With Firefox (15.0.1) I get some really, really strange results with the second image. When I opened it the first time, or everytime I press Ctrl+Shift+R it works, but it shows the URL, and a litte icon in the upper left corner: http://i.imgur.com/B7jFE.png http://i.imgur.com/B7jFE.png If I press F5 or Ctrl+R it doesnt work, just as you said.
- syassami 14y ago
  Wow, the first one crashed my chrome browser. Thanks for sharing
- m4rkuskk 14y ago
  In case safari crashes and you won't be able to open it, sudo rm -rf ~/Library/Caches/com.apple.Safari did it for me.
  - mlvljr 14y ago
    seems not working on windows, a bug?
14y ago

vog 14y ago

Even more impressive: A zip file that extracts to itself. (That's also shown in the article, as a kind of "Lempel-Ziv quine".)

DanBC 14y ago

Here are some other compression curiosities: (http://www.maximumcompression.com/compression_fun.php http://www.maximumcompression.com/compression_fun.php) It includes a 115 byte rar file that expands to 5 Mb. (That 115 bytes can be squashed down further; one compressor gets it to 39 bytes.); a file that compresses with one software but ends up bigger with another software; etc. some say that file compression is linked to AI - good general purpose compression relies on being able to predict the text and create table; if you can predict something you understand it. The Hutter prize tests this against the 100 Mb of enwiki8. Best attempt so far is a bit less than 16 Mb. (http://prize.hutter1.net/ http://prize.hutter1.net/) I remember zip bombs from early 90s BBSing. I also remember ANSI bombs.

im3w1l 14y ago
Very relevant: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomput...
- DanBC 14y ago
  > By definition, the Kolmogorov complexity K of a string x is defined as the length of the shortest program (self-extracting archive) computing x. K(x) itself cannot be computed, only approximated from above, namely by finding better and better compressions, but even if we reach K(x) will never know whether we have done so. For a text string like enwik8, Shannon's estimate suggests that enwik8 should be compressible down to 12MB. The current record is 15,949,688 bytes.
wolf550e 14y ago
Just read this: http://www.mattmahoney.net/dc/dce.html http://www.mattmahoney.net/dc/dce.html

jefffoster 14y ago

I found a similar file to this (a zip file that contains itself) and e-mailed it to a friend at work. He never received it, but I thought nothing of it (I assumed the email filters just destroyed it). A days later the mail server stops working and the sysadmin turns up at my desk. Turns out the anti-virus scanner had been unzipping and scanning repeatedly. It eventually filled up the entire disk and bad things happened.

deleted 14y ago
[deleted]
fromdoon 14y ago
>> ... eventually filled up the entire disk and bad things happened I can only imagine what would have happened. Can you share more details about that. Also, wonder how the mail servers these days are equipped to handle such attachments. Can someone throw light on that? Is it just plain simple to detect these files?
- tonyz 14y ago
  A well-known example of a zip quine: http://steike.com/code/useless/zip-file-quine/ http://steike.com/code/useless/zip-file-quine/ Compression quines and bombs are a great way to screw up automated systems. Possessing or transmitting them can easily cause a denial of service. From Wikipedia: A quine is a computer program which takes no input and produces a copy of its own source code as its only output. http://en.wikipedia.org/wiki/Quine_(computing) http://en.wikipedia.org/wiki/Quine_(computing)
- krenoten 14y ago
  Computational complexity attacks are actually quite rampant in various types of software. A good example is an "evil regex" which is usable on software that accepts regular expressions as input, and similarly costly regexes already contained in software can be exploited by certain crafted input to induce a DOS. http://en.wikipedia.org/wiki/ReDoS http://en.wikipedia.org/wiki/ReDoS
- omh 14y ago

acd 14y ago

You can also use the same technique to cause a exhaustion on the number of files/inodes. Ie you format a ext4 partition with crazy number of inodes, then create the zip file containing crazy amount of 0-byte files. Then receiving side has a normal formatted ext3,ext4 partition. Exhaustion on number of inodes. This is not nice so don't do it.

thisaccount 14y ago
Wonder what would happen if you hid a symlink pointing to root as one of the files. Someone without a doubt would rm-rf.
- bct 14y ago
  rm -rf doesn't follow symlinks: /tmp $ mkdir -p a/b/c /tmp $ mkdir -p a/d/e /tmp $ cd a/b/c /tmp/a/b/c $ ln -s /tmp/a/d . /tmp/a/b/c $ cd ../../ /tmp/a $ ls */* b/c: d d/e: /tmp/a $ rm -rf b /tmp/a $ ls d It would be pretty stupid for it to.

ctdonath 14y ago

Considering the nature of modern "art" (ex.: "here's a hard drive containing $5M in stolen software!"), and owning a "This T-Shirt is a Munition" (featuring the then-controversial RSA-in-4-lines-PERL code), I'm perversely inclined to find such a "zip bomb" small enough to print the hex or QR code on one business card. The 42kb file is a bit big; any known smaller versions?

DanBC 14y ago
(http://www.maximumcompression.com/compression_fun.php http://www.maximumcompression.com/compression_fun.php) This has a 115 byte RAR file that expands to 5 Mb. You can probably experiment to get a file just small enough for QR code, with huge output. (Note that using obscure compressor gives a 24 byte file that expends to 5 Mb.)

swighton 14y ago

I similar attack to mess up XML parsers: http://en.wikipedia.org/wiki/Billion_laughs http://en.wikipedia.org/wiki/Billion_laughs

vigrant 14y ago
lol ^ 10,000,000,000
- DoublePlusWill 14y ago
  lol * 10,000,000,000 lol ^ 10,000,000,000 is an insane amount larger. :)
tripzilch 14y ago
Right, you can also do this with SVG images, the <g> group element and something called "xref" (IIRC?) to refer back to other defined groups by their id attribute.

Zenst 14y ago

Detection of compression bimbs has improved alot as apposed to over 10 years ago when they realy did cause problems on mail servers. Home AV software detects them, crazily enough my install of GoLang on a windows box has a file that gets flagged as a compression bomb every full system scan. But examples like this happen in many forms, heck windows on some file types/sizes doing thumbnails has done wonderous things like exponentialy growing the swap file to a ever impending churned slowdown. Even computers have mental farts.

exch 14y ago
> crazily enough my install of GoLang on a windows box has a file that gets flagged as a compression bomb every full system scan. This may have something to do with Russ Cox's blog post on recursive zip-archives "Zip Files All The Way Down" in Go: http://research.swtch.com/zip http://research.swtch.com/zip Baseless speculation mode: There is a possibility that the recursive zip file was part of the Go test cases for the gzip package at some point. If it lingers in the mercurial commit history, it may still trigger hits from your AV software.
- Zenst 14y ago
  I just had to dig out my logs and see what it was - file in question is located in (default install): C:\Go\src\pkg\regexp\testdata\re2-exhaustive.txt.bz2 385KB in size though opening shows a .txt file that is 58MB in size. Basicily Avast being picky and a non-positive. Probably so crompessed that it hit whatever limit on decompressing per file in avast and avast then things its a compression bomb. Opens and extracts fine, though hardly fun reading.

Zelphyr 14y ago

Inception

tokenadult 14y ago

The most authoritative-looking reference http://www.aerasec.de/security/advisories/decompression-bomb-vulnerability.html http://www.aerasec.de/security/advisories/decompression-bomb... in this typically thinly referenced Wikipedia article looks to be several years old. What is the current state of the art? Some of the comments already posted as I post this comment talk about the situation "years ago" and at least one comment suggests that this is largely a solved problem, currently. How many wild vulnerabilities like this are there, really? (I ask questions like this about most "facts" reported in Wikipedia articles, because I am a Wikipedian myself, and I have become painfully aware of how often the "the free encyclopedia that anyone can edit" becomes "the encyclopedia in which every fact is just made up.") From a neutral point of view, is this really much of a problem in day-by-day computer use and online network use?

diminoten 14y ago
This seems like a ripe opportunity for an enterprising blogger to examine changes that have been made to how we compress things over the past few years and see if any of these changes impacts the potency of the decompression bomb as a kind of, as you said, 'update to the current state of the art'.

ryanpers 14y ago

Awesome link, but already seen it on reddit yesterday. HUH

jaylevitt 14y ago

Comp sci folks: Is predicting whether a compressed file will produce a finite (or, better, reasonably-sized) output roughly equivalent to the halting problem?

cheald 14y ago
No, because run-length encoding encodes the - well - run lengths in the file header. You can read those and know how big the resulting file will be without having to actually decompress the file.
lmkg 14y ago
It depends on the decompression algorithm. It's possible for that to be the case, but this can only happen if the compressed binary format is essentially a Turing-complete language, for which your decompresser is the interpreter. I'm not aware of any data formats for which that is the case, but from a theoretical standpoint, eval(s) is a perfectly cromulent decompression algorithm. This fact is essentially the starting point for Kolmogorov complexity. "Reasonably-sized" is actually an interesting problem in itself. If your decompresser is sufficiently advanced, you could embed a busy-beaver function, which terminates but grows faster than any computable function. I have no idea whether such functions could be expressed with less-than-Turing-complete data formats.
- dsl 14y ago
  RAR has a built in virtual machine for forwards compatibility with new compression algorithms.

mariuolo 14y ago

Welcome to 1988?