积分攻击

Posted on Edited on In
给定一组结构化输入（不是任意随机明文），把它们喂入若干轮分组密码后...

积分攻击（Integral Cryptanalysis）

原理（直观）
给定一组结构化输入（不是任意随机明文），把它们喂入若干轮分组密码后，观察某些状态位置的聚合统计（例如按位 XOR 求和）是否出现不变量（invariant）。只要这种不变量高概率成立，我们就得到一个区分器。对 10 轮 SM4 的 oracle 情形，这种攻击非常有效。

前置知识 / 记号

  • 活跃（active）：某个字节在输入集合里遍历全部取值（通常为 0..255），记作 A。
  • 均衡（balanced）：把该位置在整组样本中的值按位 XOR，结果为 0，记作 B。 ⨁i=1Nxj(i)=0 \bigoplus_{i=1}^{N} x^{(i)}_j = 0
  • Δ-集（delta set）：在输入向量中，选若干位置为活跃字节，其余位置固定为常量 C。
  • 阶数（order）：同时活跃的位置个数。阶数越高，需要的输入量越大，但传播能力也越强（能穿透更多轮）。

记法补充：我们把固定的常量记为 C。

为什么会存在这种不变量？

1. S 盒变换后不改变 XOR 和（直观）

对于任意 n-bit 置换 SS：若集合 V\mathcal V 中的元素按位 XOR 为 0，则把每个元素都过同一个 S 盒后，新的集合仍然按位 XOR 为 0：

(⨁v∈Vv=0)⟹(⨁v∈VS(v)=0) \Big(\bigoplus_{v\in\mathcal V} v = 0\Big)\Longrightarrow \Big(\bigoplus_{v\in\mathcal V} S(v) = 0\Big)

（因为 S 是对每个输入位置的置换，不改变“集合内每个值出现次数”的性质 —— 若原集合在每个位上是均衡的，映射后仍然均衡。）

2. 线性层的“搬运”性质

线性变换对 XOR 是线性的：

L(⨁iv(i))=⨁iL(v(i)) L\Big(\bigoplus_i v^{(i)}\Big)=\bigoplus_i L\big(v^{(i)}\big)

因此，如果在经过若干轮（S 盒 + 线性层）的某一步某些字节对整组样本 XOR 为 0，那么这些均衡性经过线性层后，会在其它位置以可预测的方式“搬运”或重新出现。论文中通常通过逐轮分析可证明这种搬运关系。

设计积分（对实战的步骤）

  1. 选活跃集（构造 Δ-集）：挑一个或几个字节做 A（针对 10 轮 oracle SM4 常常需要选两个活跃字节），其余位置固定为常量 C。
  2. 逐轮传播分析：对构造的 Δ-集分析经过每轮（S 盒 + 线性层）后活跃/均衡如何传播，找到在哪一轮哪个字节会出现均衡（B）。
  3. 找平衡：在第 N 轮后的某个字节出现对全体样本 XOR = 0 的 B（对 10 轮 oracle SM4，常见目标是在第 9 轮出现平衡字节）。
  4. 对比理想随机置换：在理想随机置换下，出现 B 的概率极低。因此若观测到 B，说明存在结构性偏差，从而可以构造区分器。

如何从 B 反推轮密钥 / 主密钥

  1. 当在某轮某些字节观测到均衡 B 时，可以用线性掩码或穷举子字节输入值的方式，判断哪些 S 盒的输出被约束（即哪些 S 盒输出对于整个样本集合 XOR 为 0）。
  2. 通过将这些约束“逆向传播”到该轮的子密钥相关位，枚举或筛选出满足约束的候选轮密钥字节。
  3. 把找到的轮密钥片段合并、验证并向前/向后推导（或借助已知的密钥调度关系）得到更多轮密钥，最终恢复主密钥 MK。