(I have no idea how active this repository still is, but I wanted to report this issue for posterity.)
This repository contains patches to the Info-ZIP source code to detect zip bombs (ZIP files that need an unreasonably large amount of disk space to extract). Unfortunately the current implementation has worst case quadratic time complexity, which means malicious files can make unzip run unreasonably slowly.
I've writtten a Python script to generates test cases that demonstrate the issue: many-files.py
To reproduce, run e.g.
% ./many-files.py # generates zip files; only needs to be run once
% time unzip -t many-files-1m-padded-reversed.zip >/dev/null # takes forever to finish
Some quick benchmarking:
input file file size files time w/o time with zip bomb detection
---------------------------------- ------------- ----------- ---------- -----------------------------
many-files-64k-padded-reversed.zip 5,613,726 65,534 0.3 s 1.1 s
many-files-1m-padded-reversed.zip 88,777,878 1,000,000 4.7 s 383.7 s ( 6 min 23 s)
many-files-2m-padded-reversed.zip 179,777,878 2,000,000 9.6 s 1876.1 s (31 min 16 s)
many-files-3m-padded-reversed.zip 270,777,878 3,000,000 15.0 s 4501.6 s (75 min 2 s)
This shows unzip time increases quadratically to the point of taking well over an hour to extract a zip file with 3 million entries, which would only take 15 seconds with zip bomb detection disabled.
The circumstances where this happens are not very like to occur naturally. It requires some combination of:
- a very large number of files
- file offsets not increasing monotonously
- spans not being able to be merged, e.g. because there is padding between files
However, it's easy to construct files that meet these conditions maliciously, as I've shown above. And since the purpose of the zip bomb detection logic is to catch maliciously constructed files, it is undesirable that its implementation is vulnerable to a different type of attack which makes the unzip tool run extremely slowly.
I'd also like to mention a concern about memory use: the original unzip tool was carefully designed to use only a fixed memory, regardless of how large the input file is. However, zip bomb detection requires memory proportional to the number of file entries. Then again, because the amount of memory per file is small (around 16 bytes) this is probably not too much of a problem on modern systems.
Again, I have no idea if this repository is still active or anyone cares at all, but for my own amusement I reimplemented the cover data structure to fix this: maksverver@5f5fdc7
The new data structure has worst case O(log^2 n) performance and seems to have negligible overhead in practice. I'd be happy to send a merge request if you want it.
(I have no idea how active this repository still is, but I wanted to report this issue for posterity.)
This repository contains patches to the Info-ZIP source code to detect zip bombs (ZIP files that need an unreasonably large amount of disk space to extract). Unfortunately the current implementation has worst case quadratic time complexity, which means malicious files can make unzip run unreasonably slowly.
I've writtten a Python script to generates test cases that demonstrate the issue: many-files.py
To reproduce, run e.g.
Some quick benchmarking:
This shows unzip time increases quadratically to the point of taking well over an hour to extract a zip file with 3 million entries, which would only take 15 seconds with zip bomb detection disabled.
The circumstances where this happens are not very like to occur naturally. It requires some combination of:
However, it's easy to construct files that meet these conditions maliciously, as I've shown above. And since the purpose of the zip bomb detection logic is to catch maliciously constructed files, it is undesirable that its implementation is vulnerable to a different type of attack which makes the unzip tool run extremely slowly.
I'd also like to mention a concern about memory use: the original unzip tool was carefully designed to use only a fixed memory, regardless of how large the input file is. However, zip bomb detection requires memory proportional to the number of file entries. Then again, because the amount of memory per file is small (around 16 bytes) this is probably not too much of a problem on modern systems.
Again, I have no idea if this repository is still active or anyone cares at all, but for my own amusement I reimplemented the cover data structure to fix this: maksverver@5f5fdc7
The new data structure has worst case O(log^2 n) performance and seems to have negligible overhead in practice. I'd be happy to send a merge request if you want it.