差分攻击1

发布于 2021-08-06  108 次阅读





差分攻击1

Intro

差分密码分析是一种密码分析的方法,主要用于破解分组加密,但也适用于流加密和加密哈希函数。而差分分析的首次提出,是针对Feal-4算法,所以本篇会先从Feal-4加密算法讲起,然后再介绍其在DES、AES中的应用。

Feal-4加密算法

Feal-4密码算法在密码学史上有很重要的地位,差分攻击正是研究者通过对Feal-4的研究首次提出的,之后又拓展到了DES密码算法上。自此以后,抗差分分析成了密码设计的一部分,差分分析成为了密码分析的基本方法。

由于Feal-4的自身的设计特点,差分攻击对Feal-4非常有效,不需要大量的选择明文就可以实现。

Feal-4加解密流程

Feal-4属于分组加密算法,采用Feistel架构。密钥长度为8字节,分组长度也是8字节。

Feal-4密码算法对一个分组的加密过程可用下图概述:

首先,8字节的密钥经过子密钥生成算法,扩展为6个4字节的子密钥 K0 – K5,加密过程使用的就是这样6个4字节子密钥。所以如果能恢复出子密钥,不需要恢复原始密钥,就能完成对Feal-4的解密,下文的差分攻击也正是这样做的。

分组加密过程中,首先8字节明文分组被分成左右两个部分,左半部与子密钥K4异或,右半部与子密钥K5异或。两个半部再异或作为右半部。接着进入4轮轮函数。每一轮里,右半部直接成为下一轮的左半部。这和DES比较类似。

第一轮里,右半部与K0异或,然后进入F函数,F函数实现非线性部分,F函数的结果与左半部进行异或,成为下一轮的右半部。后3轮同理,依次使用子密钥 K1 K2 K3。

4轮操作完成后,左半部就是密文分组的左半部,左半部与右半部异或后,成为密文分组的右半部。这就是一个分组的加密过程。

而解密过程,就是上述过程的逆过程。

轮函数

下面我们来看F函数。Feal-4的脆弱性就在F函数中。轮函数F将32比特映射为32比特。轮函数中使用了一个名为G函数的操作,G函数有两个定义如下

这里的移位是循环移位

有了G函数,我们看一下轮函数内部

对Feal-4进行差分攻击

差分分析的目标是获得子密钥。差分分析最早由Murphy于1990年,针对Feal4密码提出,随后 Biham 和 Shamir 又在一系列研究里对该技术进行了发展,属于选择明文攻击,适用于过度使用异或操作的分组密码算法。

差分分析,是指追踪明文对的差异的传播。这里的差异由我们根据目标定义,可以是异或值,也可以是别的。而对于Feal-4,差异指的就是异或值。

  • 定义:差分特征(differential characteristic)

    选定明文分组P1,分组之间的“差值”(differential)为δ,于是另一个明文分组就是P1+δ,明文P1对应的密文分组时C1,明文 P1+δ 对应的密文与C1的“距离”是 ε

若 δ 以一定概率对应着 ε,就称 δ 是一个差分特征

对于上述过程,也可以用下图描述

在Feal-4密码里,有这样两个有用的“特征”

  1. 同样的输入经过轮函数F一定产生同样的输出,即,当轮函数的输入差值为0x00000000时,轮函数的输出差值一定为0x00000000,概率为1。
  2. 当轮函数的输入差值为0x80800000时,轮函数的输出差值一定为0x02000000,概率为1。

基于这两个事实,我们来追踪差分特征0x8080000080800000在Feal-4加密过程的传播。

我们可以任意选择一个明文分组P0,然后与0x8080000080800000异或,得到明文分组P1,P0与P1构成一个明文对,差值为0x8080000080800000, 对应的密文分组分别是C0和C1,记

我们把作为输入,在Feal-4中加密,过程如下

上述差值进入后,我们可以看到在第三轮,也就是绿色箭头停止的地方,在这之前输出对于我们都是已知的,而这之后,由于0x02000000对应的轮函数差值不确定,我们不能继续追踪了。

我们记第三轮0x02000000进入f函数后得到的输出是,第四轮从右往左,输入为,输出为,最后得到的输出左右分别记为​。

由于​是已知的,我们可以倒推,得到我们原先不知道的三个数:

于是整个流程中的所有数我们现在都知道了,下面就需要得到子密钥,完成整个分析。

结合实际加密流程,我们需要通过枚举K3,计算Z0和Z1,从而获得实际的Z0^Z1

通过上面的计算,我们把​​异或,就可以得到可能的​​,如果这个值和差分分析得到实际的相等,那么就可以恢复K3,进而得到第三轮加密的结果。

然后就可以模仿刚才的方式,通过枚举得到K2,其差分特征是0x0000000080800000。最后可以通过差分特征0x00000000 02000000 求解出K1。

但是我们此时并不知道K0,K4,K5。注意到只有K0参与了和上面类似情况的加密过程,所以我们采取和上面类似的方式获得K0,用差分特征0x00000000 02000000。由于有了K3,K2,K1,我们就可以得到第一轮加密的左右输出,记为L1’、R1’,于是

同时,我们枚举K0,得到

于是我们同样可以得到关于K0的等式,判断方法和前面一样。在找到K0后,得到未加密的左右输出,只需要进行异或就可以得到K4,K5。

Sum

本篇通过Feal-4算法初步介绍了差分攻击,由于内容实在太多,其余内容会在后续几篇介绍。