0%

一个玩具算法的差分攻击

算法概述

​ 用流程图的形式来表示的话,看起来像这个样子(图中共有5轮)。

​ $m$ 作为明文,${k_0, k_1, \dots, k_n}$ 构成密钥。对于每一轮都通过三个操作来实现加密,分别为S盒混淆,置换混淆,轮密钥加。从算法来看,这样的确能够起到混淆的作用。不考虑明文分组只有 16 bits 的话,整个算法结构在初看之下坚不可摧。

​ 但是事实真的是这样吗?突破口在哪呢?

​ 第一点,像本文之前提到的,这个算法的明文分组只有 16 bits ,所以我们有一种最朴实的攻击思路, 穷举。所有明文的可能只有 $2^{16}$ 种,也就是说,我们可以在不超过一秒钟内,得到说有的明文-密文对,还需要密钥做什么。当然本文这里讲的是差分攻击,所以这一点我们默认没看到。

​ 第二点,如果你的老板说不把密钥恢复出来就别想拿到这个月的工资,那又该怎么办呢?这就是差分攻击的 Show time 了。

差分攻击

概述

​ 差分攻击广泛应用于破解密码算法,利用差分攻击,恢复 8 轮 DES 的密钥,只需要在普通 PC 上跑 2 分钟。差分攻击课堂上讲得很详细,互联网上也有很多文章,期中大部分在大中华局域网内也能访问到。所以我们不再赘述。(参考资料 [1] 中有师兄们很详细的介绍)

S盒特征

​ 先来看看S盒的差分输入输出特征,行坐标是S盒的输入差分,列坐标是S盒的输出差分。

​ 可以看到,输入差分-输出差分的分布并不均匀。例如,当输入差分为 0xf 时,输出差分为 0xd 的概率为 $10/16$。这就是差分攻击的突破点。

差分路径

当明文差分为 diff 时,第 r-1 轮结束后的中间结果差分为 guess_diff , 如果在密钥独立分布的情况下,对于某个 guess_diff_i 条件概率P(guess_diff_i | diff)足够大,那么 diff 和 guess_diff 就是一对好的差分起点和差分终点。为什么不说 diff 和 guess_diff 是一对好的差分对呢?因为起点和终点中间有不同的路径,我们关心的不是中间每一条路径的概率是多少,而是所有这些路径加起来的概率和是多少

​ 举个例子,对于上述算法,在 diff 为 (0 0 2 0) 的情况下,4轮之后 guess_diff为 (0 0 2 0) 最少有4条路径。

​ 其中每一条的概率都是 ${(\frac{6}{16})}^4=\frac{81}{4096}$ ,四条路径的概率就是 $\frac{81}{1024} > \frac{1}{16}$。 所以我们设定 diff 为 (0 0 2 0),guess_diff 也为 (0 0 2 0) 来恢复最后一轮的密钥。

​ 但是,这样一条路径却只能恢复 4 bits 密钥,因为只有最后一轮密钥的第5~8位才对guess_diff有影响。所以,需要找到更多概率大于$\frac{1}{16}$的差分起点和终点。

​ 怎么找呢?

活跃S盒

​ 对于一个S盒,其输入差分为0,输出差分必为0。如果差分路径中出现这样的S盒(输入差分为0),那么称之为“不活跃S盒”;反之(输入差分不为0),称之为“活跃S盒”。对于一个差分路径,活跃S盒的数量越少,其差分概率越大。本文并不准备证明这一点。

​ 所以我们把穷搜 diff 的时间复杂度从 $2^{16}$ 降到了 $C{16}^{1} + C{16}^{2}$ (即 $m$ 的输入差分最多只有 2 bits 为 1,其他位为 0)

攻击

投票

简述一下投票的过程:

  1. 对于一个固定的 diff 穷举所有可能的 $m_1$ 和 $m_2$ ( 使得 $m_1 \oplus m_2==diff$ ),这个过程的复杂度是$2^{16}$。

  2. 分别计算这些 $m_1$ 和 $m_2$ 的密文 $c_1$ 和 $c_2$ 。

  3. 猜测 guess_diff,这一步骤的复杂度在下文解释。

  4. 穷举最后一轮的密钥 key_guess,由于我们一次恢复 4 bits 密钥,所以这一步骤的复杂度是 $2^4$

  5. 对所有的 $c_1$ 和 $c_2$ ,用 key_guess 解密(一轮),如果他们解密后的差分就是 diff_guess,则 $m_1$ (或 $m_2$)给 key_guess投一票

  6. 赢得最多票数的key_guess赢得选举成为总统 (雾

所以,恢复密钥最关键的步骤就是找到/猜到合适的 diff - guess_diff 对。

找 diff - guess_diff 对

​ 寻找差分路径是差分攻击中最困难的事情,如果我们通过计算概率,来找概率最大的 diff - guess_diff ,这几乎是不可能的。因为种算法的复杂度随着层数指数增长,因此,我们不如试一试穷举。

​ 对于每一轮,首先通过有先验知识得穷举 diff ,遍历 diff 有1~2个位为1其他位为0的所有情况 ( 正如在活跃S盒一节中提到的 ),找到合适的 diff - guess_diff 对。顺便一说,这个过程也是需要投票的,判断一个 diff - guess_diff 对是不是“好的”的唯一方法就是判断能不能通过这个对恢复出正确密钥。所以,我们对每一个 diff - guess_diff 对进行“选举”。一次投票的复杂度是 ,对所有 diff - guess_diff 对投票的复杂度是

其中 $2^4$是 guess_diff 的穷举复杂度。这个复杂度是可以接受的,只需要几秒钟即可完成。甚至 ,我们只需要找到一组就可以停止搜索。

​ 找到了 diff - guess_diff 对后,按照投票的思路就可以恢复最后一层密钥了。找到最后一层密钥,重复上述过程,即可恢复出除了 $k_0$ 以外的所有密钥。至于最后的 $k_0$ ,穷举一下就结束了。

​ 攻击的攻击的完整复杂度是: , r是轮数。

代码实现

https://github.com/Roarcannotprogramming/crypto_class/tree/master

参考资料

[1] https://blog.csdn.net/weixin_43255133/article/details/83719380

欢迎关注我的其它发布渠道