由Feal-4密码算法浅谈差分攻击

阅读量    40865 |   稿费 350

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

Feal-4密码算法在密码分析史上有重要的地位,差分分析就是针对该算法首次提出,是一个很好的学习范例。*ctf2019就有一道相关的问题。可能是由于已经不存在现实应用,探讨该问题的中文文档非常少,详细分析对Feal-4进行差分攻击的我还没有看到。因此笔者将自己的分析总结与大家分享。

 

一、Feal-4 加密算法

1.1 Feal密码概述

Fea加密算法由日本NTT公司于1987年发明,该算法的全称是 Fast data Encryption ALgorithm。Feal密码的最初版本就是Feal-4,后来由陆续推出了Feal-8和Feal-N。该算法提出后,经过密码学家的研究,陆续发现了该算法的一些脆弱性,即使是后续版本也存在一定程度的不安全性。

本文我们主要讨论Feal-4,分析该密码算法的脆弱性及差分攻击方法。

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

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

关于对Feal-4的差分分析,博客 http://theamazingking.com/crypto-feal.php 有比较详细的阐述, 我自己在分析时也参考了该博客的内容,感谢作者的分享。

通过进一步学习我发现,有比该博客上的方法更高效的方式进行差分攻击。第一,该博客使用的方法,子密钥枚举空间是2的32次方,如果用Python实现,运行的时间久到无法承受,本文使用的方法枚举空间是2的17次方,能大大节约了破解时间。第二,该博客中讲到,子密钥K0不能使用差分方法求得,通过测试我发现是可以的,需要稍微改动求解方式,基本与前3轮子密钥的破解相同。这样破解K0也能使用枚举2的17次方的方法。

1.2 Feal-4密码算法加解密流程

Feal-4属于分组加密算法,采用Feistel架构。密钥长度为8字节,分组长度也是8字节。Feal-4密码算法对一个分组的加密过程可用下面的图描述

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

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

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

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

1.3 轮函数

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

G0和G1,接收两个参数 a 和 b,将a+b的值加0或加1,模256后(避免超出一个字节的长度),进行循环左移位,移2位。定义完G函数,轮函数F可用下图描述

如果说轮函数F是Feal-4的核心,G函数就是F函数的核心。

 

二、对 Feal-4 进行差分攻击

接下来我们开始对Feal-4进行差分攻击。差分分析的目标是获得加密的子密钥。

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

所谓差分分析,是指追踪明文对的“差异”的传播。这里的“差异”由我们根据目标进行定义,可以是异或值,也可以是其它。针对Feal-4,我们使用的就是异或值定义“差异”,或者称之为“距离”。有些地方也称为“特征”(characteristic)

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

如果 δ 以一定的概率对应着 ε ,就称 δ 是一个差分特征。

其实这个过程我们主要关注的是非线性部分F函数,所以也可以用下面的图描述这个过程,右侧可认为是一种简要描述

在Feal-4密码里,有这样两个有用的“特征”,第一个,同样的输入经过轮函数F一定产生同样的输出,即,当轮函数的输入差值为0x00000000时,轮函数的输出差值一定时0x00000000,概率为1。第二个,当轮函数的输入差值为0x80800000时,轮函数的输出差值一定时0x02000000,概率为1。

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

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

追踪差分特征 P’ 在Feal-4中的传播,过程如下

上述差值进入Feal-4后,我们可以追踪差值到第3轮,此后由于差值0x02000000对应的轮函数差值不确定,才中断。但是,密文分组我们是知道的(选择明文攻击),因此,L’ 和 R’ 是已知的,我们可以从密文倒推,看倒推到差值追踪中断的地方

Y' = L' ^ R'
Z' = 0x02000000 ^ L'
X' = 0x80800000 ^ Y'

由上面三行,我们已经倒推到X’了,于是整个流程里的差分值,我们都是清楚的。L’ R’ X’ Y’ Z’ 都是已知的。

请注意轮函数的输出差值Z’,马上就要用到。

结合实际加密流程图,我们还可以通过猜解K3,计算实际的Z0和Z1,从而获得实际的Z0 ^ Z1

Y0 = L0 ^ R0
Y1 = L1 ^ R1
Z0 = F(Y0 ^ K3)
Z1 = F(Y1 ^ K3)

所以现在我们有了一个K3的方程,

差分分析得到实际的 Z’ = 0x02000000 ^ L’

猜解K3得到可能的 Z’ = Z0 ^ Z1 = F(Y0 ^ K3) ^ F(Y1 ^ K3)

如果猜解的K3正确,那么这两个值应该相等,由此我们就可以爆破出K3,爆破需要枚举的空间是4个字节,即2的32次方。爆破出K3后,使用K3以及 L、R,可以恢复出第四轮加密前的数据,即第三轮加密的结果

L3 = Y
R3 = L4 ^ F(Y ^ K3)

使用L3和R3继续上面的过程,可以猜解出K2。这个过程需要改变的是使用的差分特征,猜解K3时使用的差分特征是0x8080000080800000,猜解K2时使用差分特征 0x0000000080800000,可以像K3那样构建方程

由于K3已知,可以算出此时的Y0和Y1

Y0 = L ^ F(K3 ^ R0 ^ L0)

Y1 = L ^ F(K3 ^ R1 ^ L1)

同理可以由差分数据流得到Z’

Z’ = L3’ ^ 0x02000000

其中 L3’ = R4’ = L’ ^ R’

此时猜解K2,构建Z’的等式

Z’ = F(Y0 ^ K2) ^ F(Y1 ^ K2)

Z’ = L3’ ^ 0x02000000

得到K2

同理,用差分特征0x00000000 02000000 可以求解出K1

那么如何求解K0和K4、K5呢?theamazingking 博客上讲到,无法使用差分方法求解K0,只能直接猜解K0,然后求出对应的K4和K5,然后使用其他选择明文分组验证猜解的K0 K4 K5 正确性。经过测试我发现其实是可以使用差分的方式求K0的。

还是使用差分特征0x0000000002000000,此时构建K0的方程针对 X’ 构建。有了K3 K2 K1后,我们就有了第一轮加密的左右输出,从而有了L1’ 和 R1’,于是
X' = L1' ^ 0x00000000 = L1'

另一方面,猜解K0,得到

X0 = F(R1_0 ^ K0)
X1 = F(R1_1 ^ K0)
X' = X0 ^ X1

我们同样可以得到K0的等式。

提高破解速度

上述过程已经可以实现子密钥的恢复,但是枚举空间是2的32次方,theamazingking的 C demo 程序就是使用的这种算法。C程序的运行时间已经较慢了,使用Python实现破解程序,速度慢到无法承受。得益于Feal-4轮函数的设计,我们还能以更快的速度找到子密钥,方法如下

首先定义M函数,针对4字节输入产生4字节输出,如下

其中z表示zero,0x00

然后对所有可能的四字节序列,计算 Q0 和 Q1

此时有这样的结论:如果A恰好等于M(K3),那么下面的式子成立

将式子展开,就能看到等式左右两边相等

基于这种方式,我们可以将猜解子密钥的过程分为两步。

第一步,猜解16位的M(K3),即 M(K3) = (0, a0, a1, 0),猜解的空间是2的16次方

通过上述步骤得到 Q0 和 Q1,然后与 Z’ 建立方程,

Q0 ^ Q1 = F[ M(Y0) ^ (0, a0, a1, 0) ] ^ F[ M(Y1) ^ (0, a0, a1, 0) ]
Z' = L' ^ 0x02000000
Q0 ^ Q1 的8-23位 = Z' 的8-23位

通过上述三行式子,枚举全部的 M(K3),得到所有可能的 M(K3)

第二步,根据K3 = (c0, c0^a0, c1^a1, c1),继续猜解 c0 c1两个字节,猜解方式依然是基于Z’构建等式,猜解的空间是2的16次方,就可以得到完整的子密钥 K3。

通过这种子密钥求解方式,两次2的16次方的枚举,共2的17次方的枚举次数,就可以求解出子密钥K3,K2 K1 K0的求解方式一样。实际测试中,效率提升非常明显。

以上就是对Feal-4的差分攻击过程。上述分析过程仍然有可以改进的地方,比如选择明文的数量。以及使用破解K0的方式,用同一组选择明文破解K3 和 K2,第二组选择明文破解K1 和 K0,这样需要的选择明文数更少。由于时间原因我没有再做测试。

 

三、实例

*ctf 2019 的 notfeal 问题就是这样一个使用差分方式攻击Feal密码的例子。不过该程序对原始Feal-4进行了改动。有以下两点

第一,F函数的输出被逆序了。

第二,Feistel架构左右颠倒了。

只要理解了差分攻击的过程,不难调整差分过程,完成攻击。

由于输出逆序,三轮使用的差分特征要调整为

1.0×0000000080800000

2.0×8080000080800000

3.0×0000000200000002

该问题限定的选择明文数量是50组,实际上使用36组就可以成功。

代码很乱就不放了。可参考 sixstar 在github上的官方 writeup(该wp使用的就是theamazingking的C代码)

值得一提的是,差分攻击得到的子密钥组不唯一,但是都可以正确解密。

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多