不可能差分

差分分析着力于寻找高概率的长差分路径，要求输入和输出差分满足差分传播轨迹。

在理论分析阶段，差分轨迹（特征）作为区分器来判断给定的 oracle 是真随机还是加密机。当然，拿到区分器后，可以从区分器的首尾扩展，来实现密钥恢复。

• 而不可能差分与差分分析刚好相反，其着力于寻找一段长不可能差分轨迹，要求某些固定位置的输入差分 (0,a,0,0) 经过一定轮数 r 传播，无论如何也达不到某些固定位置的输出差分 (b,0,0,0) ，例如：

输入差分为 01

S(00) XOR S(00 XOR 01) = 01

S(01) XOR S(01 XOR 01) = 01

S(10) XOR S(10 XOR 01) = 01

S(11) XOR S(11 XOR 01) = 01

得到的全空间输出差分没有包括 00,10,11，但 00 是零差分，所以，得到该 S 盒的不可能差分为：

在 99年，Biham，Biryukov 和 Shamir 的文章 Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials 中，给出了一种类似中间相遇的方法来寻找不可能差分轨迹，称作 miss in the middle，其原理是：

• 寻找中间某轮的不可能差分传播来构建不可能差分轨迹，在此轨迹上的差分均为不可能差分。

如其在文章中的描述，找到 24 轮对 Skipjack 的不可能差分轨迹，该轨迹在第 12 轮以不可能的差分传播，讲前 12 轮和后 12 轮连接，形成的 24 轮差分轨迹使用正确密钥加密的消息不可能满足。如：

假设差分轨迹 $\alpha \to {\gamma }_1\backslash alpha\; \backslash rightarrow\; \backslash gamma\_1$，和 ${\gamma }_2\to \beta \backslash gamma\_2\; \backslash rightarrow\; \backslash beta$ 均以概率 1 传播

其中间差分传播 ${\gamma }_1\to {\gamma }_2\backslash gamma\_1\; \backslash rightarrow\; \backslash gamma\_2$ 以概率 0 传播（即不可能）

所以差分轨迹 $\alpha \to \beta \backslash alpha\; \backslash rightarrow\; \backslash beta$ 为一条不可能差分轨迹。

$\alpha \to {\gamma }_1\nrightarrow {\gamma }_2\to \beta \backslash alpha\; \backslash rightarrow\; \backslash gamma\_1\; \backslash nrightarrow\; \backslash gamma\_2\; \backslash rightarrow\; \backslash beta$

续，找到差分轨迹的 U-method