前言

汇报文章：

• Differential-Linear Cryptanalysis
  在这篇论文中，Langford和Hellman首次提出将差分分析和线性分析结合的思想，并且给出了DES的8轮差分-线性攻击的结构与相关复杂度分析。
• Enhancing Differential-Linear Cryptanalysis
  基于上述文章的差分-线性攻击的思想，Biham等人对其进行了改进：选择不为1的差分特征。

8轮DES攻击

• 整体思想

通过差分保证线性逼近式中需要的bit不变，应用线性攻击的方法恢复最后一轮的个别子密钥。

• 整体结构

  • 第1轮：明文对的构造。

  • 第2-4轮：差分路径。

  • 第5-7轮：线性路径。

  • 第8轮：密钥恢复。
    
    

  • 明文输入阶段：

    • 整体结构：
      
      我们需要得到满足第2轮的差分输入的明文对。
    • 明文对构造：对于一个结构，遍历$L_0[9,17,23,31]$与$R_0[2,3]$这6个bit位置，同一个结构其他bit位置相同。在第一轮的F函数中，只有S1的输入有差分，所以只有S1的输出值可能不同，S1的输出bit位置经过P置换的位置为[9,17,23,31]从而决定了$R_1$，所以对于每一个明文，在$R_0[2,3]$选取不同的值时，都可以通过$L_0[9,17,23,31]$来调节$R_1$来和选定的明文 $\Delta$$R_1=0$.
    • 完成上述操作就需要猜测第一轮中S1中的6bit密钥。
    • 数量分析：对于一个结构，6bit遍历，产生$2^6=64$个明文，对于每一个明文，都能找到3个不同的明文满足第二轮差分输入，但是存在相互重复的情况，所以有64*3/1=96对。

  • 差分阶段：
    

    • 差分输入对：输入对的$L_1$只在bit位置2或3有异或，输入对的$R^1$完全相同（所以对于一个第二轮的输入，与之匹配的输入对共有3种）
    • 第二轮输出情况：$L^2$=$R^1$,故$L^2$无异或。进入F函数的输入完全相同，故F函数的输出无异或（完全相同），经过与$L^1$进行异或后，$R_2$只在bit位置2或3有异或。
    • 第三轮输出情况：$L^3$=$R^2$,故$L_3$只在bit位置2或3有异或。进入F函数中的输入只在bit位置2或3有差分，故F函数中S2-S8输入相同，仅有S1输入有异或，S1的输出4bit经过P置换操作后的位置为(3,1)/(5,1)/(6,3)/(8,3)，对应bit位置为：9/17/23/31，后与之进行异或的$L_2$无差分，故$R_3$只有bit位置9/17/23/31可能有差分。
      
    • 第四轮输出情况：$L^4$=$R^3$,故$L_4$只在bit位置9/7/23/31有异或。进入F函数的$R_3$，首先，经过E扩展后，S2/S3/S4/S5/S6/S8这6个S盒的输入都可能有差分，所以这6个S盒的输出都可能有差分，
      
      S1和S7输出的8bit无差分，对应坐标为：(3,1)(5,1)(6,3)(8,3)和(8,4)(3,4)(6,2)(2,3)，对应输出位置：9/17/23/31/32/12/22/7无差分。
      
      经过4轮迭代后，选取的输入差分以概率1在$L_4$[3,8,14,25]和$R_4$[17]这5个bit位置无差分。

  • 线性阶段

    • 使用的线性逼近式：
      
      成立的概率：p=0.695。
      因为$K_1[26]$和$K_3[26]$未知，当他们的异或加一定为0或1（在猜测密钥固定的情况下）。所以我们给出以下式子：
      
      其概率：p=0.695或0.305（取决于$K_1[26]$和$K_3[26]$=0或1）.
    • 攻击思想：对于输入的明文对，都有上面的线性逼近式成立，我们将这对明文的线性逼近式异或加，就得到：
      $\Delta$(($L_0[3,8,14,25]$$⨁$$R_0[17]$)$⨁$($L_3[3,8,14,25]$$⨁$$R_3[17]$))=0
      $\Delta$($L_0[3,8,14,25]$$⨁$$R_0[17]$)以概率1为0，
      故：$\Delta$($L_3[3,8,14,25]$$⨁$$R_3[17]$))=0成立的概率为：$p^2+q^2$=0.576（$q=1-p$）

  • 密钥恢复阶段（上述分析的角标只针对3轮线性分析）

    • 整体结构
      
    • 已知$\Delta$($L_7[3,8,14,25]$$⨁$$R_7[17]$))=0成立的概率为：$p^2+q^2$=0.576（$q=1-p$），
      $R_7[3,8,14,25]=L_8[3,8,14,25]$（通过明文可知），$L_7[17]$我们通过$R_8[17]$和F函数的输出异或得出：
      $L_7[17]=Output(F[17])⨁R_8[17]$，在F中S1的output的第二bit经过P置换后的位置为17，所以我们需要$K_8{,}_1$ 的6bit密钥值即可的到$L_7[17]$的值。

  • 复杂度分析

    • 猜测密钥：$K_1{,}_1$和$K_8{,}_1$共 6bit。
    • 所需明文：根据线性攻击的数据复杂度估计规则，所需明文对数的估计式为：$8/(r-0.5{)}^2$，其中$r=0.576$，故所需明文对数约为1400对。我们需要1400/96种结构，每个结构产生64个明文，故对于8轮DES进行差分-线性攻击，需要的明文量为$1400\ast 64/96=900$。
    • 时间复杂度：选取明文量为$768=2^{9.58}$，共猜测10bit密钥值，$2^{10}$种，每次进行2个S盒的运算，故时间复杂度为$2^{9.58}\ast 2^{10}\ast 2/64=2^{14.58}$。

  • 具体的攻击流程：

  1. 设立10bit密钥（$K_1{,}_1{K}_8{,}_1$）的寄存器（两个子秘钥有2bit是重复），共$1024$种密钥情况；
  2. 对于每种$K_1{,}_1$密钥情况，通过上述结构构造方式，生成900个明文/1400个明文对，满足第二轮的差分输入；
  3. 计算明文输入对应的密文；
  4. 猜测最后一轮子秘钥$K_8{,}_1$，得到$\Delta$($L_3[3,8,14,25]$$⨁$$R_3[17]$))的值，若为0，这将此10bit密钥对应计数器+1；
  5. 猜测计数器中的最大值对应的密钥值为10bit正确的子秘钥。

改进8轮DES攻击

• 整体思想：
  引入有概率的差分路径.

• 差分路径：
  

  • 第1轮：
    在第1轮中输入差分为00 80 82 00 60 00 00 00，F函数的输入为60 00 00 00，我们需要F函数的输出差分为00 80 82 00才能满足第2轮的输入差分，所以F(60 00 00 00)=00 80 82 00的概率为14/64。
  • 第2轮：
    第2轮的F输入无差分，输出无差分。整体输出差分为：00 00 00 00 60 00 00 00。
  • 第3轮：
    F函数的输入差分为：60 00 00 00，只有S1输入有2bit差分，故只有S1的输出的4bit有差分，经过P置换后到[8,17,23,31]这4个bit位置，这4个bit位置分别代表了对应位置异或值为0或1两种可能，我们将其规范表达出来：$F(60000000)=00W0XY0Z$，其中$W\in$ {0,8}，$X\in$ {0,8}，$Y\in$ {0,2}，$Z\in$ {0,2}，所以第3轮的输出差分为：60 00 00 00 00 W0 XY 0Z
  • 第4轮：
    根据基础差分-线性中对于F函数输出的分析，经过E扩展、S盒、P置换后，我们可以确定的是，S1和S7的输出经过P置换后的bit位置：[9,17,23,31,32,12,22,7]无差分，对于[17]，它确定了?? ?? M? ??中M的范围$0,1,2,3,4,5,6,7$，不可能为8，因为最高位的位置为[17]=0。

• 线性路径：
  
  我们线性逼近式的输入端掩码bit位置为$L[3,8,17]$和$R[17]$，根据上述差分路径的输出：00 W0 XY 0Z ?? ?? M? ??，线性掩码bit位置对应的差分值都为0（p=14/64）

• 整体概率计算：

  • 线性
  • **线性逼近式的概率：**使用堆积引理计算
    $p=-20/64$,$1/2+q=1/2+2(-20/64{)}^2\approx 1/2+0.195$
  • 经过差分路径后的输出差分满足线性线性逼近式所需bit为0的概率：
    包括满足差分特征的对和不满足差分特征的对。（差分路径概率记为$1/2+p^{\prime }=1/2+14/64$）
    满足差分特征的对，所需bit异或值必为0，$p_1=p^{\prime }=14/64$
    不满足差分特征的对，在我们所需要的bit位置（$L[3,8,17]$和$R[17]$）异或值也可能为0，将这一部分的概率估计为$p_2=(1-p^{\prime })/2$
    所以总体满足线性逼近式中所需bit异或为0的概率为$q=p_1+p_2=1/2+p^{\prime }/2=1/2+0.109$ 。
  • 整体概率使用堆积引理：两次线性逼近式成立概率
    

• 具体攻击流程：

1. 选择$2^{13.81}$满足差分明文对（$0080820060000000$）作为输入；
2. 计算明文输入对应的密文；
3. 建立针对6bit子秘钥的寄存器（$K_8{,}_1$的$2^6=64$情况）；
4. 猜测最后一轮子秘钥$K_8{,}_1$，得到$\Delta$($L_3[3,8,14,25]$$⨁$$R_3[17]$))的值，若为0，这将此10bit密钥对应计数器+1；
5. 猜测计数器中的最大值对应的密钥值为10bit正确的子秘钥。

• 复杂度估计：
  • 时间复杂度，选取了$2^{14.81}$个明文，猜测的密钥总数$2^6=64$，每次需要计算1个S盒，所以时间复杂度为：
    $2^{14.81}\ast 2^6/64=2^{14.81}$。

改进9轮DES攻击

• 改进思想：替换8轮攻击所使用的差分路径，以减少路径中的活动S盒的个数，并在第1轮加上一轮输入构造以满足第2轮的差分输入（构造思想通传统差分-线性攻击第1轮）。
• 差分路径
  
• 第1轮结构的构造：

1. 选取一个初始明文$P_0$。对$P_0$中的8个bit位置：(18 22 28 28 00 00 00 00)，遍历得到256个明文，记作$P_0$—$P_{255}$；
2. 再用差分(40 00 00 00 00 00 02 02)与上述产生的256个明文进行异或，得到另外的256个明文。以上对于每一个结构得到了512个明文，记作$P_{256}$—$P_{511}$；
3. 猜测第一轮$K_1{,}_6$和$K_1{,}_8$ 12bit子密钥，验证$P_i$与$P_{i-256}$，因为他们进入F函数的差分为00 00 02 02，活动S盒为S6和S8，猜测S6和S8的12bit子密钥。若经过F函数后，可能产生差分值得位置为18 22 28 28，输入对的$\Delta$$L_0$=18 22 28 28，故必然存在差分抵消的情况：$\Delta$$L_0$$⨁$$\Delta$$F(R_0)$=00 00 00 00；
4. 若抵消成功，则满足我们第2轮的差分输入；
5. 接下来步骤同8轮DES攻击。

• 复杂度分析：
  • 猜测密钥数为18bit。
  • 所需明文量为$2^{15.75}$。
  • 每次攻击进行3次S盒的运算，故$2^{15.75}\ast 2^{18}\ast 3/72=2^{29.17}$