差分密码分析-2

...续差分密码分析-1

$CIPHER-4CIPHER-4$

$CIPHER-4CIPHER-4$已经十分类似我们现在使用的分组密码（见 $AESAES$ 算法 $RijndaelRijndael$）：使用 $rr$ 轮加密，对 $16-bitblock16-bit\backslash ;block$ 操作，所有的 $r+1r+1$ 轮的密钥都随机均匀选取，每一轮包含结构 $S[\cdot ]andP[\cdot ]S[·]\backslash ;and\backslash ;P[·]$ （都可逆）见下图：

其中，每一轮的输入为 $16-bit16-bit$ ，被分为 $4\ast 4-bit4\; *\; 4-bit$ 的四个半字节放入 $4\ast S[\cdot ]4\; *\; S[·]$ 和 $P[\cdot ]P[·]$ 中运算，也就是说 $S[\cdot ]andP[\cdot ]S[·]\backslash ;and\backslash ;P[·]$ 都是在 $\{0,1{\}}^4\to (0,f)\backslash \{0,1\backslash \}^4\backslash ;\backslash rightarrow(0,f)$ 上的置换

#4 轮的 $CIPHER-4CIPHER-4$ 实现了充分的扩散（雪崩），这得益于$P[\cdot ]P[·]$的设计；

#除 $S[\cdot ]S[·]$ 外，其余运算对二进制上的加法 $⨁\backslash bigoplus$ 均是线性的，$P[\cdot ]P[·]$ 运算可以用一个线性的矩阵表示；

下面，考虑对$CIPHER-4CIPHER-4$分析，继承对$CIPHER-3CIPHER-3$的分析方法，寻找前 $r-1r-1$ 轮的差分特征，猜第 $rr$ 轮使用的密钥 $k_{r}k\_r$，由于有 4 个 $S[\cdot ]S[·]$ 所以将差分特征表示为：

还有一个 $P[\cdot ]P[·]$ 作用在 $S[\cdot ]S[·]$ 之后，而 $P[\cdot ]P[·]$ 不会影响差分值，只会影响其在下一轮出现的位置， $P[\cdot ]P[·]$的作用是将差分传播到尽可能多的 $S[\cdot ]S[·]$ 中，将 $P[\cdot ]P[·]$过程表示为：

所以，${\beta }_1\mathrm{\mid }\mathrm{\mid }{\beta }_2\mathrm{\mid }\mathrm{\mid }{\beta }_3\mathrm{\mid }\mathrm{\mid }{\beta }_4\backslash beta\_1||\backslash beta\_2||\backslash beta\_3||\backslash beta\_4$ 就表示输入差分经 $S[\cdot ]S[·]$ 之后的输出差分，${\gamma }_1\mathrm{\mid }\mathrm{\mid }{\gamma }_2\mathrm{\mid }\mathrm{\mid }{\gamma }_3\mathrm{\mid }\mathrm{\mid }{\gamma }_4\backslash gamma\_1||\backslash gamma\_2||\backslash gamma\_3||\backslash gamma\_4$ 表示输出差分经 $P[\cdot ]P[·]$之后该轮最后的输出差分，所以一轮的差分总体表示为：

通过表$Table6.2Table\backslash ;6.2$ 可以发现，如果输入 $S[\cdot ]S[·]$ 的差分为 0，则输出差分也为 0 ，所以对于 $16-bitblock16-bit\backslash ;block$，可以以没半个字节为单位，构造只在一位（一个 $S[\cdot ]S[·]$ 输入差分）为非零值的数据。当然，这在分析上是允许的，但变成了*选择明文攻击，因为明文是我们自己构造的。在考虑$S[\cdot ]S[·]$的活跃性时，相当于构造只有一个$S[\cdot ]S[·]$活跃的轮。构造的输入差分例如$(0,0,1,0)(0,0,1,0)$，每一个位置进入一个$S[\cdot ]S[·]$，那么至少在第一轮只有一个$S[\cdot ]S[·]$的输出会存在差分。

再考虑到前面对$CIPHER-1,CIPHER-2CIPHER-1,CIPHER-2$分析的时候，得到一个$S[\cdot ]S[·]$ 存在最大的差分特征 $f\stackrel{S[\cdot ]}{}bf\backslash ;\backslash stackrel\{S[·]\}\{\backslash rightarrow\}\backslash ;b$ ，概率为$\frac{10}{16}\backslash frac\{10\}\{16\}$，所以将输入差分令为$(0,0,0,f)(0,0,0,f)$，那么对第一轮，就只有第四个$S[\cdot ]S[·]$ 存在差分，描述经过一轮差分的传递：

但是，一个好的$P[\cdot ]P[·]$置换，会将差分传递到下一轮尽量多的$S[\cdot ]S[·]$，比如采用 $MDSMDS$ 矩阵的$P[\cdot ]P[·]$，见$Matrix\mathrm{\_}BranchandMDSMatrix\backslash \_Branch\backslash ;and\backslash ;MDS$。即使不考虑$P[\cdot ]P[·]$有足够好的扩散性能，其也可以将差分特征扩散，比如：

所以上面整个过程描述下来就是：

因为这是整个一轮，所以其整个过程的概率就是$\frac{10}{16}\backslash frac\{10\}\{16\}$.

继续考虑第二轮，通过表 $Table6.2Table\backslash ;6.2$ 可以看到，$(1,1,0,1)(1,1,0,1)$ 存在差分的三位再经过一次 $S[\cdot ]S[·]$ 的输出差分特征以概率$(\frac{6}{16}{)}^3(\backslash frac\{6\}\{16\})^3$存在（*因为每个输入差分1到输出差分2的特征概率都是$\frac{6}{16}\backslash frac\{6\}\{16\}$，所以将其概率相乘才是总体输出差分为$(2,2,0,2)(2,2,0,2)$的概率）且差分特征描述为：

经过一次 $P[\cdot ]P[·]$ 置换，以概率 1 获得差分$(0,0,d,0)(0,0,d,0)$：

所以，两轮的差分传递描述为：

计算总概率，第一轮概率是 $\frac{10}{16}\backslash frac\{10\}\{16\}$，第二轮概率是$(\frac{6}{16}{)}^3(\backslash frac\{6\}\{16\})^3$，乘在一起得到 $\frac{10}{16}\ast (\frac{6}{16}{)}^3=\frac{135}{4096}\backslash frac\{10\}\{16\}\; *\; (\backslash frac\{6\}\{16\})^3=\backslash frac\{135\}\{4096\}$，也就意味着我们在枚举密钥时，已经失去了对于穷举的优势。当然，对于这个例子可能不十分合适去解释，因为其用来 4 个 $S[\cdot ]S[·]$ ，那就假设每个$S[\cdot ]S[·]$ 前面使用的都是相同密钥，密钥是 4 位 2 进制，也就共有 $2^4=162^4=16$种可能。很显然 $\frac{135}{4096}\backslash frac\{135\}\{4096\}$ 要小于 $\frac{1}{16}\backslash frac\{1\}\{16\}$ ，所以对两轮$CIPHER-4CIPHER-4$的差分分析失去了消除噪声的优势。

考虑一下原因，很自然的想到，$P[\cdot ]P[·]$ 是影响该结构差分传播的一个大问题，在第 2 轮时由于差分特征被 $P[\cdot ]P[·]$ 扩散开，所有就产生了三条路径，而计算时需要将三条路径的概率相乘，也就造成了经过两轮后差分特征概率变得如此低。同时，在第一轮输入开始就以我们预像的最大差分概率来构造差分，并将其注入明文来构造明文对，这种方法可能并不会给我们带来最佳差分路径（概率最高），因为其在前面 $CIPHER-1,2,3CIPHER-1,2,3$ 中使用的差分特征仅仅对 $S[\cdot ]S[·]$ 而这里有 $P[\cdot ]P[·]$，所有我们应该将 $S[\cdot ]andP[\cdot ]S[·]\backslash ;and\backslash ;P[·]$ 一起考虑。给出一个例子：

可能这是将差分扩散性作为优先级考虑的一种路径，但这条路径的差分特征概率确实比上面一条更高，通过表$Table6.2Table\backslash ;6.2$发现，差分特征概率为$\frac{6}{16}\backslash frac\{6\}\{16\}$,为一轮的差分特征概率，同时为每一轮的差分特征概率。所有经过 4 轮之后，得到概率为 $(\frac{6}{16}{)}^4(\backslash frac\{6\}\{16\})^4$ 的差分特征路径：

以上过程也可以通过寻找满足要求的明密文对来描述，如果要求选择的明密文对对满足在每一轮差分都为一定值,如上面的 $(0,0,2,0)(0,0,2,0)$ ，则在随机密钥的情况下（其实对于我们举例的密码，密钥并没有影响到差分，但为保证其随机性，还是随机选择密钥，选择 5 个种子密钥，没有经过密钥编排，用作 4 轮，每一轮使用一个 4 位 2 进制作为密钥参与密码运算），统计对数并计算平均值，然后与总可能差分数量 $2^{1}6=655362^16=65536$ 作比，可以得到与计算特征概率几乎相同的结果：

来比较以下，

• $betterpathbetter\backslash ;path$ 的差分特征概率：每一轮的都是 $\frac{6}{16}\backslash frac\{6\}\{16\}$ 所有4轮之后概率为 $(\frac{6}{16}{)}^4(\backslash frac\{6\}\{16\})^4$
• $inheritedpathinherited\backslash ;path$ 的差分特征概率：$\frac{10}{16}\ast (\frac{6}{10}{)}^3\ast \frac{6}{10}\ast \frac{6}{10}\backslash frac\{10\}\{16\}*(\backslash frac\{6\}\{10\})^3*\backslash frac\{6\}\{10\}*\backslash frac\{6\}\{10\}$

由上面的对比可以看到，$betterpathbetter\backslash ;path$ 拥有更大的差分特征概率。那么考虑以下，在找到 4 轮差分特征之后，是否有相对于穷举的优势来猜第五轮的密钥$k_{5}k\_5$，很明显，，也就是噪声大于我们猜测的概率。

这是否意味着差分分析的失败？？（假设上面的$betterpathbetter\backslash ;path$ 就是最好的差分特征传播路径）在一定轮数之后就失去了其统计上的意义？？可能差分确实在传递到一定论数之后确实会因为特征概率太小而被噪声淹没，但似乎我们漏掉了一些使概率放大的办法...

接差分密码分析-3