对称密码攻击之差分分析

概述

差分分析是一种选择明文攻击，通过分析明文对中的差异对结果密文的差分的影响，这些差分是用来给可能的密钥进行分配概率，确定最有可能的密钥

差分分析是目前已知的攻击迭代密码最有效的方法之一，差分指的是明文对的异或

原理

基本思想

• 基本思想：试图构造$(x,x')$，使得最后一层的输入差分$\Delta y(r-1)$可预测，然后利用这个差分和最后一层的输出$(y,y')$来分析密钥

简单分析一下DES的结构，每轮有轮密钥加的步骤，轮密钥加需要先对分组进行扩展，将32 bit的信息位扩展成48 bit，然后与48 bit的轮密钥进行异或，最后输入S盒与P盒中

DES输入与输出的关系主要有四个部分，轮密钥加，扩展，S盒，P盒

对于密钥加的结果的差分为$(x\oplus k)\oplus (x^*\oplus k)=x\oplus x^*$，从而密钥加不会影响差分的传播

扩展变换E的差分为$E(x\oplus k)\oplus E(x^*\oplus k)=E(x \oplus k \oplus x^* \oplus k)=E(x\oplus x^*)$，从而扩展变换也不会影响差分的传播

P盒差分为$P(y)\oplus P(y*) = P(y\oplus y*)$

S盒差分为$S(x) \oplus S(x^*)=y\oplus y^*$，结果不确定，不仅与输入差分有关，还与输入$x$有关

分析可知，DES中除了S盒以外，其他组件的差分传播都是确定的，只有S盒使得差分的传播存在不确定性，因此DES的差分分析本质上是对S盒的差分分析，从而恢复部分或全部密钥

因此，为了恢复进入第i个S盒的密钥，需要选择明文对$(x,x')$，使得其进入S盒的输入差分不为零，然后获得该轮函数的输出差分$\Delta=F(x\oplus k)\oplus F(x^*\oplus k)$，从而建立第i个S盒的差分分析模型

DES可以使用差分分析的原因在于，其S盒的差分分布具有不均匀性，意味着对于相同的输入差分，不同的输入会对应不同的输出差分，也就是输出差分和输入与输入差分均有关

实现

记输入差分为$α$，输出差分为$\beta$，定义

$$ IN_s(α,\beta)=\{x\in\{0,1\}^8 \ | \ \beta=S(x\oplus α) \oplus S(x)\} $$

记S盒的差分分布表$N_s$，其表示$IN_s(α,\beta)$的个数

$$ N_s(α,\beta)= \# IN_s(α,\beta) $$

因此，通过求$IN_s(α,\beta)$，就可以知道经过密钥加后的输入$z$的取值范围$A$，记密钥$k$的取值范围为

$$ \{k \ | \ k=z\oplus x ,z \in A\} $$

这个集合一般是全体8 bit串的真子集，从而可以排除一部分不可能的密钥

选择多个$α$和$x$，重复上述步骤若干次，然后对得到的这些密钥集合取交集，可以将密钥$k$缩小至若干个甚至一个，从而还原出密钥

需要注意的是：如果只选择多个不同的输入$x$，但是不改变输入差分$α$，最后得到的是两个候选的密钥选项，因为$k$和$k\oplus α$都是满足输入输出差分

因为S盒的设计是完全公开的，所以任何时候都可以跑差分分析

例子

首先，DES的S盒输入为6 bit串，输出为4 bit串，对于给定的输入差分$α$，其一共对应着64种不同的输入

假设分析的是第一个S盒$S_1$，输入差分为$\Delta=110100$，则可能输入有

$$ \Delta = \{(000000,110100),(000001,110100),...,(111111,110100)\} $$

共有64种不同的组合

而对于这些输入，S盒输出4 bit，一共有16种可能$0000,0001,...,1111$

现将上述$\Delta$中每一对的两个值分别作为S盒的输入，然后得到两个输出，例如$S_1(000000)=1110$，$S_1(110100)=1001$，从而得到输出差分为$1110\oplus 1001 = 0111$，对$\Delta$中的每一个对都这么处理，并统计每个差分出现的次数，然后可以得到下列输出差分计数表和分布表

通过上述表格可以发现，S盒的差分计数表和分布表是不均匀的，计数表的计数总和为64，如果是均匀的话，则每一格应当为4，但是结果显然不是，因此可以利用这个特性分析S盒

根据上述表格与之前的分析，假设密钥为k，S盒输入$x =z\oplus k =000001$，输入差分$α=110100$，可以计算得到$S_1(x)=S_1(z\oplus k)=S_1(000001\oplus k)=0001$，$S_1(z\oplus α \oplus k)=S_1(000001 \oplus 110100 \oplus k)=1100$，$\beta=0001 \oplus 1100 = 1101$，查找上表可得到输出差分为1101的对应的可能的输入$x$为

$$ x\in\{000110,010000,010110,011100,100010,100100,101000,110010\} $$

从而对应的输入使用的密钥为$k=x\oplus z$，如下

$$ k\in\{000111,010001,010111,011101,100011,100101,101001,110011\} $$

如果选取$x=100001$，固定$α$不变，可以将密钥的范围进一步缩小到如下集合

$$ k\in\{000011,000000,010111,1101111,110100,100011\} $$

继续固定$α$，选择不同的$x$，最后可以将密钥确定为$k=100011$

DES一共有8个S盒，而每个S盒都有64种可能的差分，因此需要制作64*8=512张差分分布表，现代计算机可以做到，因此只需要遍历已经知道的密钥的取值集合，使用枚举的密钥计算，然后判断输出差分是否相同

代码实现

以后有时间再补吧