差分密码分析-3

续差分密码分析-2

$DifferentialCryptanalysiswithDifferentialDifferential\backslash ;Cryptanalysis\backslash ;with\backslash ;Differential$

$differentpathtosamedestinationdifferent\backslash ;path\backslash ;to\backslash ;same\backslash ;destination$

在我们上面的分析中，计算了每一轮的路径、特征及概率，但对现实使用的密码进行差分分析时，往往不会这样做，因为拿到每一轮的结果过于复杂，往往使用一定工具，如 MILP，来搜索达到可提供优势的差分路径的最大长度。而该搜索过程也不会考虑中间差分值，仅仅考虑该路径的输入差分和输出差分，中间值都可以为未知，例如对$CIPHER-4CIPHER-4$有：

假设我们限制特定的输入输出差分，如都为 $(0,0,2,0)(0,0,2,0)$，那么中间值无论是多少，只要能达到这一点就算做 *优势对*，否则算作 *劣势对*。很自然的想到，经过 4 轮且满足条件：输入差分为$(0,0,2,0)(0,0,2,0)$且输出差分为$(0,0,2,0)(0,0,2,0)$ 的优势对远远不止中间值$betterpathbetter\backslash ;path$所示的那些，我们将优势对构成的路径记为 $AdvpathsAdv\backslash ;paths$：

可以查表$Table6.2Table\backslash ;6.2$可以验证以上$AdvpathsAdv\backslash ;paths$，及查询其特征概率，均为$(\frac{6}{16}{)}^4(\backslash frac\{6\}\{16\})^4$ ,所以将其特征概率相加得到 $4\ast (\frac{6}{16}{)}^4=\frac{81}{1024}4*(\backslash frac\{6\}\{16\})^4=\backslash frac\{81\}\{1024\}$ ，而 $\frac{81}{1024}>\frac{1}{16}\backslash frac\{81\}\{1024\}\; >\; \backslash frac\{1\}\{16\}$，所以，在不考虑路径中间差分值的时候，差分攻击对分析 4 轮 $CIPHER-4CIPHER-4$，来猜测第五轮密钥 $k_{5}k\_5$ 时是有一定优势的。在实践的差分分析中，我们往往也是采用这种办法。

同样的，类似 $Fig\mathrm{.}6.7Fig.\backslash ;6.7$ 的描述方式如下：明显的，忽略了中间差分值，使优势对的数量提升了，这对应差分特征概率的提升。

$FilteringFiltering$

所谓差分密码分析，即识别发生差异的统计特性异常分布，产生比被我们称作噪声的枚举概率更高的猜测概率，从而使我们在猜测时，正确的数据能够从海量的数据中凸显出来，而非被其淹没。

在前面已经介绍了将差分特征概率尽量提高的办法（当然还会有其他更有效的办法），那现在该把关注点放在猜测密钥上。

回顾下前面整个过程：

1. 建$DDTDDT$表并通过密码结果找出最佳差分路径，记录每一轮都满足差分路径的*数据*（明文1：密文1，明文2：密文2 为一对），例子中大概有1296对；
2. 只考虑输入差分和输出差分，而不需要在每一轮都满足差分路径以提高差分特征概率，将同时满足输入差分和输出差分的数据记录下来，例子中大概有 5310 对；
3. 枚举所有密文（全空间）因为寻找的差分路径是在一定概率下成立的，所有需要枚举所有密文，才能利用到差分提供的优势（才能达到使正确密钥凸显出的数据量）

按照这个过程，我们将在最后一轮对每个密文，如果密码设计足够好的话会有 $2^{16}=655362^\{16\}=65536$ 个，考虑对的话就是 $A_{65536}^{2}A^2\_\{65536\}$，这将是很庞大的数据量，且对每一对密文都需要枚举 $2^{16}2^\{16\}$ 个密钥，与构造的区分器进行对比。显然，虽然我们通过忽略中间差分路径取值来提高了特征概率，但在枚举猜密钥的过程中仍然需要很高的复杂度。

所有，需要考虑将密文对筛掉一些，只留下满足条件的密文对，在第四轮之后，得到的差分值为$(0,0,2,0)(0,0,2,0)$，通过查表 $Table6.2Table\backslash ;6.2$ 可得，该差分经过一次 $S[\cdot ]S[·]$ 得到的值可能为 $(0,0,h,0)(0,0,h,0)$ 其中 $h\in \{1,2,9,a\}h\backslash in\{\backslash \{1,2,9,a\backslash \}\}$，而最后一轮没有 $P[\cdot ]P[·]$ ，那么对所有密文，我们需要留下的仅仅是满足条件：

1. 输入差分为$(0,0,2,0)(0,0,2,0)$的明文加密所得；

2. 在 1. 的基础上，将差分的第 0，1，3 半字节位不为全零，且第 2 半字节位不等于 $\{1,2,9,a\}\{\backslash \{1,2,9,a\backslash \}\}$ 的密文对筛掉。

将所以符合上述条件的密文对记录下来，上述例子中大概有 7387 对，也就是说我们仅仅需要对 7387 个密文对，枚举所有可能的最后一轮密钥，这就将数据量降下来很多，同时，找到正确密钥的概率变为 $\frac{5310}{7387}\approx 70\mathrm{\%}\backslash frac\{5310\}\{7387\}\; \backslash approx\; 70\backslash \%$ ,使用未经过筛选的密文对猜密钥，得到正确的概率是 $\frac{5310}{56636}\approx 8\mathrm{\%}\backslash frac\{5310\}\{56636\}\; \backslash approx\; 8\backslash \%$，可见，筛选给猜密钥提供了很大的优势。书中给出的解释：

$KeyRecoveryKey\backslash ;Recovery$

在 4 轮之后，差分传递的特征及其概率如下：

概率为 $\frac{5310}{65536}\approx (\frac{6}{16}{)}^4\approx 0.08\backslash frac\{5310\}\{65536\}\; \backslash approx(\backslash frac\{6\}\{16\})^4\backslash approx0.08$，而筛选之后剩余的对的概率为 $\frac{7387}{65536}\approx 0.11\backslash frac\{7387\}\{65536\}\; \backslash approx0.11$，筛选出的对中可以用来求出正确密钥的对的比率为 $\frac{5310}{7387}\approx 0.7\backslash frac\{5310\}\{7387\}\backslash approx0.7$.那么，给出一个例子，如果我们有总共 $tt$ 个对，筛选后留下的对为 $t\ast 0.11t*0.11$ 个，可能满足条件的对为 $t\ast 0.08t*0.08$ 个。比如 $t=500t=500$ ，则会筛选出 $5555$ 个满足差分特征的对，其中有 $4040$ 个是由正确的最后一轮密钥加密所得，$1515$ 个为无用对。为什么会有一部分无用对留下？我们筛选留下的是明文差分且密文差分都满足条件的对，而在密文位置满足差分特征的对往回推并不一定能够得到区分器末尾（例子第四轮后）的差分值。

1. 我们只能通过对比，确切的猜出不为零的第 2 个半字节位，即 4 个 $bitsbits$，记作目标比特 $targetbitstarget\backslash ;bits$ ，但其他 3 个半字节位由于没有穷尽所有可能的结果，所有无法确定其值。这并未达到分析的目的，甚至连一轮密钥都没有获取到。需要恢复更多 $bitsbits$，需要重复该过程来恢复全 $bitsbits$ 的密钥。

2. 每次只能恢复一轮的密钥，想要恢复更多轮，可能需要更多次的重复上述过程，或者根据密钥编排算法来推所有密钥。（往往是拿到足够多轮次的密钥之后再根据密钥编排算法推）

*差分分析中，获得了一部分密钥 $bitsbits$ 之后，会大大提高恢复其余更多 $bitsbits$ 的难度。