差分分析学习（三）

在上一篇文章的最后，我们得到了一个四轮差分

(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})

但是它的概率太小了，无法从中有效区分出正确的密钥信息. 事实上，攻击者根本就不知道经过每一轮之后的差分变成了什么. 攻击者实际上只需要关心

(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})

这种结构称为 差分（differential）.

需要提一下，英文中用 difference 表示差分值，也就是我们前面讲的两个值的异或；用 differential 表示差分对，也就是由一个差分值传播到另一个差分值. 在中文中往往都称为「差分」了，一般根据上下文也不会引起误解.

差分可以包含很多个以相同开始和结束的特征. 在我们的例子中，这个差分除了包括

(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})

还包括

\begin{align} &(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,0,2})\xrightarrow{\mathscr{R}}(\texttt{0,0,0,1})\xrightarrow{\mathscr{R}}(\texttt{0,0,1,0})\xrightarrow{\mathscr{R}} (\texttt{0,0,2,0}),\\ &(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,0,2})\xrightarrow{\mathscr{R}}(\texttt{0,0,1,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}} (\texttt{0,0,2,0}), \text{and}\\ &(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}(\texttt{0,0,0,2})\xrightarrow{\mathscr{R}}(\texttt{0,0,1,0})\xrightarrow{\mathscr{R}} (\texttt{0,0,2,0}). \end{align}

我们不知道 $(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})$ 成立的确切的概率是多少，但是我们知道这个差分中包含四个特征，并且每个特征成立的概率是 $(\frac{6}{16})^4$ . 因此，这个差分成立的概率应该大约是（或者大于） $4\times (\frac{6}{16})^4=\frac{81}{1024}$ .

过滤（Filtering）

差分分析的基本目的，是识别「差分发生的异常统计分布」. 这种「异常」是我们试图检测的信号，而那些不遵循我们预期特征/差分的明文-密文对，会掩盖这种信号. 因此我们希望尽可能滴消除这些「错误对」（不遵循特征的对），让检测信号变得更容易.

通常指查看密文就可以识别错误对. 应该把这些错误对丢弃掉，因为它们不会对密钥恢复提供有用的信息.

我们继续用 CipherFour 来说明「过滤」技术. 现在仔细研究一下，当明文对是正确的对时，差分如何通过第五轮（也就是最后一轮）传播. 在第五轮我们有

(\texttt{0,0,2,0})\xrightarrow{S}(\texttt{0,0,}h,\texttt{0})

通过查询差分分布表中输入差分为 2 的行，我们知道其中 $h$ 的取值为 $\{\texttt{1,2,9,a}\}$ .

因为在最后一轮没有使用 P 盒，这四个值一定会在第五轮之后成为密文的一部分. 因此对于每一个明文对，攻击者可以检查对应的密文对，确定这个密文对是错误对 / 可能是正确对. 在我们的例子中，密文差分有 12 个 bits 必须取 0，其余 4 个 bit 只能取 4 个特定值. 一个好的过滤技术对差分攻击的成功是很重要的.

恢复密钥信息

现在，我们将所有部分放在一起，构建对 CipherFour 的密钥恢复攻击. 在我们的攻击中，我们只会恢复最后一轮用到的密钥 $k_5$ 的 4 个 bits. 这些 bits 称为 目标密钥比特.

穷举密钥的实验结果告诉我们，之前用到的四轮差分 $(\texttt{0,0,2,0})\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}?\xrightarrow{\mathscr{R}}(\texttt{0,0,2,0})$ 有 $\frac{5310}{65536}\approx 0.08$ 的概率成立，而一个对在过滤中通过的概率是 $\frac{7387}{65536}\approx 0.11$ .

假设攻击者收到 $t$ 个满足输入差分 $(\texttt{0,0,2,0})$ 的明文对的加密结果. 那么仅仅根据密文差分，他就可以过滤掉肯定错误的对. 如果明文是随机选择的，那么预计有 $t\times \frac{7387}{65536}\approx t\times 0.11$ 个对会通过过滤，其中肯定会有 $t\times 0.08$ 个满足差分的对.

现在我们知道，当我们穷举目标密钥比特的每个值的时候，正确的值会为满足差分（differential）的对产生预期的差分（difference）. 这意味着满足差分的对，总是会指示出目标比特的正确值. 因此，在攻击中，如果有 $t$ 对明文，目标比特的正确值会被指示 $t\times 0.08$ 次.

我们假设，错误的目标比特以 $\frac{1}{16}$ 的概率给出期望的差分. 那些不满足差分特性但是仍然通过过滤的对，会指示一个（不正确的）目标比特. 对于选定的 $t$ 对明文，我们预计大约会指示 $t\times(0.11-0.08)=t\times 0.03$ 个不正确的目标比特值. 通过使用足够多的消息，我们期望目标比特的正确值会是被指示最多的值. 例如，如果 $t=500$ ，那么我们认为正确的值应该被指示 40 次，而错误的值应该被指示 15 次.

我们的攻击从 CipherFour 的五轮版本中恢复了 4 个 bits. 类似地，我们可以使用其他差分来做类似的差分攻击. 恢复第一轮的密钥也是可能的. 一旦攻击者恢复了第一轮或最后一轮子密钥的全部 16 个 bits，就可以剥离一轮密码，并继续攻击较弱的版本. 在差分攻击中，最困难的部分是找到 任何一个 密钥位，一旦找到一些密钥位，恢复其余部分就很容易了.

至此，我们应该理解了差分分析的基本思想.