A better zip bomb

分享一个有趣的工具
ZBLG:非递归拉链?炸弹,比例为28000000:1

数据无价,谨慎使用,请勿用于非法用途。

声明:
本文译自:https://www.bamsoftware.com/hacks/zipbomb/
作者:David Fifield
Email:david@bamsoftware.com

一切版权原作者所有。

2019-07-02 updated 2019-07-03, 2019-07-05, 2019-07-06

summary

本文介绍如何构建一个非递归拉链炸弹,(Zip_bomb,这里勉强译为拉链炸弹吧🙂)。

“非递归”意味着它不依赖于解压缩程序在zip文件中嵌套的递归解压缩zip文件:它在单轮解压缩后完全展开。输出大小在输入大小的基础上呈二次方增加,在zip格式的限制下,达到压缩比2800万 (10 MB → 281 TB)。使用64位扩展甚至可以实现更大的扩展。该构造仅使用最常见的压缩算法DEFLATE,并且与大多数zip解析器兼容。

img

zbsm.zip 42 kB 5.5 GB
zblg.zip 10 MB 281 TB
zbxl.zip 46 MB 4.5 PB (Zip64, less compatible)

源代码:

1
git clone https://www.bamsoftware.com/git/zipbomb.git

或者:

1
wget https://www.bamsoftware.com/hacks/zipbomb/zipbomb-20190702.zip

数据和数据来源

1
git clone https://www.bamsoftware.com/git/zipbomb-paper.git

non-recursive zip bomb

non-recursive recursive
zipped size unzipped size ratio unzipped size ratio
Cox quine 440 440 1.0
Ellingsen quine 28 809 42 569 1.5
42.zip *42 374 558 432 13.2 4 507 981 343 026 016 106 billion
this technique 42 374 5 461 307 620 129 thousand 5 461 307 620 129 thousand
this technique 9 893 525 281 395 456 244 934 28 million 281 395 456 244 934 28 million
this technique (Zip64) 45 876 952 4 507 981 427 706 459 98 million 4 507 981 427 706 459 98 million
  • 关于42.zip

  • 有两个版本的42.zip,一个较老版本的42 374字节,以及更新版本的42 838字节。不同之处在于新版本在解压缩之前需要密码,新版本结业密码为:42。我们仅与旧版本进行比较。如果需要,提供以下副本: 42.zip

    1
    2
    3
    4
    5
    16 x 4294967295       = 68.719.476.720 (68GB)
    16 x 68719476720 = 1.099.511.627.520 (1TB)
    16 x 1099511627520 = 17.592.186.040.320 (17TB)
    16 x 17592186040320 = 281.474.976.645.120 (281TB)
    16 x 281474976645120 = 4.503.599.626.321.920 (4,5PB)

使用zip格式的压缩炸弹必须应对这样一个事实,即zip解析器最常支持的压缩算法DEFLATE 无法达到大于1032的压缩比。因此,zip炸弹通常依赖于递归解压缩,在其中嵌套zip文件zip文件以获得每层的额外因子1032。但是这个技巧只适用于递归解压缩的实现,而大多数都没有。

最着名的zip炸弹, 42.zip,扩展到了一个强大的4.5 PB 如果它的所有六个层都是递归解压缩的,那就是微不足道的 0.6 MB在顶层。

Zip Quines,就像EllingsenCox一样,它们包含自己的副本,因此如果递归解压缩无限扩展,同样可以非常安全地解压缩一次。

本文展示了如何构造一个压缩比超过DEFAATE限制1032的非递归拉链炸弹。它通过重叠zip容器内的文件来工作,以便在多个文件中引用高度压缩数据的“内核”,而不制作它的多个副本。zip炸弹的输出尺寸在输入尺寸上呈二次方增长; 即,随着炸弹变大,压缩比变得更好。构造取决于zip和DEFLATE的特征 - 它不能直接移植到其他文件格式或压缩算法。它与大多数zip解析器兼容,例外的是“流”解析器,它在一次传递中解析而无需先查询zip文件的中心目录。我们试图平衡两个相互冲突的目标:

  • 最大化压缩比。我们将压缩率定义为zip文件中包含的所有文件大小的总和除以zip文件本身的大小。它不计算文件名或其他文件系统元数据,只计算内容。
  • 兼容。Zip是一种棘手的格式,解析器不同,特别是在边缘情况和可选功能周围。避免利用仅适用于某些解析器的技巧。我们将评论某些方法来提高zip炸弹的效率,这会降低兼容性。

zip文件的结构

zip文件由引用 文件中央目录组成。

正常格式

img

中央目录位于zip文件的末尾。它是中央目录标头的列表。每个中央目录头包含单个文件的元数据,如文件名和CRC-32校验和,以及指向本地文件头的向后指针。中央目录标题长度为46个字节,加上文件名的长度。

文件由本地文件头和 后面的压缩文件数据组成。本地文件头长30个字节,加上文件名的长度。它包含来自中央目录标头的元数据的冗余副本,以及随后的文件数据的压缩和未压缩大小。Zip是容器格式,而不是压缩算法。每个文件的数据都使用元数据中指定的算法进行压缩 - 通常是DEFLATE

zip格式中的许多冗余和含糊不清允许各种恶作剧。拉链炸弹只是刮擦表面。进一步阅读的链接:

这种zip格式的描述省略了许多理解拉链炸弹所不需要的细节。有关完整信息,请参阅 APPNOTE.TXT的4.3节 或Florian Buchholz 的PKZip文件结构,或参阅源代码

第一个见解:重叠文件

通过压缩一长串重复字节,我们可以生成 高度压缩数据的内核。就其本身而言,内核的压缩率不能超过1032的DEFLATE限制,因此我们想要一种在许多文件中重用内核的方法,而无需在每个文件中单独复制它。我们可以通过重叠文件来实现:使许多中央目录标头指向单个文件,其数据是内核。

img

让我们看一个例子,看看这种结构如何影响压缩比。假设内核是1000字节 并解压缩到 1 MB。然后第一个MB 输出“成本” 1078个字节 输入:

  • 31个字节 用于本地文件头(包括1字节文件名)
  • 47个字节 用于中央目录头(包括1字节文件名)
  • 1000字节 对于内核本身

但每一个 1 MB 仅在第一次成本之后的产出 47个字节 - 我们不需要另一个本地文件头或内核的另一个副本,只需要一个额外的中央目录头。因此,虽然内核的第一个引用具有1 000 000 /1078≈928的压缩比,但每个附加引用将该比率拉近接近1 000 000 /47≈21277,更大的内核提高了上限。

这个想法的问题是缺乏兼容性。由于许多中央目录标头指向单个本地文件头,因此元数据(特别是文件名)无法与每个文件匹配。一些解析器对此犹豫不决Info-ZIP UnZip (标准的Unix unzip程序)提取文件,但有警告:

1
2
3
4
5
unzip overlap.zip
inflating: A
B: mismatching "local" filename (A),continuing with "central" filename version
inflating: B
...

并且Python zipfile模块 抛出异常

1
2
3
4
$ python3 -m zipfile -e overlap.zip .
Traceback (most recent call last):
...
__main__.BadZipFile: File name in directory 'B' and header b'A' differ.

接下来,我们将看到如何修改文件名一致性的构造,同时仍保留重叠文件的大部分优点。

第二个见解:引用本地文件头

我们需要为每个文件分离本地文件头,同时仍然重用单个内核。简单地连接所有本地文件头都不起作用,因为zip解析器将找到一个本地文件头,它希望找到DEFLATE流的开头。但这个想法会有所改变。我们将使用DEFLATE(非压缩块)的一个功能来“引用”本地文件头,使它们看起来像是在内核中终止的同一个DEFLATE流的一部分。每个本地文件头(第一个除外)将以两种方式解释:作为代码(zip文件结构的一部分)和数据(文件内容的一部分)。

img

DEFLATE流是一系列 ,其中每个块可以是压缩的或非压缩的。压缩块是我们通常想到的; 例如,内核是一个大的压缩块。但也有非压缩块,它以一个5字节的头开始, 长度字段意味着“ 逐字输出下一个n字节”。解压缩非压缩块意味着仅剥离5字节头。压缩和非压缩块可以在DEFLATE流中自由混合。输出是按顺序解压缩所有块的结果的串联。

“非压缩”概念仅在DEFLATE层具有意义; 文件数据仍然在zip层计为“压缩”,无论使用哪种块.

最简单的方法是从内到外理解这种引用重叠结构,从最后一个文件开始,然后向后工作。首先插入内核,它将形成每个文件的文件数据结尾。

预先 添加本地文件头LFH N并添加指向它的中央目录头CDH N. 将LFH N和CDH N中的“压缩大小”元数据字段设置为内核的压缩大小。现在预先添加一个5字节的非压缩块头(图中用绿色显示),其长度字段等于LFH N的大小。前置第二个本地文件头LFH N -1 并添加一个中央目录头CDH N -1这指向它。将两个新标头中的“压缩大小”元数据字段设置为内核的压缩大小 加上非压缩块标头的大小(5个字节) 加上 LFH N的大小。

此时,zip文件包含两个名为“Y”和“Z”的文件。让我们来看看解析它时zip解析器会看到什么。假设内核的压缩大小为1000字节,LFH N的大小为31字节。我们从CDH N -1开始, 然后按照指向LFH N -1的指针。第一个文件的文件名是“Y”,其文件数据的压缩大小是1036个字节。将下一个1036字节解释为DEFLATE流,我们首先遇到非压缩块的5字节头,该块表示要复制接下来的31个字节。我们写下接下来的31个字节,即LFH N.,我们解压缩并附加到文件“Y”。继续在DEFLATE流中,我们找到一个压缩块(内核),我们将其解压缩到文件“Y”。现在我们已经到达压缩数据的末尾并且使用文件“Y”完成。继续执行下一个文件,我们按照从CDH N 到LFH N的指针,找到一个名为“Z”的文件,其压缩大小为1000字节。将这1000个字节解释为DEFLATE流,我们立即遇到压缩块(内核再次)并将其解压缩到文件“Z”。

现在我们已经到了最终文件的末尾并完成了。输出文件“Z”包含解压缩的内核; 输出文件“Y”是相同的,但另外以LFH N的31个字节为前缀。

我们通过重复引用过程完成构造,直到zip文件包含所需数量的文件。每个新文件都添加一个中心目录头,一个本地文件头和一个非压缩块来引用紧接着的本地文件头。压缩文件数据通常是一系列DEFLATE非压缩块(引用的本地文件头),后跟压缩内核。内核中的每个字节对输出大小贡献大约1032  N,因为每个字节都是N的一部分文件。输出文件的大小不同:zip文件中较早出现的文件大于稍后出现的文件,因为它们包含更多带引号的本地文件头。输出文件的内容不是特别有意义,但没有人说它们必须有意义。

这种引用重叠结构具有比前一部分的完全重叠结构更好的兼容性,但兼容性是以压缩比为代价的。在那里,每个添加的文件只花费一个中央目录标题; 这里,它需要一个中心目录头,一个本地文件头,以及引用头的另外5个字节。

优化

现在我们已经有了基本的拉链炸弹结构,我们将努力使其尽可能高效。我们想回答两个问题:

  • 对于给定的zip文件大小,最大压缩比是多少?
  • 考虑到zip格式的限制,最大压缩比是多少?

内核压缩

尽可能密集地压缩内核是值得的,因为每个解压缩的字节都被放大N倍。为此,我们使用一个名为bulk_deflate的自定义DEFLATE压缩器,专门用于压缩重复字节串。

当给定无限重复字节流时,所有体面的DEFLATE压缩器将接近1032的压缩比,但我们更关心特定的有限大小而不是渐近。bulk_deflate将更多数据压缩到与通用压缩器相同的空间:比zlib和Info-ZIP大约多26kB,比Zopfli大约多15kBZopfli是一种用于密度交换速度的压缩器。

img

bulk_deflate高压缩比的价格缺乏一般性。bulk_deflate只能压缩单个重复字节的字符串,并且只有那些特定长度,即517 + 258的  ķ为整数ķ ≥0此外密集压缩,bulk_deflate是快速的,这样做基本恒定的工作而不管输入的大小,一边从实际写出压缩字符串的工作。

文件名

出于我们的目的,文件名大多是自重。虽然文件名由于是引用的本地文件头的一部分而确实对输出大小做出了贡献,但文件名中的一个字节的贡献几乎与内核中的一个字节无关。我们希望文件名尽可能短,同时保持文件名不同,并且需要考虑兼容性。

在文件名上花费的每个字节都是在内核上花费的2个字节。(2因为每个文件名在中央目录头和本地文件头中出现两次。)文件名字节平均只产生(N + 1)/ 4字节的输出,而内核中的一个字节计为1032  ñ。

示例: 1 2 3

第一个兼容性考虑因素是字符编码。zip格式规范规定文件名将被解释为CP 437,或者如果设置了某个标志位则为UTF-8APPNOTE.TXT附录D)。但这是跨zip解析器不兼容的一个主要问题,它可能会将文件名解释为某些固定或特定于语言环境的编码。因此,为了兼容性,我们必须将自己限制在CP 437和UTF-8中具有相同编码的字符; 即US-ASCII的95个可打印字符。

我们受文件系统命名限制的进一步限制。某些文件系统不区分大小写,因此“a”和“A”不计为不同的名称。像FAT32这样的常见文件系统 禁止某些字符, 如’*’和’?’。

作为安全但不一定是最佳折衷方案,我们的拉链炸弹将使用由36个字符的字母表组成的字符组成的文件名,不依赖于大小写区别或使用特殊字符:

0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

文件名以明显的方式生成,通过可能的字符循环每个位置并在溢出时添加位置:

“0”,“1”,“2”,……,“Z”,
“00”,“01”,“02”,……,“0Z”,
……,
“Z0”,“Z1”,“Z2”, …,“ZZ”,
“000”,“001”,“002”,……

有36个长度为1的文件名,36 个长度为2的文件名,依此类推。四个字节足以表示 1 727 604 不同的文件名。

鉴于zip文件中的N个文件名通常不是全长相同,我们应该按哪种方式排序,最短到最长或最长到最短?一点点反思表明最好把最长的名字放在最后,因为这些名字引用最多。订购文件名最长最后添加900 MB输出到zblg.zip,与组织它们最长的相比。不过,这是一个次要的优化900 MB 只包括 0.0003%总输出大小。

内核大小

引用重叠结构允许我们放置压缩的数据内核,然后便宜地复制它多次。对于给定的zip文件大小 X,我们应该投入多少空间来存储内核,以及制作副本的数量是多少?

为了找到最佳平衡,我们只需要优化单个变量N,即zip文件中的文件数。N的每个值都需要一定量的开销用于中央目录头,本地文件头,引用块头和文件名。所有剩余空间都可以由内核占用。因为N必须是整数,并且在内核大小降至零之前只能容纳这么多文件,所以只需测试N的每个可能值 并选择产生最多输出的值。

将优化程序应用于X = 42 374,大小为42.zip,在N = 250 处找到最大值。这250个文件需要21 195 离开的字节数 21 179内核的字节数。该大小的内核解压缩到21 841 249 字节数(比率为 1031.3)。解压缩内核的250个副本加上来自引用的本地文件头的一点点额外内容,产生的总解压缩输出为5 461 307 620字节,压缩率为129万。

img zbsm.zip 42 kB → 5.5 GB

1
zipbomb --mode = quoted_overlap --num-files = 250 --compressed-size = 21179> zbsm.zip

优化在分配给内核的空间和分配给文件头的空间之间产生了几乎均匀的分割。这不是巧合。让我们看一下引用重叠结构的简化模型。在简化模型中,我们忽略了文件名,以及由于引用本地文件头而导致输出文件大小略有增加。对简化模型的分析将表明,内核和文件头之间的最佳分割大致是均匀的,并且当分配最佳时,输出大小以二次方式增长。

定义一些常量和变量:

X zip文件大小(固定)
ñ zip文件中的文件数(要优化的变量)
CDH = 46 中央目录头的大小(没有文件名)
LFH = 30 本地文件头的大小(没有文件名)
Q = 5 DEFLATE非压缩块头的大小
C ≈1032 内核的压缩比

H(N)为N个文件所需的头部开销量。请参考 图表) 以了解此公式的来源。
$$
H(N) = N ·(CDH + LFH)+(N -1)·Q
$$
内核剩余的空间是 X - H(N)。总解压缩大小 S X(N)是内核的N个副本的大小,以比率C解压缩。(在此简化模型中,我们忽略了来自引用的本地文件头的次要附加扩展。)
$$
S X(N) =(X - H(N))C  N.
=(X - (N ·(CDH + LFH)+(N -1)·Q))C  N.
= - (CDH + LFH + Q)C  N 2 +(X + Q)C  N.
$$
小号X(Ñ)是一个多项式Ñ,因此它的最大必须一个地方衍生物 小号 ‘ X(Ñ)是零。取导数并找到零给我们 N OPT,最佳文件数。
$$
小号 ‘ X(Ñ OPT) = -2(CDH + LFH + Q)C  N OPT +(X + Q)C
0 = -2(CDH + LFH + Q)C  N OPT +(X + Q)C
N OPT =(X + Q)/(CDH + LFH + Q)/ 2
$$
H(N OPT)为文件头分配了最佳的空间量。它独立于CDH,LFH和C,接近X / 2。
$$
H(N OPT) = N OPT ·(CDH + LFH)+(N OPT - 1)·Q
=(X - Q)/ 2
$$
S X(N OPT)是分配最佳时的总解压缩大小。由此我们看到输出大小在输入大小上呈二次方增长。
$$
S X(N OPT) =(X + Q)^2  C /(CDH + LFH + Q)/ 4
$$

它有点复杂,因为精确的限制取决于实现。Python zipfile 忽略 文件数。Go archive / zip 允许 更大的文件计数,只要它们在低16位中相等即可。但是为了广泛的兼容性,我们必须坚持所述的限制。

随着我们将zip文件扩大,最终我们遇到了zip格式的限制。zip文件最多可包含2 个 16-1个文件,每个文件的未压缩大小最多为2^32 - 1个字节。更糟糕的是, 一些实现 采用最大可能值作为64位扩展的存在的指示符,因此我们的限制实际上是2^16 - 2和2^32 - 2. 碰巧我们遇到的第一个限制是关于未压缩的文件大小。在zip文件大小为8 319 377字节时,天真优化将使我们的文件数为47 837,最大文件为2^32 + 311字节。

接受我们不能无限制地增加N和内核的大小,我们希望找到可达到的最大压缩比,同时保持在zip格式的限制内。继续进行的方法是使内核尽可能大,并拥有最大数量的文件。即使我们不能再维持内核和文件头之间的大致均匀分割,每个添加的文件确实会增加压缩比 - 只是没有像我们能够继续增长内核那样快。实际上,当我们添加文件时,我们需要减小内核的大小,以便为每个添加的文件获得稍大的文件大小腾出空间。

该计划产生一个zip文件,其中包含2^16 - 2个文件和一个解压缩到2^32 - 2 178 825字节的内核。文件在zip文件的开头变长 - 第一个和最大的文件解压缩到2^32 - 56个字节。这与我们可以使用bulk_deflate-encoding的粗略输出大小一样接近,最后54个字节的成本将超过它们的价值。(zip文件整体压缩率是2800万,最后54个字节最多可以获得54⋅1032⋅(2^16 - 2)…“3650万字节,所以只有54个字节可以用1个字节编码才有用 - 我不能用不到2个字节进行编码。)所以除非你能将54个字节编码成1个字节,否则只会降低压缩率。)输出大小这个拉链炸弹,281 395 456 244 934字节,是理论最大值(2^32 - 1)⋅(2^16 - 1)的99.97%。 压缩比的任何重大改进只能来自减小输入大小,而不是增加输出大小。

img zblg.zip 10 MB → 281 TB

10 MB → 281 TB

1
zipbomb --mode = quoted_overlap --num-files = 65534 --max-uncompressed-size = 4292788525> zblg.zip

高效的CRC-32计算

中央目录头和本地文件头中的元数据是 未压缩文件数据的 CRC-32校验和。这带来了一个问题,因为直接计算每个文件的CRC-32需要与总解压缩大小成比例地工作,这在设计上是很大的。(毕竟这是一个拉链炸弹。)我们宁愿做最坏情况下与拉链成比例的工作尺寸。有两个因素对我们有利:所有文件共享一个共同的后缀(内核),而未压缩的内核是一串重复的字节。我们将CRC-32表示为矩阵产品 - 这将使我们不仅可以快速计算内核的校验和,还可以跨文件重用计算。本节中描述的技术是crc32_combine zlib中函数的轻微扩展,Mark Adler 在此解释 。

您可以将CRC-32建模为状态机,为每个输入位更新32位状态寄存器。0位和1位的基本更新操作是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint32 crc32_update_0(uint32 state) {
// Shift out the least significant bit.
bit b = state & 1;
state = state >> 1;
// If the shifted-out bit was 1, XOR with the CRC-32 constant.
if (b == 1)
state = state ^ 0xedb88320;
return state;
}

uint32 crc32_update_1(uint32 state) {
// Do as for a 0 bit, then XOR with the CRC-32 constant.
return crc32_update_0(state) ^ 0xedb88320;
}

如果你认为状态寄存器是一个32元素的二进制向量,并使用XOR进行加法和AND进行乘法运算,那么 crc32_update_0就是 线性变换 ; 即,它可以表示为乘以32×32二进制 变换矩阵。要了解原因,请注意将矩阵乘以向量只是将每列乘以向量的相应元素后对矩阵的列求和。移位操作state >> 1 只是取状态向量的每个位 i并将其乘以除了位i -1(从右到左对位进行编号)之外的任何位置的向量。有条件的最终XOR state ^ 0xedb88320 只在位时发生 b是1可以代表第一次乘以 b0xedb88320然后将其异或进入状态。

此外,crc32_update_1只是 crc32_update_0加(XOR)常数。这使得crc32_update_1一个 仿射变换:矩阵乘法再平移(即,矢量相加)。如果我们将变换矩阵的尺寸放大到33×33并且将额外的元素附加到始终为1的状态向量,我们可以在单个步骤中表示矩阵乘法和平移。(此表示称为 齐次坐标。)

矩阵M 0如下

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

矩阵M1如下

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

33×33变换矩阵M 0和M 1分别计算由0位和1位影响的CRC-32状态变化。列向量存储在底部的最高有效位:从下到上读取第一列,您会看到CRC-32多项式常量edb88320 16 = 1 1 1 0 1 1 0 11 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 00 2。两个矩阵仅在最终列中不同,最终列表示齐次坐标中的平移向量。在M 0中,平移为零,并且在M 1中,它是edb88320 16,CRC-32多项式常数。正好在对角线上方的1表示换档操作state >> 1

这两种操作crc32_update_0crc32_update_1 可以由33×33的变换矩阵来表示。示出了矩阵M 0和M 1。矩阵表示的好处是矩阵组成。假设我们想要表示通过处理ASCII字符’a’而产生的状态变化,其二进制表示为01100001 2。我们可以在单个变换矩阵中表示这8位的累积CRC-32状态变化:
$$
M a = M 0 M 1 M 1 M 0 M 0 M 0 M 0 M 1
$$
并且我们可以通过将M a的多个副本乘以一起矩阵求幂来表示一串重复’a’的状态变化。我们可以使用square-and-multiply算法快速进行矩阵求幂,这允许我们 仅在大约log 2 n步骤中计算M n。例如,表示9’a的字符串的状态变化的矩阵是  
$$
(Ma)9 = M M M M M M M M Ma a a a a a a a a

=(M M M M)2 M.a a a a a

=((M M)2)2 M.a a a

=(((Ma)2)2)2 M.a
$$
square-and-multiply算法对于计算M kernel是非压缩内核的矩阵很有用,因为内核是一串重复的字节。要从矩阵生成CRC-32校验和值,请将矩阵乘以零向量。(齐次坐标中的零向量,即:32 0后跟1。这里我们省略校正和预处理和后处理的次要复杂性。)为了计算每个文件的校验和,我们向后工作。首先初始化M := M 内核。内核的校验和也是最终文件的校验和,文件 N,因此将M乘以零向量并将得到的校验和存储在CDH N和LFH中ñ。的文件的文件数据 ñ - 1相同的文件的文件数据 Ñ,但随着LFH添加的前缀 Ñ。这样计算中号LFH Ñ,用于LFH状态改变矩阵 Ñ,和更新中号 := 中号 中号LFH Ñ。现在 M表示处理LFH N后跟内核的累积状态变化。 通过再次将 M乘以零向量来计算文件 N -1的校验和。继续该过程,将状态变化矩阵累积到 M中,直到所有文件都已处理完毕。

扩展名:Zip64

早些时候,由于zip格式的限制,我们在扩展方面遇到了障碍 - 无论zip文件多么巧妙地打包,都不可能产生超过281 TB的输出。使用Zip64#ZIP64)可以超越这些限制,Zip64#ZIP64)是zip格式的扩展,可将某些标题字段的大小增加到64位。对Zip64的支持绝不是通用的,但它是更常用的扩展之一。至于压缩率,Zip64的作用是将中央目录头的大小从46字节增加到58字节,并将本地目录头的大小从30字节增加到50字节。参考 公式 为了在简化模型中实现最佳扩展,我们看到Zip64格式的拉链炸弹仍然以二次方式增长,但由于分母较大而变得更慢 - 这 在Zip64线的垂直位置略低的下图中)可见 。为了弥补兼容性的损失和增长缓慢,我们删除了所有实际的文件大小限制。

假设我们想要一个扩展到的拉链炸弹 4.5 PB,与.zip递归扩展的大小相同。zip文件有多大?使用二进制搜索,我们发现解压缩大小超过解压缩大小42.zip的最小zip文件的压缩大小为 46 MB。

img zbxl.zip 46 MB → 4.5 PB (Zip64,兼容性较差)

1
zipbomb --mode = quoted_overlap --num-files = 190023 --compressed-size = 22982788 --zip64> zbxl.zip

4.5 PB大致是Event Horizon Telescope捕获的数据大小,用于制作黑洞,堆栈和硬盘堆栈的 第一张图像

使用Zip64,考虑最大压缩率不再是实际有趣的,因为我们可以继续增加zip文件大小和压缩率,直到压缩的zip文件都非常大。然而,一个有趣的门槛是2 64 个字节 (18 EB 要么 16 EiB) - 大多数文件系统都不适合这么多数据。二进制搜索找到产生至少那么多输出的最小拉链炸弹:它包含1200万 文件并具有压缩内核 1.5 GB。zip文件的总大小是 2.9 GB 它解压缩到 2 64 + 11 727 895 877字节,压缩比超过 62亿。我没有让这个可下载,但你可以使用源代码自己生成它。它包含的文件非常大,可以发现 Info-ZIP UnZip 6.0中的错误

1
zipbomb --mode = quoted_overlap --num-files = 12056313 --compressed-size = 1482284040 --zip64> zbxxl.zip

扩展名:bzip2

​ bzip2以一个行程编码步骤开始,该步骤将重复字节串的长度减少51倍。然后将数据分成 900 kB块和每个块单独压缩。根据经验,运行长度编码后的一个块可以压缩到32个字节。900 000×51/32 = 1 434 375。

DEFLATE是zip格式中最常用的压缩算法,但它只是众多选项中的一种。可能第二种最常见的算法是bzip2,虽然不像DEFLATE那样兼容,但它可能是第二种最常用的压缩算法。根据经验,bzip2的最大压缩比约为1.4百万,这允许更密集的内核包装。忽略兼容性的损失,bzip2能否实现更高效的拉链炸弹?

是 - 但仅适用于小文件。问题是bzip2没有像我们用来引用本地文件头非压缩的DEFLATE 那样。因此不可能重叠文件并重用内核 - 每个文件必须有自己的副本,因此整体压缩率并不比任何单个文件的比率好。在图中我们看到,无重叠bzip2仅对大约一兆字节以下的文件优于引用的DEFLATE。

仍然有希望使用bzip2 - 下一节中讨论的本地文件头引用的替代方法。此外,如果您碰巧知道某个zip解析器支持bzip2 容忍不匹配的文件名,那么您可以使用完全重叠构造,而不需要引用。

img

拉链尺寸与拉链尺寸适用于各种拉链炸弹结构。请注意日志日志比例。每个结构都显示有和没有Zip64。无重叠构造具有线性生长速率,其在线的1:1斜率中可见。bzip2线的垂直偏移表明bzip2的压缩比大约是DEFLATE的压缩比的千倍。引用的DEFLATE结构具有二次增长率,如线的2:1斜率所证明的。Zip64变体的效率略低,但允许输出超过281 TB。在达到最大文件大小时,字段引用的bzip2从二次到线性转换的行(2^32 - 2个字节),或外场引用允许的最大文件数。

扩展:额外字段引用

到目前为止,我们使用DEFLATE的一个功能来引用本地文件头,我们刚刚看到同样的技巧不适用于bzip2。有一种替代的引用方式,稍微有点限制,只使用zip格式的功能,而不依赖于压缩算法。

在本地文件头结构的末尾有一个可变长度的 额外字段,其目的是存储不适合标题的普通字段的信息(APPNOTE.TXT第4.3.7节))。额外信息可以包括例如高分辨率时间戳或Unix uid / gid; Zip64信息存储在额外字段中。额外字段表示为长度值结构; 如果我们在不添加值的情况下增加长度字段,那么额外的字段将增长到包含在zip文件中的任何内容 - 即下一个本地文件头。使用此技术,每个本地文件头可以通过将它们包含在其自己的额外字段中来“引用”以下本地文件头。与DEFLATE非压缩块引用相比,额外字段引用的好处有三个:

  1. 额外字段引用只需要4个字节的开销,而不是5个字节,从而为内核留出更多空间。
  2. 额外字段引用不会增加文件的大小,这会在zip格式的限制下运行时为更大的内核留下更多的空间。
  3. 额外字段引用提供了一种将引用与bzip2结合的方法。

尽管有这些好处,但外场报价不如DEFLATE报价灵活。它不像DEFLATE引用那样链:每个本地文件头不仅必须包含紧接的下一个头,而且还必须包含所有后面的头。随着接近zip文件的开头,额外字段的长度会增加。因为额外字段的最大长度为 2^16 - 1个字节,假设文件名按照描述分配,则最多只能引用1808个本地文件头(或带有Zip64的1170)。(在DEFLATE的情况下,您可以对第一个(最短的)本地文件头使用额外字段引用,然后切换到剩余的DEFLATE引用。)另一个问题是,为了符合内部数据结构在额外字段中,必须选择16位类型标记(APPNOTE.TXT第4.5.2节)。在引用的数据之前。我们想要选择一个类型标记,它将导致解析器忽略引用的数据,而不是试图将其解释为有意义的元数据。Zip解析器应该忽略未知类型标记,因此我们可以随机选择类型标记,但是存在将来可能分配标记的风险,从而破坏了构造的兼容性。

img

上图说明了使用带有和不带Zip64的bzip2的额外字段引用的可能性。两条线都有一个膝盖,在该拐点处,生长从二次转变为线性。在非Zip64情况下,膝盖出现在最大未压缩文件大小的位置(2……32 - 2个字节) 到达了; 在此之后,人们只能增加文件数量,而不能增加文件的大小。当文件数达到1809时,当我们在额外字段中用尽房间引用额外标题时,该行完全结束。在Zip64的情况下,膝盖发生在1171个文件,之后文件的大小可以增加,但不是它们的数量。外场引用也有助于DEFLATE,但差别很小,以至于在视觉上难以察觉,因此从图中省略了。它将 zbsm.zip 的压缩比提高了 1.2%; zblg.zip 0.019%;和zbxl.zip 0.0025%。

讨论

在相关工作中, Plötz等人。 使用重叠文件创建近自我复制的zip文件。Gynvael Coldwind 之前曾建议(幻灯片47)重叠文件。

为了兼容性,我们设计了引用重叠拉链炸弹结构,考虑了许多实现差异,其中一些显示在下表中。由此产生的结构与通常从后到前工作的zip解析器兼容,首先咨询中心目录并将其用作文件索引。其中包括Nail中包含的示例zip解析器,这是从正式语法自动生成的。但是,这种结构与“流”解析器不兼容,这些解析器是在没有首先读取中心目录的情况下从头到尾解析zip文件的解析器。就其性质而言,流式解析器不允许任何类型的文件重叠。最有可能的结果是他们只会提取第一个文件。它们甚至可能引发错误,就像sunzip一样,它解析了最后的中心目录并检查它与已经看到的本地文件头的一致性。

如果您需要提取的文件以除本地文件头的字节之外的某个前缀开头,则可以在引用下一个头的非压缩块之前插入DEFLATE块。并非zip文件中的每个文件都必须参与炸弹构造:如果需要,您还可以包含普通文件以符合某种特殊格式。(源代码有一个--template 选项来促进这个用例。)许多文件格式使用zip作为容器; 示例是Java JAR,Android APK和LibreOffice文档。

PDF 在许多方面类似于zip。它在文件末尾有一个交叉引用表,指向文件中较早的对象,它支持通过FlateDecode过滤器对对象进行DEFLATE压缩。我没有尝试过,但也许可以使用引用重叠的想法制作PDF压缩炸弹。甚至可能没有必要努力工作:binaryhax0r在 博客文章中 建议人们可以简单地在单个对象上指定多层FlateDecode,这使得压缩炸弹变得容易。

检测我们在本文中开发的特定类型的拉链炸弹很容易:只需查找重叠文件。Mark Adler已经 为Info-ZIP UnZip 编写了一个补丁。但是,一般来说,拒绝重叠文件并不能防止所有类别的拉链炸弹。除非您准确了解将用于解析它的解析器的内部,否则很难预先确定zip文件是否是炸弹。 通常,查看标题并汇总所有文件的“未压缩大小”字段不起作用,因为标题中存储的值可能与实际的未压缩大小不一致。(请参阅兼容性表中的“允许太短的文件大小”行。)对拉链炸弹的强大保护涉及在操作时对zip解析器设置时间,内存和磁盘空间限制。处理zip解析,作为对不受信任数据的任何复杂操作,请谨慎操作。

Info-ZIP UnZip 6.0 Python 3.7 zipfile 去1.12 档案/邮编 yauzl 2.10.0 (Node.js) 指甲 示例/拉链 Android 9.0.0 r1 libziparchive sunzip 0.4 (流媒体)
DEFLATE
ZIP64
bzip2的
允许不匹配的文件名 警告
允许错误的CRC-32 警告 如果为零
允许太短的文件大小
允许文件大小为2 32 - 1
允许文件数为2 16 - 1
unzips overlap.zip 警告
解压缩zbsm.zip和zblg.zip
解压缩zbxl.zip

所选拉链解析器与各种拉链功能,边框和拉链炸弹结构的兼容性。背景颜色表示从限制较少到限制较多的比例。为了获得最佳兼容性,请使用不带Zip64的DEFLATE压缩,匹配中央目录头和本地文件头中的名称,计算正确的CRC,并避免32位和16位字段的最大值。

致谢

我感谢 Mark AdlerRuss CoxBrandon EnrightMarek MajkowskiJosh Wolfe以及USENIX WOOT 2019评论员对本文草稿的评论。CaolánMcNamara评估了LibreOffice中拉链炸弹的安全影响。

本文的一个版本将出现在 USENIX WOOT 2019 研讨会上。该论文的源代码可用。 准备提交的工件zipbomb-woot19.zip

你有没有找到一个扼杀这些拉链炸弹的系统?他们是否帮助您展示漏洞或赢得错误赏金? 让我知道,我会在这里提一下。

  • LibreOffice 6.1.5.2

    重命名为zblg.odt或zblg.docx的zblg.zip将导致LibreOffice在尝试确定文件格式时创建和删除大量~4 GB的临时文件。它最终完成,它会删除临时文件,因此它只是一个不填满磁盘的临时DoS。CaolánMcNamara回复了我的错误报告。

  • Mozilla addons-server 2019.06.06

    我尝试了针对本地安装的addons-server的zip炸弹,这是addons.mozilla.org背后的软件的一部分。该系统处理它摆好,强加时间限制 的110秒提取。拉链炸弹的扩展速度与磁盘允许达到时间限制一样快,但在此之后,进程被终止并且解压缩的文件最终会自动清除。

  • UnZip 6.0

    Mark Adler 为UnZip 编写 了一个补丁来检测这类拉链炸弹。2019年7月5日:我注意到CVE-2019-13232 已分配给UnZip。就个人而言,我认为UnZip(或任何拉链解析器)处理此处讨论的拉链炸弹的能力必然代表一个安全漏洞,甚至是一个bug。这是一种自然的实现方式,并且不会以任何方式违反规范。本文中讨论的类型只是一种类型的拉链炸弹,并且有许多方法可以解决zip解析可能出错的非炸弹。 如上所述,如果要抵御资源耗尽攻击,你应该尝试枚举,检测和阻止每个已知的攻击; 相反,你应该对时间和其他资源施加外部限制,这样无论面对什么样的攻击,解析器都不会行为过多。尝试检测和拒绝某些结构作为首次通过优化没有任何问题,但你不能就此止步。如果您最终没有隔离并限制对不受信任数据的操作,则您的系统可能仍然容易受到攻击。考虑用HTML中的跨站点脚本进行类比:正确的防御不是尝试过滤掉可能被解释为代码的字节,而是要正确地逃避一切。

  • 防病毒引擎

    Twitter用户@TVqQAAMAAAAEAAA 报告称 “我的测试机器上的McAfee AV爆炸了”。我没有独立确认,也没有版本号等细节。Tavis Ormandy 指出VirusTotal for zblg.zip 中有很多“Timeout”结果 (截图)2019年7月6日)。AhnLab-V3,ClamAV,DrWeb,Endgame,F-Secure,GData,K7AntiVirus,K7GW,MaxSecure,McAfee,McAfee-GW-Edition,Panda,Qihoo-360,Sophos ML,VBA32。 zbsm.zip的结果 (截图2019年7月6日) 是相似的,但有一组不同的超时发动机:Baido,噶,ClamAV的,CMC,DrWeb,残局,ESET,NOD32,F-Secure公司,的GData,金山,迈克菲-GW-版,纳米防病毒时,Acronis 。有趣的是,zbxl.zip的结果没有超时 ; (截图2019年7月6日) 也许这意味着一些杀毒软件不支持Zip64?一些引擎将文件检测为某种压缩炸弹。有趣的是,当进行小的修改时,它们是否仍然这样做,例如更改文件名或为每个文件添加ASCII前缀。

---本文结束感谢您的阅读---
北岸冷若冰霜 wechat
欢迎使用微信扫一扫上面的二维码,订阅我的公众号!
坚持原创分享,点击下方打赏,您的支持将鼓励我继续创作!