ZIP 明文攻击原理 2021年12月14日
程序
0 条评论

在看 CTF 时发现了 zip 明文攻击的攻击方式，然而举的例子里基本都是使用工具——也就是 ARCHPR 简单完成破解，转而进行下一步操作，对明文攻击本身并没有做更多解释。本想看看 ARCHPR 的明文攻击实现的，结果发现这东西是商业软件……于是开始找其他资料。

简单搜了一圈发现这种攻击是基于 Biham 和 Kocher 在 94 年发表的论文《A Known Plaintext Attack on the PKZIP Stream Cipher》实现的。

明文攻击主要利用大于 12 字节的一段已知明文数据进行攻击，从而获取整个加密文档的数据。也就是说，如果我手里有一个未知密码的压缩包和压缩包内某个文件的一部分明文（不一定非要从头开始，能确定偏移就行），那么我就可以通过这种攻击来解开整个压缩包。比如压缩包里有一个常见的 license 文件，或者是某个常用的 dll 库，或者是带有固定头部的文件（比如 xml、exe、png 等容易推导出原始内容的文件），那么就可以运用这种攻击。当然，前提是压缩包要用 ZipCrypto 加密。

也就是说从明文到密文的这个流程中我们有了头尾两端的数据，再利用加密算法中的弱点还原出加密密钥，从而解密整个压缩包（同一个压缩包的文件都是用同一个密钥加密）。但是仍然要注意，如果文件在加密前经过了压缩，加密算法的输入不再是我们所知道的明文而是压缩后的数据，明文攻击会失败（在压缩包里查看文件的属性可以看到压缩方式，比如“ZipCrypto Deflate”就是加密压缩，“ZipCrypto Store”就是加密储存）。这就多了找出明文压缩后的数据这样一个额外步骤。

ZipCrypto

要想攻击首先需要知道 ZipCrypto 的加密方式。这个加密算法是面向字节流的（而现代对称加密算法是对一个分组进行加密），它内部使用了 3 个 32 比特的整数来表示密钥，可以将它们称为 key0，key1 和 key2。通常我们在打包文件时输入的密码会被转换成这 3 个 dword。算法基本就是用一个循环来加密数据，加密函数记为 UpdateKeys，cpp 代码如下：

// p 是用来更新内部 key 的明文
// lsb、msb 分别表示取 dword 的最低和最高字节（不是位）
void PKCipher::UpdateKeys(uint8_t p) {
  k0 = crc::Crc32(k0, p);
  k1 = (k1 + crc::lsb(k0)) * 134775813 + 1;    // 134775813 是 magic number
  k2 = crc::Crc32(k2, crc::msb(k1));
}
uint8_t PKCipher::GetK3() {
  uint16_t tmp = k2 | 3;
  return crc::lsb((tmp * (tmp ^ 1)) >> 8);
}
void PKCipher::Encrypt(std::vector<uint8_t>& data) {
  for (uint8_t& p : data) {
    uint8_t c = p ^ GetK3();
    UpdateKeys(p);
    p = c;
  }
}

UpdateKeys 仅仅是更新了内部 key，真正对明文进行加密用的是从 key2 派生出来的 16 比特的 key3。可以看到，不仅 key3 只有 16 比特长，它的低两位因为和 3 做了位与操作所以必然是 1，使得 key3 的取值范围缩小到 \(2^{14}\)，这就有了反推的基础。

明文攻击

先将明文的序列记为 P，下标从 1 到 n，这里的 \(P_1\) 是指序列中的第一个，并不一定代表这是第一个明文字节。同样有密文序列记为 \(C_{1 \ldots n}\)，密钥序列 \(Key0_{1 \ldots n}\)，\(Key1_{1 \ldots n}\) 和 \(Key2_{1 \ldots n}\)。根据

uint8_t c = p ^ GetK3();

我们首先就能得到相应的 \(Key3_{1 \ldots n}\) 序列。

Key2

Key3 只受 Key2 的 [2..16) 位影响，所以 Key2 一共有 \(2^{14}=16384\) 个可能，而 Key3 只有一个字节，即 256 个不同的值，那么反过来从一个已知的 Key3 平均可以映射到 \({16384 \over 256}=64\) 个可能的 Key2[2..16)，剩下的比特位仍然未知。
由 crc32 的逆运算可以得到 $$\begin{align} Key2_i & = crc32^{-1}(Key2_{i+1}, MSB(Key1_{i+1})) \\\\ & = (Key2_{i+1} << 8) \bigoplus crcinvtab[MSB(Key2_{i+1})] \bigoplus MSB(Key1_{i+1}) \end{align}$$ 来看公式右边的三个部分：

  1. 在 \(Key2_{i+1}\) << 8 中它的低 8 位总是 0，而 Key2 的最低两位在 Key3 逆推时也没有考虑在内，所以计算结果的 [10,32) 是“有效”的，会影响下一个迭代的 Key2
  2. \(crcinvtab[MSB(Key2_{i+1})]\) 的值对每个可能的 Key2 都是确定的，并且 [0,32) 位都有效
  3. \(MSB(Key1_{i+1})\) 它的结果是一个字节，那么 [8,32) 都是 0，只有 [0,8) 会影响 Key2

这样等式两侧的比特位取个交集可以看到 Key2[10,16) 的比特位是两边都知道的，而我们也知道每个 \(Key2_i\) 在 [2,16) 范围里都有 64 个可能的值，那么通过对比相邻 Key2 的 [10,16) 部分，找不到相等值的 Key2 就可以排除掉，从而减少我们的搜索空间。比如从 64 个结果中取出一个可能的 \(Key2_i\)，遍历 64 个 \(Key2_{i-1}\)，如果所有 \(Key2_{i-1}\) 的 [10,16) 部分和当前的 \(Key2_i\) 都不相等，那么就可以排除掉这个 \(Key2_i\)。显然 Key2 的序列越多，能排除的值也越多，实际操作中只要使用二十多个字节就能大幅缩小可能的值。

Key1

缩小 Key2 的数量后就要开始一个个枚举了，中间计算出的所有可能值最终都要一个个验证并排除。继续根据公式倒推。迭代 Key2 时有个 \(MSB(Key1_{i+1}])\) 在里面，现在我们在逐个枚举 Key2，那么这个过程中我们也可以得到所有 Key1 的最高字节（准确说是从第三个 Key1 开始，因为倒推 Key2 时我们只能倒推到第二个为止，根据公式第一个 Key2 需要第零个 Key2，算不了）。
再看 Key1 的。$$Key1_{n-1} + LSB(Key0_n) = (Key1_n – 1) * 134775813^{-1}$$ \(134775813^{-1}\) 是 134775813 的乘法逆元，可以计算出它的真实值是 0xd94fa8cd，并不是它的倒数。
因为我们现在已经确定 Key1 的最高字节，那么在公式两边同时取 MSB 就可以建立 \(Key1_n\) 和 \(Key1_{n-1}\) 之间的关系。因为 \(LSB(Key0_n)\) 只是一个字节，在左边整体取完 MSB 后它最多只会使最终结果加一或减一，在实际比较中只要加上这个处理就行。然后如法炮制，遍历 Key1 的 [0,24)，找到可能的 Key1 值，然后继续搜索下一个可能值即可（这部分可以打表大幅优化速度）。

Key0

同样上面遍历 Key1 时我们也得到了相匹配的 Key0 （可能的）最低字节序列。然后计算 \(Key0_{n+1}\) 则直接根据 UpdateKeys 函数计算 crc 即可。
论文里提到说 crc32 是线性函数，只要有四个连续的 LSB(Key0) 和与它配对的明文就可以完整还原出四个 Key0 的值。然后只要有了一个完整的 Key0，所有 \(Key0_{1 \ldots n}\) 的值也都能推出来。
因为 UpdateKeys 里那个 crc32 展开后是 $$Key0_{n+1} = (Key0_n >> 8) \bigoplus crctab[LSB(Key0_n \bigoplus P_n)]$$（其中 P 代表明文）。\(LSB(Key0_n)\) 和 \(P_n\) 已知，那么可以得到唯一的 \(MSB(Key0_{n+1})\)。然后已知 \(Key0_{n+1}\) 的 [0,8) 和 [24,32)，再计算，可以得到 \(Key0_{n+2}\) 的 [0,8) 和 [16,32)。再下一个就是完整的 [0,32) 了，所以能全部还原出来。bkcrack 的代码中是

  1. 直接从 \(Key0_5\) 算到 \(Key0_8\)（算出了完整的 \(Key0_8\)）
  2. 然后用已知的 \(Key0_8\) 到 \(Key0_{11}\) 的 LSB 验证上一步的结果
  3. 再从 \(Key0_8\) 倒推至 \(Key0_4\)
  4. 利用 Key2 的迭代公式，代入 \(Key2_2\) 倒推出 \(Key1_2\) 的 [26,32) 位（因为推导 Key2 时低两位没参与，所以这里得到的 Key1 也抠掉了两位）
  5. 利用 Key1 的迭代公式配合得到的 Key0，将 \(Key1_4\) 和 \(Key0_4\) 代入并倒推两次得到 \(Key1_2\)
  6. 比较上面两步各自得到的 \(Key1_2\) 的差，如果小于 \(2^{27}-1+256\) 则通过验证（因为公式里还有个 LSB(Key0)，所以再加上 256）

原始 Key

全部算完后就可以开始算最初的三个 key 了。将 3 个 key 的第八次迭代值作为初始值，配合明文进行 UpdateKeys 的逆运算。这里倒推时除了明文的部分（比如这里从第八个字节的明文开始）遍历完之外，还有 12 个字节的 ZIP 头部也要接着遍历，这才把原始 key 都拿到手。



我写的样例代码也是参考 bkcrack，虽然能也能跑出结果但是因为没做优化所以慢得一批，姑且留了一份。