差分密码分析基础

差分密码分析（Biham 和 Shamir，1990 年）是一种选择明文攻击，用于分析明文对中的差分如何通过密码传播。通过找出能够以较高概率产生可预测输出差分的输入差分，攻击者可以利用统计方法恢复密钥位。

对于基于 XOR 的密码：差分 ΔX = X XOR X'。对于基于加法的密码：差分 ΔX = X - X' mod 2^n。XOR 差分最常见，因为 XOR 与基于 XOR 的密钥混合可交换（密钥调度的影响会在差分对中抵消）。

差分对 (P, P') 的输入差分为 ΔP = P XOR P'。加密后得到 (C, C')，其输出差分为 ΔC = C XOR C'。有用的差分是具有较高概率 p 的 ΔP → ΔC，也就是说，许多差分为 ΔP 的 (P, P') 对会产生差分为 ΔC 的输出。

DDT（差分分布表）统计：对于每个输入差分 Δx 和输出差分 Δy，有多少个输入 x 满足 S(x) XOR S(x XOR Δx) = Δy。将计数除以 2^n 即可得到概率。优秀的 S 盒的 DDT 最大值为 2（概率为 1/2^{n-1}），不存在强差分。

对于具有 r 轮的分组密码，请找出一条序列 ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}，其中每轮转换的概率都是已知的。将各轮概率相乘：总体概率 p = p1 * p2 * ... * p_{r-1}。攻击需要 2/p 个差分对来恢复最后一轮密钥。

利用一个高概率的 r-1 轮差分：收集 N = 2/p 个明文对。对于每个候选的最后一轮密钥 K'，将两份密文各自解密一轮，对结果执行 XOR，并检查差分是否匹配 ΔU_{r-1}。正确的 K' 大约匹配 N/2 次；错误密钥大约匹配 N/2^{bit_size} 次。

高级加密标准的 S 盒是 GF(2^8) 上的乘法逆变换，后接仿射变换。其 DDT 最大值为 4（共 256 个输入），因此每个 S 盒的差分概率 ≤ 4/256 = 1/64。高级加密标准每轮有 4 个 S 盒，但宽轨设计确保完整差分路径的概率低于 2^{-100}。

Joan Daemen 的宽轨设计（用于高级加密标准/Rijndael）：定义 MixColumns 的分支数 B。任何一轮中的非平凡差分路径都会激活至少 B 个 S 盒。4 轮 × 每轮 4 个 S 盒保证至少有 25 个活跃 S 盒，因此概率 < 2^{-100}。

截断差分只指定差分的一部分（例如只指定哪些列处于活跃状态，而不指定确切的差分值）。这使得针对更多轮的攻击成为可能，而完整差分在这些轮数上通常过于微弱。截断差分曾用于攻击缩减轮数的高级加密标准、SERPENT 及其他 SPN 密码。

不可能差分是指某一对 (ΔP, ΔC) 对任何密钥都不可能发生。任何将观测到的、具有该差分的明文对 (P, P') 映射为相应结果的密钥都会被排除。收集足够多的差分对后，所有错误密钥都会被排除，只剩下正确密钥。

回旋镖攻击（Wagner，1999 年）将两个较短的差分组合成一种自适应的选择明文/密文攻击。它把密码分成两半，每一半都有一个概率较高的短差分，从而能够攻击比任何单个差分所允许的轮数更多的密码。

差分分布表（DDT）在密码分析中的作用是什么？

差分密码分析利用高概率的输入到输出差分传播。高级加密标准通过 DDT 最优的 S 盒和宽轨设计抵抗这种攻击。下一节：线性密码分析和近似表。