差分密码分析

Differential  Cryptanalysis  to  ToyCipherDifferential\;Cryptanalysis\;to\;ToyCipher

CIPHER−1CIPHER-1

以一个toyciphertoycipher为例：CIPHER−1CIPHER-1，其中，S[⋅]S[·] 表示一个公开的 S−BoxS-Box 置换（可逆)

在已知明文 m0  m1m_{0} \; m_{1} ，密文 c0  c1c_{0}\;c_{1} 的情况下（已知明文攻击），加密过程如下：

(已知：m0  m1  c0  c1;m_{0} \; m_{1}\; c_{0}\;c_{1} ; 未知：k0  k1  u  v)k_{0}\;k_{1}\;u\;v)

由于两次加密使用的是相同的密钥 k0k_{0}和 k1k_{1} ，所以对明文以密码最常用操作( ⨁\bigoplus )做差分得到：

即，明文m0  m1m_{0} \; m_{1}差分 == 中间状态 u0,u1u_{0}, u_{1} 的差分，消去了密钥 k0k_{0} 的影响；

所以，跳过 k0k_{0} 的影响，枚举 k1k_{1} 的候选值，记 tt，当t t 满足

S−1[t⨁c0]⨁S−1[t⨁c0]==m0⨁m1\textcolor{red}{S^{-1} [ t \bigoplus c_{0}] \bigoplus S^{-1} [ t \bigoplus c_{0}] == m_{0} \bigoplus m_{1}}

时，记 11 次有效的 tt 计数，当 tt 计数足够多时，则认为 tt 有很大可能就是k1k_{1} ，只需验证即可。

Conclusion‾  P1:Conclusion\underline{ }\;P_1:

  1. 即使中间数据未知，仍然可以通过寻找已知数据的差异来断定中间数据的差异；
  2. 差分分析的一种方法(init) ，通过寻找确定的一部分中间状态数据，穷举另一部分未知数据来恢复密钥。

下面是一个具体的分析的例子:

简单解释一下以上例子的过程：（已知明文攻击）

  1. 选择两对明密文，根据上面推出的公式：中间值差分(u0⨁u1)==(u_{0}\bigoplus u_1)== 明文差分 (m0⨁m1)(m_{0} \bigoplus m_{1})，计算出u0⨁u1u_{0} \bigoplus u_{1}的值;

  2. 计算出S[⋅]S[·]的逆S−1[⋅]=R[⋅]S^{-1}[·]=R[·]，用来计算核心推导式;

  3. 穷举所有的 k1=tk_{1}= t,根据式：S−1[t⨁c0]⨁S−1[t⨁c0]S^{-1} [ t \bigoplus c_{0}] \bigoplus S^{-1} [ t \bigoplus c_{0}]计算出中间值差分;

  4. 将3.中的结果与2.中的结果匹配，对可能使等式S−1[t⨁c0]⨁S−1[t⨁c0]==m0⨁m1S^{-1} [ t \bigoplus c_{0}] \bigoplus S^{-1} [ t \bigoplus c_{0}] == m_{0} \bigoplus m_{1}成立的t计数（或存到一个集合中）需要注意使成立的t值可能不唯一，这就涉及到差分概率，后面再说;

  5. 为了找出唯一的t=k1t=k_{1}，需要更多的明密文对来重复上述1.2.3.4.过程;

  6. 将多个明密文对产生的可能t=k1t=k_{1}结果取交集，直到得到最后的唯一的结果，即可以断定其为正确的k1k_{1}



CIPHER−2CIPHER-2

下面考虑一个更复杂的例子，假设Cipher−2Cipher-2有两个SS盒及33个密钥：

明显，在以上例子中，虽然有关系 m0⨁m1m_{0} \bigoplus m_{1}，但无法通过S[⋅]S[·]的逆找到中间值ww和vv，因为再往前传递数据的过程中，S[⋅]S[·]会消去已有的差分关系（当然，不是完全消去）

那么，就需要更进一步的考虑SS盒对该差分传递的影响

下面做一个小测试，考虑两个相同SS盒的输出差分: 取i,j分别为进入两个S盒的数据，且i是j的补，即j=i⨁fj=i \bigoplus f，则有下表$

#小知识：二进制数据ii的补==i⨁F16==i⨁1⃗==i\bigoplus F_{16} ==i\bigoplus \vec{1}

按照CIPHER−1CIPHER-1的办法无法获取中间值vv和ww，因为经过了非线性的SS盒，⨁\bigoplus 的差分无法被传递下去； 所以选定明文 ii，和通过明文 ii 可以推出的明文 jj ，并将其分别进入 SS 盒，拿到其输出 SS 盒的差分，建立下表：

通过上面发现，在第五列，dd 出现的频率更高，下面给出以上由 ii 到 jj 到 S[i]⨁S[j]S[i] \bigoplus S[j] 的推导过程：

i(i.e.message  or  plaintext)→i⨁F=S[i]⨁S[j]i(i.e. message\;or\;plaintext) \rightarrow i \bigoplus F = S[i] \bigoplus S[j]

所以，我们只需要有一个明文 ii 即可；

根据对 CIPHER−1CIPHER-1 的攻击可以知道，m0⨁m1==u0⨁u1==Fm_{0}\bigoplus m_{1} == u_{0} \bigoplus u_{1} == F,所以有：*当两个异或等于 FF 的值分别进入该 SS 盒，会有1016\frac{10}{16}的概率得到输出差分 d d ；

同时，通过猜测k2k_{2}可以得到 ww 位置的差分，而 ww 位置的差分又等于 vv 位置的差分。

所以得到结论：

通过选择两个输入差分为 F 的明文产生密文（并不是选择明文攻击），猜测 k2k_{2} 从反向在中间进行对比，如果差分数据十分随机，则猜测的 k2k_{2} 不对，如果猜测 k2k_{2} 使得在中间 v0⨁v1v_{0}\bigoplus v_{1} 为 dd，则很大可能猜测的 k2k_{2} 正确。

那么更进一步，对任何一对"选择"的明密文，猜测 k2k_{2} ，并将所有 k2k_{2} 的猜测记在hashhash表中，如果 k2k_{2} 使得中间的差分 v0⨁v1=v_{0}\bigoplus v_{1} =差分分布表中频率出现最高的数据（如 Table  6.1Table\;6.1 的 dd），则将该hashhash表中对于的 k2k_{2} 的位置计数 +1+1.(*逆向推 k2k_{2} 的过程中，正确的 k2k_{2} 将会使中间值差分出现的频率远高于其他值出现的频率，如上图 v0⨁v1=dv_{0} \bigoplus v_{1}=d 概率为 1016\frac{10}{16},而其他为116\frac{1}{16}.

以上的寻找输入差分 dind_{in} 及其经过两个 S−BoxS-Box 之后的输出差分 doutd_{out} 的值可以建一个差分表 DDT\textcolor{red}{DDT} ,如下：

从下图可以看出，当输入差分为ff时，输出差分为dd出现的频率最高次数为10，所以选择差分 ff 从 plaintextplaintext 注入，获得一条差分概率最大的路径，概率为1016\frac{10}{16},路径为f→df\rightarrow d.

对 CIPHER−2CIPHER-2 的分析让我们发现了 S[⋅]S[·] 的一些规律，比如：

  • 如果两对差分输入位上均不同，如 0001  and  11100001\;and\;1110，观察上表的 1  and  e1\;and\;e ，输出差分在各位也均不同；
  • 在所有位位置不同的十对输入将产生除了第二个最低有效位位置之外的所有不同的输出对；
  • and  so  on  and  so  forthand\;so\;on\;and\;so\;forth

那么，如果一对输入输出差分(α,β)(\alpha,\beta)，即输入差分 α\alpha 通过 S[⋅]S[·] 可以得到输出差分 β\beta ,则称该过程为通过操作 S[⋅]S[·] 的差分特征 (differential)  characteristic  across  the  operation  S[⋅] (differential) \;characteristic\;across\;the\;operation\;S[⋅] 记作α  S[⋅]  β\alpha\;\stackrel{S[·]}{\rightarrow}\;\beta ,一个特征成立就有与其对应的概率如 f  S[⋅]  bf\;\stackrel{S[·]}{\rightarrow}\;b 的概率为1016\frac{10}{16}.

Differential  Cryptanalysis  using  CharacteristicDifferential\;Cryptanalysis\;using\;Characteristic

CIPHER−3CIPHER-3

有了上面的规律，可以考虑一个更加复杂的ToyCipherToyCipher：CIPGERTHREECIPGERTHREE在CIPHER−2CIPHER-2的基础上，又多加了一个S[⋅]S[·]及一个密钥k3k_3

有了对CIPHER−2CIPHER-2的分析方法，对CIPHER−3CIPHER-3分析就容易理解多了：如果考虑通过一个S[⋅]S[·]，则给定差分 ff 会得到差分 dd 的概率时 1016\frac{10}{16}；那么，考虑差分继续往后传播，到第二个S[⋅]S[·]，通过查表 Table6.2Table 6.2 可以得知，概率最高的是特征 d  S[⋅]  cd\;\stackrel{S[·]}{\rightarrow}\;c，概率为 616\frac{6}{16}，也就是说，如果我们希望能够通过"猜密钥"的方式（或者是枚举）得到密钥 k3k_3 ，就需要经过两个 S[⋅]S[·] ，而带来的影响是，差分概率降低（*我们选取的是差分概率最高的一条特征路径）。很自然的，我们把通过两个S[⋅]S[·]的差分特征概率乘起来 1016∗616=1564\frac{10}{16} * \frac{6}{16}=\frac{15}{64}，也就是说，我们猜出正确的k3k_3的概率是1564\frac{15}{64},但这也是很大的降低了噪声对我们猜测密钥的影响，因为随机猜测密钥的。

接差分密码分析-2...