[clug] Zip "bombs"

[Paul Wayper]

On 16/7/19 6:56 pm, Andrew Janke via linux wrote:
> So, I was reading this:
> 
>    https://www.vice.com/en_us/article/597vzx/the-most-clever-zip-bomb-ever-made-explodes-a-46mb-file-to-45-petabytes
> 
> Simple! I thought...  I can do that too.
> 
>   for i in 1000 10000 100000 1000000
>   do
>      dd if=/dev/zero count=$i | zip $i.zip -
>   done
> 
>    Magical-Unicorn:bob$ du -sk *.zip
>    4    1000.zip
>    8    10000.zip
>    52    100000.zip
>    500    1000000.zip
> 
> Hrmpfht! well that isn't going to work. At best I'm getting ~500MB of
> zeros into 500K, I'm a few orders of magnitude off.
> 
> So, bash/perl golf time if anyone cares to educate me. I'll admit I
> haven't read the paper in detail or the links pointed to but it
> appears that there is more to this than meets the eye. Yes, I should
> have known this from the start.

Standard tools aren't going to do it here.  To really get a huge input in a
tiny zip file, you need to understand the zip encoding format.  And there's no
better paper than the Zip Quine:

https://research.swtch.com/zip

Most compression works by having an efficient way of expressing output.  So if
'Ln' means 'the next n characters are literal' and 'Rn' means 'repeat the last
n characters in the output', then something like:

L1 h R1 R2 R4 R8 R16 R32 R64 R128

produces 256 'h' characters from 10 bytes (25.6/1 expansion).  That's assuming
the L and R commands pack into one byte, the command part is one bit and the
'n' part is seven bits, and you can't read from before the start of the input.
 At that point, every 'R128' command you add increases the size of the output
by 128 bytes and the zip file by one byte - so those ten bytes plus 990
subsequent 'R128' commands give you 126848 bytes of output to 1000 bytes of
input.  Obviously, this approaches 128 to 1 expansion asymptotically.

The DEFLATE coding that zip and gzip use is more complicated than that, but
that's the basic idea.  Other encodings, such as LZMA, offer different and
probably better opportunities for zip expansion.

Have fun,

Paul