概要

如果一个游戏的文件加密程序只对文件逐字节做了以下操作的任意次任意组合

  • 异或一个字节
  • 异或一组字节
  • 取反
  • 比特置换：即对字节上所有比特位的“洗牌”操作，包括左移位，右移位，算术或逻辑移位，循环移位等

但没有 AND 和 OR 操作

假如你能拿到至少一组明文-密文对，就可以用本文的方法自动破解加密算法，生成等价加解密程序


GF(2) 视角下字节的基本运算

逆向里谈 GF(2)，通常指的是这样的域

  • 集合为 {0, 1} 两个比特位
  • 加法为模 2 加法
  • 乘法为模 2 乘法

各种字节运算在 GF(2) 的含义

  • XOR：模 2 加法，也等价于模 2 减法

    • a ^ b = a + b = a - b

  • AND：模 2 乘法

    • a & b = ab

  • OR: 等价如下二次多项式

    • a | b = a + b + ab

  • NOT: 等价于跟 1 异或

    • !a = a + 1


线性变换与仿射变换

以线性代数为例，线性变换是：

$$ y = Ax $$

仿射变换是：

$$ y = Ax + b $$

当 b 是零向量的时候，仿射变换就退化为线性变换

AES 算法中，S-box 的生成有两阶段，第二阶段正是 GF(2) 的仿射变换

GF(2) 世界里的仿射变换

$$ y = Ax + b $$

还是一样的表达式，但变量含义不同

通常我们处理的是字节，一个字节是 8 比特。在上面方程中，x 往往作为字节，也是一个 8 元素的比特向量

$$ x = (bit_1, bit_2, bit_3, bit_4, bit_5, bit_6, bit_7, bit_8) $$

y 和 b 也分别是 8 元素的比特向量

A 是 8 x 8 的矩阵，象征 8-bit → 8-bit 的线性变换

整体语义，就是一个字节 x 里的每个比特，由自身所有位置的比特线性组合，形成一个新字节 Ax，然后跟另一个字节 b 异或，得到结果字节 y


仿射视角下的汇编

  • XOR

    比如 XOR 0x39，就是 y = Ax + b 时，把 A 作为单位矩阵，把 b 写为 0x39 = 0b00111001

$$ b = (0, 0, 1, 1, 1, 0, 0, 1) $$

  • NOT

    取反就是 XOR 1，对应 y = x + b，其中

$$ b = (0, 0, 0, 0, 0, 0, 0, 1) $$

  • SHL

    逻辑左移：每个比特位等于右邻比特值，没有右邻的末尾总为 0

    可以看作 y = Ax 时

$$ A = \begin{pmatrix} 0 & 1 & 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 & 1 & 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 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$

  • ROR 3

    循环右移 3 位：第 i 位比特，等于第 (i - 3) mod 8 位的比特

    可以看作 y = Ax 时

$$ A = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 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 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} $$

  • SAL

    算术左移：在 SHL 的基础上，总是保留首位比特

$$ A = \begin{pmatrix} 1 & 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 & 1 & 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 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$

还有 ROL, SHR, SAR 等等，均可以用 GF(2) 的仿射表达式表示


仿射变换的复合规律

先证明一个关键结论：仿射变换的复合仍是仿射变换

假设

$$ f(x) = A_1x + b_1 \\ g(x) = A_2x + b_2 $$

那么

$$ (f \circ g)(x) = f(A_2x + b_2) = A_1(A_2x + b_2) + b_1 $$

$$ (f \circ g)(x) = A_1A_2x + A_1b_2 + b_1 $$

从形式看，上式中 x 的系数是一个 8x8 的矩阵，偏置项是一个 8x1 向量

令 A = A1·A2，b = A1·b2+b1，可写为

$$ (f \circ g)(x) = Ax + b $$

显然也是仿射变换

更进一步，不难推论：

无论一个文件应用了多少次仿射变换，最终都可等价到一次仿射变换，用一个仿射表达式表示

根据这点，就可以愉快地描述很多游戏文件的加密算法了


举例：各种游戏加密算法的仿射描述

例子 1

以 PC98 游戏 Nanba Kouseke 为例，它的加密算法是先 xor 39，然后 ror 3

xor 39，即线性变换是单位矩阵，设 b1 = 0x39 = 0b00111001，可写作

$$ y = x + b_1 $$

ror 3，即无偏置项，设

$$ A_2 = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 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 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} $$

可写为

$$ y = A_2x $$

复合两个函数，得到

$$ y = A_2x + A_2b_1 $$

例子 2

Win 版游戏 EVE Burst Error，加密算法是逐字节取反，即 xor FF

那么，线性系数是单位矩阵，设 b1 = 0xFF = 0b11111111，可写为

$$ y = x + b_1 $$

例子 3

Yuris 引擎的加密算法有两个密钥，其中对游戏正文的加密（可参考我以前博客 Yu-Ris 引擎研究 ）是循环 xor 4 个字节

假设 xor 的 4 个字节为 b1, b2, b3, b4

这里有两种方法：

  • 方法一：把每个密文/明文文件，每字节分别按位置 i mod 4 = 0/1/2/3 分成 4 个子文件，得到 4 个独立的仿射系统，分别表示为

$$ y = x + b_1 \\ y = x + b_2 \\ y = x + b_3 \\ y = x + b_4 \\ $$

  • 方法二：把 A 在对角线上重复 4 次写成 32x32 的矩阵，y, x, b 扩展为 32 维向量，可以写作

$$ y = Ax + b $$


破解仿射类加密文件的算法

问题的提出：给定一个黑箱模型，如何判定并恢复其未知的仿射变换？

如果这个黑箱的操作可以复合为一个仿射变换。通过上面的例子，不难发现最终表达式可以分为两类：

第一类、没有异或 / 只异或一个字节

这种情况是最简单的，以上面例子 1 为例，最终结果等价于

$$ y = Ax + b $$

密文取 2 个字节相加，消掉偏置项 b（利用异或既是模 2 加法又是模 2 减法，可以互相抵消的特性）

$$ y1 + y2 = (Ax_1 + b_1) + (Ax_2 + b_2) = A(x_1 + x_2) $$

接着，构造差分样本。以一对字节 (x1, y1) 作为基准，后面所有字节对其做差分计算，可得

$$ Δy_2 = y_2 + y_1 = AΔx_2 \\ Δy_3 = y_3 + y_1 = AΔx_3 \\ \dots $$

A 是 64 个未知的比特，选择足够多的字节，对它列线性方程组就能解出

  • 如果无解，考虑第二类

  • 如果解出来，得到确定的加密表达式，代入所有明文-密文样本测试

    • 如果匹配，算法破解成功
    • 若不匹配，考虑第二类

第二类、异或一组字节

假设我们有至少两对明文-密文文件，这种情况比较简单（只有一对明文-密文文件，后面讨论）

用文件间的差分把 b 消掉 → 只剩 A → 解出 A → 消掉 A → 得到 xor-only 模型：

$$ y = x + b $$

这时，只要把明文和密文异或，就可以知道 b，得到仿射表达式

举例

以一个比较复杂的情形为例，假设一个加密算法由 3 个仿射组件构成：先 xor (11 22 33)，再 ror 40，再 xor (44 55 66 77)。这时，复合后的仿射变换为

$$ y = A_3A_2A_1x + f(b_1, b_2, b_3, A_1, A_2, A_3) $$

令

$$ A = A_3A_2A_1 \\ b = f(b_1, b_2, b_3, A_1, A_2, A_3) $$

复合式可写成

$$ y = Ax + b $$

参考例子 3，这里若要保持 A 是 8x8 矩阵，需将偏置项分段

因为两组异或密钥的长度是 3 和 4，所以合成后异或密钥必有为两者的最小公倍数 12 为循环的周期，即

$$ f(b_1,b_2,b_3,A_1,A_2,A_3) = \begin{cases} c_1 \\ c_2 \\ ... \\ c_{11} \\ c_{12} \end{cases} $$

无论分段函数是什么，我们只要找两对明文-密文文件 (x1, y1) 和 (x2, y2)，相加总能抵消偏置项（同时抵消分段周期）

$$ y_1 + y_2 = A(x_1 + x_2) $$

接着，以一对文件为基准，其它所有文件对其做差分运算

$$ Δy_i = AΔx_i （i=2,3,...,n） $$

取足够多的样本，解出 A

令

$$ x' = Ax $$

代入原式

$$ y = x' + b $$

再把 x’ 和 y 异或，就可读出 b。结果必是一个至多以 12 为周期循环的异或密钥


第二类的改进

不同于第一类情况，第二类算法要求拿到至少两对密文-明文文件，实践上有时不容易满足

只拿到一对密文和明文时，可以破解吗？

可以，分两种情况考虑

情况一、异或字节长度已知的情况

比如长度是 4。密文文件取前 4 字节为基准字节组，整个文件删掉前 4 个字节，剩余文件每 4 字节跟基准字节组异或，得到新密文文件 Δy。同样对明文文件做相同操作，得到新明文 Δx，这样就抵消掉偏置项，新密文-明文对里只有线性关系 Δy = AΔx

然后（作为一个没有异或的黑箱）按第一类的方法求解出 A，再回代解出 b

情况二、异或字节长度未知的情况

核心思想是求出异或字节长度，然后转化为“异或字节长度已知的情况”去解

因为单字节异或是逐字节双射

  • 所有 A 都加密成 X，因此原文中 A 的频率和密文中 X 的频率是相同的
  • 所有 B 都加密成 Y，因此原文中 B 的频率和密文中 Y 的频率是相同的

所以这种加密有个特点：取原文各个字节的频率排成向量，和密文各个字节的频率向量，两者是重排序的关系。

考虑向量比较不方便，因此对所有字节的频率取平方和，压缩为一个统计量，这个统计量就是 IC（重合指数，现实意义上视为从文本中随机取两个字节，两个字节相等的概率）

同样的，对单字节仿射加密 y = Ax + b，因为 x ↔ Ax，Ax ↔ y，所以 x ↔ y

单字节异或前后，这个统计量不变。多字节循环异或的时候，统计量会被破坏。而多字节循环异或可以拆为多个独立的单字节异或，每个分组里统计量不变。利用这点，将明文和密文按不同周期分组计算 IC，选出所有 IC 一一相等时对应的周期，即为长度


代码

https://github.com/dantecsm/affine-attack


后续课题

VN 游戏逆向中，往往不容易直接获取完整对齐的明文和密文对，只知道一段文本和它来源于哪个加密文件才是常态。一段文本用 SJIS 编码表示，可以视为明文文件的一小段，即，问题可重定义为：

给定一个黑箱模型，只有完整密文和部分明文的情况下，如何判定并恢复其未知的仿射变换？

最经典的做法，就是对明文异或 00-FF 生成 256 个样本，然后搜索它们是否在密文中出现——这是针对只异或一个字节的加密，作为快速检查有一定成功率，但不通用

首先还是去异或

  • 若仿射过程至多异或一个字节：让密文，明文每个字节跟第一个字节异或，就得到一个去除偏置项的密文，明文样本。
  • 若仿射过程循环异或多个字节：参考上面“第二类的改进”讨论，利用周期性去异或

然后就变成一个 y = Ax 的问题了

理论上讲，假设明文有 N 个字节，遍历密文所有相邻的 N 字节组合，代入求解就行。但这种做法相当耗时

考虑到大多数游戏加密算法最终还需解密。解铃还须系铃人——很多 VN 游戏开发者不会用不可逆的变换去加密字节。因此，虽然仿射变换的定义很广，但实际大多数时候的加密只涉及对比特位的重排序（shuffle）操作。这种操作有个特点——每个字节从二进制视角看，0 和 1 的个数是相等的

利用这个特点，先逐字节计算明文的每个位置的二进制比特之和，形成一个向量，再筛选密文所有 N 字节组合里跟它匹配的样本，只检验它们就行

除此之外，像 Race Queen Risa 和 D-sparay 等游戏，不仅有比特置换，还有字节置换的操作，比如，每 4 个字节按 2 1 0 3 重排，或者逐 len 长区间里每个字节按 i * 7 mod (len) 的方式重排等。这些操作并不会改变它所定义的区间里所有字节的比特和，即使后续复合了比特置换和异或，本质上在它所操作的变换区间里，也还是仿射变换

可以假定一个 T 长的区间，比如为 4。在这个区间内数据用 y = Ax + b 的仿射变换描述，x, y, b 为 32 长向量，A 为 32*32 矩阵，然后解这个方程。后续再讨论