ZIP 明文攻击原理(上)
文章目录
【注】本文最后更新于 October 14, 2019,文中内容可能已经过时。
不会有下了
前言
ZIP 的明文攻击可以说是我在 CTF 里学到的最有用的玩意儿之一了。然而比较残念的是这玩意儿竟然是 CTF 里少有的既常用又不知道原理的玩意儿。。。
这怎么能忍呢?这么有用的东西竟然没人分析!利用明文攻击从网络上破解一下加密资源(嘿嘿嘿),不比 RSA 那堆实际生活中根本用不上的攻击算法有用多了吗!
于是我就打算再次(划掉)研究一下 ZIP 的明文攻击。这么有趣的东西怎么可以不知道原理呢!而且知道原理以后还可以魔改出题(大雾
ZIP 明文攻击简介
明文攻击,顾名思义是知道明文的攻击(
简单地来讲,就是当我们知道一个加密压缩包内某个文件的内容的时候,我们就可以利用明文攻击迅速有效找出 keys(可以理解为 password 的内部表示形式),从而破解这个压缩包。(password 不一定能成功还原,不过解压文件有 keys 就够了
在 CTF 中常见的玩法是给一个 xxx.jpg 和一个 xxx.zip,然后查看 xxx.zip 发现里面也有 xxx.jpg,和一个 flag.txt——暗示地非常明显的明文攻击题目。
比较高级一点的,可能会利用某些文件头之类的来当做明文,比如 XML 文件开头很可能是 <?xml version="1.0"
前置知识
Rust 简介
本文主要使用 Rust 描述算法。
原因当然是因为我喜欢 Rust (划掉
原因是我们需要斯必得(speed),所以肯定不能用 Python(用 Python 还不如用 JS 。。。 C 语言虽然有斯必得,但是 C 语言。。。你可以看看 pkcrack 的源码,再对比一下 bkcrack 的源码。。。 pkcrack 也就注释多一点这点比较强了
C++ 虽然也有斯必得,但是我不会 C++ (理直气壮
所以我就选择了 Rust —— 由 Mozilla 公司创造的伟大语言!虽然学习曲线有点陡峭,但一旦越过写起来就非常 excited。
Rust 的教程可以参照:Rust 程序设计语言 (不过只是读代码的话感觉不看应该也读得懂,比如我看 bkcrack 的源码的时候就完全不懂 C++
ZIP 传统加密算法
要想研究 ZIP 的明文攻击,我们首先得熟悉 ZIP 的传统加密算法(这里强调“传统”,是因为这么不可靠的加密算法其实早就有替代方案了。当然很多压缩软件为兼容性考虑默认还是使用传统加密算法,这就给了我们可乘之机(讲得自己跟犯罪分子一样(
ZIP 的传统加密,本质上也是异或加密。当然,不是用 password 异或,而是用一个伪随机数流来和明文进行异或。而产生这个伪随机数流,需要用到三个 keys,下文分别以 x,y,z 代指。这三个 keys 非常重要,加密解密过程实质上只需要这三个 keys,密码的作用其实是初始化这三个 keys。
简要介绍一下加密流程:在加密前,首先会用密码作为种子初始化这个伪随机数流,然后每加密一个 byte,都会用这个 byte 作为输入产生下一个伪随机数(这个随机数称为 k )。
解密过程也是差不多的,首先初始化伪随机数流,然后每解密一个 byte,都用解密后的 byte 作为输入产生下一个伪随机数。
这个算法非常简单,我们可以直接看代码
|
|
非常简洁易懂的加密对吧,好了进入下一节
CRC32 的查表法与逆
这个其实没什么好讲的,主要就是如何用查表优化 CRC32 的计算以及逆 CRC32
这类文章网上一抓一大把,这里只给结论了(其实是我不知道原理 $$ \mathrm { crc32 = crc32(pval, char) = (pval \gg 8) \oplus crctab[LSB(pval) \oplus char] } \\ \mathrm { pval = crc32^{-1}(crc32, char) = (crc32 \ll 8) \oplus crcinvtab[MSB(crc32)] \oplus char } $$ 而 crctab 和 crcinvtab 的生成算法见下面的代码
|
|
明文攻击
step1 - 生成 K 列表
首先,称 get_k()
函数的返回值,也就是那个用来加解密的伪随机数为 k
然后,现在我们已经拿到了明文和密文。显然,将明文和密文异或,我们就可以得到 k 的序列。这应该是显而易见的,毕竟 k ^ plain_byte = cipher_byte
,那么由异或的性质我们就可以推出 cipher_byte ^ plain_byte = k
step2 - 从 K 到 Z
拿到了 k,接下来就轮到 z 了。
观察 k 的生成代码
|
|
可以发现 k 是由 temp 计算得到的,而 temp 是由 z 计算得到的。真是 excited,竟然只有 z 一个未知量。
那么如何用 k 推出 z 呢?当然是推不出的,我们只能推出一个大概的范围。
冷静分析一下,注意到 (self.z | 3)
这个操作,使得 temp 最低两位始终为 1,消除了 z
的 2 个最低有效位的影响;
而 temp 是 u16
类型的,消除了 z
的16个最高有效位的影响。于是 temp 的值仅仅取决于 z
的 [2, 16) 位,共计 14 位。为了方便接下来的讨论,我们将这 14 位命名为 bits1。
bits1 只有 14 位,那显然 temp 的值就一共只有 $2^{14}$ 种可能性。而 k 作为一个 u8 类型的变量,它的值只有 $2^8$ 种可能性。 也就说是,平均起来对于每一个确定的 k,存在 $2^{14} \div 2^8 = 2^6 = 64$ 个 temp 与之对应,同理,也只有 64 个 bits1 与之对应 。当然这只是统计学意义上的推断,不能当做证明。
接下来我们来证明一下
|
|
运行一下这个程序,没有报错。说明是对的,证明完毕(你们可能会觉得这个证明很扯,但是我觉得我已经很贴心了—— 论文中 TM 提都没提这个结论是怎么来的(当然应该有数学意义上的证明不过懒得推了(其实是不会
也就是说,给定一个 k,我们能推出 $2^{6} $个可能的 temp, 对应的可以推出 $2^{16}$ 个可能的 bits1。再加上 z 的未知的 16 个最高有效位,我们通过一个 k 可以推出 $2^6 \times 2^{16} = 2^{22} $ 个可能的 z 的 30 个最高有效位 的值。
列一下代码
|
|
$2^{22}$ 个可能的值,有点多啊。。。这还只是 z 呢。。。
step3 - 缩小 Z 范围
这么多 z 完全没法玩,因为利用一个确定 z 进行一次攻击的复杂度是 $2^{16}$(后文会提到), 不优化一下的话整个攻击的复杂度就到了 $2^{22} \times 2^{16} = 2^{38}$,完全没法做下去了。
不要慌,我们这还只用了一个已知明文 byte,而进行攻击只需要 12~13 个 bytes(同样后文会提到) 我们可以用剩下的 bytes 来想办法减少 z 的候选值。
观察一下 z 的更新代码,发现这里比较麻烦,有两个变量——上一轮的 z 和这一轮的 key1
|
|
为了直观一点我们写成如下形式,i 表示第 i 轮 $$ \mathrm { Z_{i+1} = crc32(Z_i,MSB(Y_{i+1})) } $$ 借用前置知识里关于 crc32 的结论,这个表达式可以改写为 $$ \begin{align} \mathrm {Z_i} & = \mathrm {crc32^{-1}(Z_{i+1}, MSB(Y_{i+1}))} \\ & = \mathrm { (Z_{i+1} \ll 8) \oplus crcinvtab[MSB(Z_{i+1})] \oplus MSB(Y_{i+1}) } \end{align} $$ WOW,看起来更复杂了(其实没有
冷静分析一下,假设我们从那 $2^{22}$ 个 $\mathrm {Z_{i+1}}$ 的 30 个最高有效位 的可能值中取出一个:
- 我们知道 $\mathrm {Z_{i+1}}$ 的30 个最高有效位值,那显然 $\mathrm { Z_{i+1} \ll 8 }$ 的 [10, 32) 位我们是知道的‘
- $\mathrm {crcinvtab[MSB(Z_{i+1})]}$——显然我们知道它的整个值
- $\mathrm {MSB(Y_{i+1})}$——表面上看起来这完全是个未知量,其实不然,如果把它当成一个 u32 变量的话,显然它的 [8, 32) 位我们是知道的 —— 全是 0
- $\mathrm {Z_i} $ —— 根据和 $\mathrm {Z_{i+1}}$ 一样的方法我们可以推导出它的 [2, 16] 位,虽然可能值有 64 个。。。
这个地方不妨列个表
Side | 表达式 | 已知位数 | 分布范围 | 值的个数 |
---|---|---|---|---|
左边 | $\mathrm {Z_i}$ | 14 | [2, 16] | 64 |
右边 | $\mathrm {Z_{i+1} \ll 8}$ | 22 | [10, 32) | 1 |
$\mathrm {crcinvtab[MSB(Z_{i+1})]}$ | 32 | [0, 32) | 1 | |
$\mathrm {MSB(Y_{i+1})}$ | 24 | [8, 32) | 1 | |
左侧总计 | 14 | [2, 16] | 64 | |
右侧总计 | 22 | [10, 32) | 1 | |
两侧已知位范围交集 | 6 | [10, 16) | ||
两侧已知位范围并集 | 30 | [2, 32) |
这里有两个很重要的点:
- 两侧的 [2, 32) 位是相同的(好像是废话。。。
- 两侧的 [10, 16) 位都是已知的
这有啥用呢?
我们可以利用这个性质来缩小 $\mathrm {Z_i}$ [2, 32) 位的可能值的范围! 正常来讲 $\mathrm {Z_i}$ 应该和 $\mathrm {Z_{i+1}}$ 一样都有 $2^{22}$ 个可能值。 然而利用上文的结论,我们可以依次取出一个 $\mathrm {Z_{i+1}}$ 的值,然后计算出 $\mathrm {crc32^{-1}(Z_{i+1}, MSB(Y_{i+1}))}$ 的 [10, 16) 位 (值得一提的是由于只要 [10, 16) 位,$\mathrm {MSB(Y_{i+1})}$ 的值我们可以直接填 0 —— 因为它的 [10, 16) 位都是 0),然后对比 $\mathrm {z_i}$ 的 [2, 16) 位的候选值中哪些值的 [10, 16) 位和它相同,就可以缩小 $\mathrm {Z_i}$ 的[2, 16) 位可能值的范围(平均来讲刚好可以将 64 个值缩小到一个),继而缩小 $\mathrm {Z_i}$ 的范围,然后按照以此类推缩小 $\mathrm {Z_{i-1}}$ 的范围,缩小 $\mathrm {Z_{i-2}}$ 的范围,etc
(需要注意的是这个范围不会一直缩小,后期会不断浮动,实际操作中需要记录最小范围
这个过程的代码如下
|
|
step4 - Attacking!
(在念这个的时候我脑子里其实是美国大兵的语音)
从 Z 到 Y
根据 update_keys 函数,我们得到得到以下推论(这也是显而易见的,可以参照 step3 里的那个式子 $$ \mathrm { MSB(Y_{i+1})=(Z_{i+1} \ll 8) \oplus crcinvtab[MSB(Z_{i+1})] \oplus Z_i } $$ 很显然,给定一个 Z($\mathrm {Z_n}$,$\mathrm {Z_{n -1}}$,…,$\mathrm {Z_{2}}$) 列表,我们可以得出对应的 MSB(Y) ($\mathrm {MSB(Y_{n})}$,$\mathrm {MSB(Y_{n-1})}$,…,$\mathrm {MSB(Y_{2})}$)列表。全然不够啊,还有 $2^{24}$ 位是未知的。
冷静分析一下,首先我们从 update_keys 函数可以得知 $$ \mathrm {Y_i = (Y_{i-1} + LSB(X_i)) \times 08088405h + 1 \ \ \ (mod 2^{32})} $$
即 $$ \mathrm {(Y_i - 1) * 08088405h^{-1} = Y_{i-1}+LSB(X_i)} $$
然后两边取 MSB,就(很可能)可以得到以下表达式 $$ \mathrm {MSB((Y_i - 1) * 08088405h^{-1})=MSB(Y_{i-1})} $$ 诶,$\mathrm {LSB(X_i)}$ 咋没了。。。因为它太小了。。。才 8 位,而我们这里只保留高 8 位。去掉它绝大多数情况下都不会影响表达式成立。
于是我们现在成功建立了 $\mathrm {Y_i}$ 和 $\mathrm {Y_{i-1}}$ 之间的联系,现在可以用这个关系来缩小 Y 的可能值的范围(似曾相识的手法
首先,穷举 $\mathrm {Y_i}$ 的 [0, 24) 位的可能值。然后判断能否使上面的表达式成立。这个可以将值缩小到原来的 $\frac{1}{2^8}$ ,也就是说只剩下 $2^{16}$ 个 Y 的可能值了。这也就是整个攻击过程的复杂度了,接下来的步骤都是固定的,时间复杂度是 O(1)。
MSB(a) - MSB(b) = MSB(a - b)
or MSB(a) - MSB(b) = MSB(a - b) + 1
从 Y 到 X
现在我们有(最多)$2^{38}$ 个可能的 Y 值列表。
如何获取 X 呢?
由上文的公式 $$ \mathrm {Y_i = (Y_{i-1} + LSB(X_i)) \times 08088405h + 1 \ \ \ (mod 2^{32})} $$ 变形可得 $$ \mathrm {LSB(X_i) = (Y_i -1) \times 08088405h^{-1}-Y_{i-1} \ \ \ (mod 2^{32})} $$ 于是我们获得了 X 的 [0, 8) 位,还剩 24 位。
观察 update_keys 最后一个还没用到的式子 $$ \begin{align} \mathrm {X_i }&= \mathrm {crc32(X_{i-1},P_i)} \\ &= \mathrm {(X_{i-1} \gg 8) \oplus crctab[LSB(X_{i-1}) \oplus P_i]} \end{align} $$ 这是一个很诱人的式子,它意味着只要我们找到一个 X 的可能值,我们就能推出整个唯一的 X 列表。
那么如何找到呢?请听下回分解。
文章是半年前写的,本来打算写完再发的,但是因为我估计不会填这个坑了,所以干脆就这样发出来吧。如果有对这方面感兴趣的同学,或许可以让他少走一些弯路。
没有下回了。因为论文后面看不懂了,也不想看了。这种该讲解的地方不讲解,不用讲解的地方反倒讲解的文章读起来太糟心了。想了想,也许这就是“知识的诅咒”吧。
参考资料 (假装严肃
- Biham, E., & Kocher, P. C. (1994, December). A known plaintext attack on the PKZIP stream cipher. In International Workshop on Fast Software Encryption (pp. 144-153). Springer, Berlin, Heidelberg.
- PKWARE Inc. .ZIP File Format Specification. from https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT
- Kimci86. bkcrack source code. from https://github.com/kimci86/bkcrack
- conrad. pkcrack. from https://www.unix-ag.uni-kl.de/~conrad/krypto/pkcrack.html
- Mark Stamp. Breaking Ciphers in the Real World. Retrieved April 15, 2019, from San Jose State University, Department of Computer Science Web site: http://www.cs.sjsu.edu/~stamp/crypto/