差分分析学习（二）

在上一篇文章的最后，我们画出了一张差分分布表：

为了分析接下来的 CipherThree，我们需要做一个抽象，定义一下 差分特征（differential characteristic）：两个具有差分 $\alpha$ 的输入，在经过操作 $S[\cdot ]$ 后得到两个具有差分 $\beta$ 的输出，那么这一对 $(\alpha,\beta)$ 就被称为 差分特征，可以表示为 $\alpha \xrightarrow S \beta$.

CipherThree

按照前面所说的对 CipherTwo 的攻击，攻击者猜测 $k_3$，计算 $y_0$ 和 $y_1$，计算 $x_0\oplus x_1$. 为了验证猜测是否正确，攻击者输入的消息 需要通过 2 个 S 盒.

从差分分布表中，我们可以读出：

• 两个具有差分 $\texttt{f}$ 的消息，以 $\frac{10}{16}$ 的概率产生具有差分 $\texttt{d}$ 的输出.
• 两个具有差分 $\texttt{d}$ 的消息，以 $\frac{6}{16}$ 的概率产生具有差分 $\texttt{c}$ 的输出.

因此我们可以组合两个 S 盒的操作：

• 对第 1 个 S 盒使用特征 $\texttt{f} \xrightarrow S \texttt{d}$.
• 对第 2 个 S 盒使用特征 $\texttt{d} \xrightarrow S \texttt{c}$.

如果假设这些特征是相互独立的，那么这个 2 轮特征 $\texttt{f} \xrightarrow S \texttt{d} \xrightarrow S \texttt{c}$ 的概率就是 $\frac{10}{16}\times \frac{6}{16}$. 也就是说，攻击者输入具有差分 $\texttt{f}$ 的消息，可以以 $\frac{15}{64}$ 的概率预期 $y_0\oplus y_1$ 的值是 $\texttt{c}$. 给定足够多的明文-密文对，像 CipherTwo 的攻击那样操作，我们就可以恢复密钥 $k_3$.

CipherFour

CipherFour 是一个 $r$ 轮的迭代加密，块大小为 16-bit.

让我们考虑对 CipherFour 的差分攻击. 如果我们试图进行 CipherThree 中类似的攻击，那么首先需要找到一个特征，这个特征可以预测 $r-1$ 轮后两个部分加密的消息的差分. 如果能够找到一个具有足够高概率的特征，那么原则上，我们就能够恢复轮密钥 $k_r$.

为了构建多轮的特征，我们先尝试找到 一轮的特征.

一轮的特征

我们需要研究 4 个 S 盒，找到存在高概率输出差分的输入差分. 由于 P 盒是线性的，可以直接计算一轮的输入差分. 4 个 S 盒的输入和输出差分可以记为

其中 $\alpha_i$ 是输入到每个 S 盒的值 $A_i$ 之间的差分，$\beta_i$ 是输出值 $S[A_i]$ 之间的差分. 因为 P 盒是固定的，我们可以 确切地预测 差分通过 P 盒发生的变化

其中 $\beta_1\Vert \beta_2\Vert \beta_3 \Vert\beta_4$ 是 P 盒 16-bit 的输入差分. 对于一整轮 $\mathscr{R}$，

表示 CipherFour 一轮的特征.

注意到差分分布表左上角的项是 16，也就是说「输入差分为 0 时，输出差分为 0」发生的概率为 1. 很显然，对于相同的输入，S 盒会有相同的输出，选择所有 4 个 S 盒输入差分都为 0 会得到一个概率为 1 的一轮特征. 但这对密码分析来说没有意义，一个 非平凡 的一轮特征必须最多具有 3 个输入差分为 0 的 S 盒.

我们考虑发生概率为 $\frac{10}{16}$ 的特征

经过 P 盒

这就得到了完整的一轮

在这个基础上再扩展一轮，发生概率为 $(\frac{6}{16})^3$ 的特征

经过 P 盒

假设两个一轮特征相互独立，那么我们就得到了 CipherFour 的一个发生的概率为 $\frac{10}{16}\times (\frac{6}{16})^3=\frac{135}{4096}$ 的二轮特征

注意，上面描述的过程从差分分布表中查找每个 S 盒最高概率的特征. 但是这样找到的特征可能在一轮中是最佳的，但其他密码组件（例子中为 P 盒）可能会让这个特征在多轮中变得不那么理想.

例如，我们考虑输入差分 $(\texttt{0,0,2,0})$，发生概率为 $\frac{6}{16}$ 的一轮差分

由于输入差分等于输出差异，这个特征可以与其自身连接，产生我们想要的任意多轮的特征. 这样的特性称为 迭代特性. 我们有概率为 $(\frac{6}{16})^2$ 的二轮差分

概率为 $(\frac{6}{16})^3$ 的三轮差分

概率为 $(\frac{6}{16})^4$ 的四轮差分

类似前几次攻击，如果攻击者选择输入差分 $(0,0,2,0)$ ，从密文反向计算，根据四轮后部分加密的密文中的差异是否符合预期，得到最后一个子密钥 $k_5$（的某些位）.

这样做的问题是：这个差分发生的概率是 $0.02$，而随机指定的差分发生的概率是 $\frac{1}{16}>0.02$ ，无法从中有效区分出正确的密钥信息. 在下一篇文章中我们会解决这个问题.