BlockCipher4
huangx607087学习分组密码的笔记4
0.About
38个月过去了,终于从 3 更新到 4 了,好耶!!
因为0xGame出了一个简单的两轮DES差分,之前密码学课程中也讲了DES差分,因此自己决定尝试自行探索一下DES的差分攻击
Review:你当年写这个的时候,应该不会意识到3和4之间隔了多久吧
4. DES的差分攻击
4o01 DES的差分攻击简介
DES在 8 轮迭代之后,其原本明文的统计规律已经消失,并且扩散性达到了最好。为何DES还要设计成 16 轮呢?原因就在于,8轮DES很容易受到差分攻击。
我们来回顾一下单轮DES的Festial结构:E扩展、P置换、轮密钥加、S盒四个部分,其中只有S盒为非线性部分,其余均为线性部分,可以根据已知内容去逆推。而差分攻击,就是构建两个明文 $M_1$ 和 $M_2$,加密后得到 $C_1$ 和 $C_2$,根据 $M_1\oplus M_2$ 和 $C_1\oplus C_2$ 的值,尝试反推 $K$ 的值。而差分攻击之所以能够起作用,其原因就是 $S$ 盒的不均匀性。下图显示了 $S_1$ 的差分情况,可以看出:当 $S_0$ 两个输入异或值为 $01\text{H}$ 时,有 $6/64$ 的概率两个输出的异或值为 $3$,$2/64$ 的概率两个输出的异或值为 $5$,$12/64$ 的概率输出 $\mathrm{10}$。而当 $S_0$ 的两个输入异或值为 $\mathrm{34H}$ 时,两个输出异或值为 $2$ 的概率达到了 $16/64$。 因此,差分攻击属于选择明文攻击,需要加密机才能实现。
p.s. 本博文十六进制数均会出现 $\mathrm{0x}$ 前缀或 $\mathrm H$ 后缀,若无前后缀标明的,则均按照十进制看待。$S$ 盒编号取值为 $0\sim 7$。
我们以 $S_0$ 盒输入差分为 $01\text H$ 为例,经过实验,可以得到下面的内容:也就是当 $S_0$ 0输出差分值为 $3$ 时,可能的输入值(不是输入差分)为 $29,61,60,28,45,44$ 这六种(仔细的人可以注意到:每一组内都存在异或值为 $1$ 的一对数,因为你的输入差分为 $1$)。
1 |
|
因此,我们可以使用下面的代码,构造: int detSCnt[8][64][16]
和 set<int> detSREC[8][64][16]
。其中:detSCnt[i][j][k]
表示第 $i$ 个 $S$ 盒输入差分为 $j$ ,输出差分为 $k$ 的情况数量。 detSREC[i][j][k]
表示第 $i$ 个 $S$ 盒,输入差分为 $j$,输出差分为 $k$ 时所有可能的输入值构成的集合。例如: $\mathtt{detSCnt[0][1][3]=6}$,$\mathtt{detSRec[0][1][3]}={29,61,60,28,45,44}$。显然,有 $\mathtt{|detSRec[i][j][k]|=detSCnt[i][j][k]}$。
1 |
|
4o02 0xGame2024 DES的实现代码
后面我们以 0xGame 2024 那个简化版DES为例,这里没有考虑初始置换盒轮密钥的生成,但其实加上这两个过程,本质也一样。因为这两个过程仍然是线性变换。
1 |
|
4o02 2轮DES
对于两轮DES而言,若输入 $(L_0,R_0)$ ,可以得到输出为 $(R_0,R_1)$,然后第二轮得到输入 $(R1,R_2)$,最后交换一下得到密文为 $R_2||R_1$。
由于最后有 $R_1$ 的存在,因此其安全性和一轮 DES 没有差别。
而已知 $L_0,R_0,R_1$ 时,考虑到最后一步存在 $\oplus L_0$ 的操作,因此在一轮中,可以直接构造 $L_0=00000000\mathrm H$。这样最后一步就可以被我们忽略掉了。
假设构造 (00000000H,00000000H)
和 (00000000H,12345678H)
两个明文。由于 $E$ 置换是确定的,因此有
$$
E(\mathtt{00000000H})=\mathtt{000000000000H}=\mathtt{00H,00H,00H,00H,00H,00H,00H,00H}
$$
$$
E(\mathtt{12345678H})=\mathtt{0A41A82AC3F0H}=\mathtt{02H,24H,06H,28H,0AH,2CH,0FH,30H}
$$
因此,经过 E 扩展后,上下异或,可以得到XOR前的差分为 $\mathtt{02H,24H,06H,28H,0AH,2CH,0FH,30H}$
由于异或的Key是一样的,因此经过轮密钥加后,S 盒的输入差分也为 $\mathtt{02H,24H,06H,28H,0AH,2CH,0FH,30H}$。
假设密钥为 $\mathtt{76AD5C3FFB2EH}=\mathtt{2EH,2CH,3FH,0FH,1CH,35H,2AH,1DH}$(这个我们不知道)。但一轮加密后,我们可以得到两组数据: $(R_0,R_1)=\mathtt{00000000H,3213371EH}$ 和 $(R_0,R_1)=\mathtt{12345678H,86C32DB5H}$。因为我们 XOR 的 $L_0$ 为全 $0$,因此将两个 $R_1$ 进行 $P^{-1}$ 置换,可以得到 $R_0=\mathtt{00000000H}$ 对应的 $S$ 盒输出内容为 $\mathtt{34E41D72H}$,$R_0=\mathtt{12345678H}$ 对应的 $S$ 盒输出内容为 $\mathtt{84F321B7H}$,两个做异或,得到 $S$ 盒差分值为 $\mathtt{B0173CC5H}$。这也顺序对应了八个 $S$ 盒各自的输出差分值。
然后我们就可以进行查表:以 $S_0$ 为例:detSRec[0][0x02][0xB]={63,61,40,42,29,31}
,而 $S_0$ 的 输入内容为 $\mathtt{02H}$ 。对这里面所有的内容异或输入内容$\mathtt{02H}$,可以得到 0x02 xor detSRec[0][0x02][0xB]={61,63,42,40,31,29}
。同理,其他的七个 $S$ 盒的相关内容也能够被推出来。比如在下图中,我们得到了 $K$ 的第 $0\sim5$ 位的六个候选值和 $6\sim11$ 位的十个候选值。多次选取,取交集,就可以得到最后可能的密钥 $K$ 了。
特别提醒:推密钥的时候,考虑的不是输入差分,是输入内容!这里因为构造了全0的明文,输入差分就是输入内容,此处巧起来了,这里一定要考虑输入的内容,因为只有知道输入内容,才能尝试获取密钥!!!对输入差分的使用体现在了我们的数组下标里面。
0xGame原题是十次机会,但其实完全够用了,下面是两轮攻击的脚本。
1 |
|
可能的输出结果,最后一行为猜测密钥和实际密钥,可以看出是正确的:
1 |
|
4o03 3轮DES
进入三轮 DES,我们可以知道 $R_2$ 和 $R_3$ 的值,这个时候,我们就需要开始重视 $E$ 扩展了。 $E$ 扩展是将每组 4bit 和前一组的最后一bit、后一组的最高一bit结合。也就是
1 |
|
因此,为了每次只影响一个 $S$ 盒的输出,我们可以选择 $S$ 盒的输入差分为 $4,8,12$ (这个 $12$ 没有加任何前后缀哦),对应的十六进制位为 $2,4,6$。下面我们继续以 $S_0$ 为例:
1 |
|
可以看到,当 $S_0$ 输入差分为 $\mathtt{0CH}$ 时,输出差分为 $\mathtt{EH}$ 的概率最高,为 $14/64$。而当 $S_0$ 输出差分值 $\mathtt{EH}$ 时,对应输出差分为 $\mathtt{E0000000H}$,经过 $P$ 盒置换,得到 $\mathtt{00808200H}$。然后这个 $\mathtt{00808200H}$ 还要和 $L_0$ 异或。
因此,可以构造 $(L_0,R_0)=\mathtt{(00808200H,60000000H)}$,这样在第一轮结束后,第二轮输入的 $R_1$ 差分为全 $0$,这样 $R_2$ 在异或前的差分就是全 $0$,异或后,可以有 $R_2=\mathtt{60000000H}$。
分析每一步的概率:第一轮输入差分 $(L_0,R_0)=\mathtt{(00808200H,60000000H)}$,输出差分为 $\mathtt{60000000H,00000000H}$ 的概率为 $14/64$,第二轮输入差分 $\mathtt{60000000H,00000000H}$,输出差分 $\mathtt{00000000H,60000000H}$ 的概率为 $1$,第三轮输入差分 $\mathtt{00000000H,60000000H}$,输出差分 $\mathtt{60000000H,XXXXXXXXH}$ 的概率为 $1$。因此,询问 $5$ 次差不多就能有一次符合条件的结果。至于输出差分不符合期望的情况,我们直接丢弃,重新询问。
因此,最后我们只需要找到 $R_2=\mathtt{60000000H}$ 的输出即可,对于其他 $S$ 盒也一样,这边给出一组参考数据吧:
1 |
|
所以三轮的代码如下:
1 |
|
一个可能的运行结果:
1 |
|
4o04 4轮DES
对于 4 轮 DES 而言,其在 3 轮上面又多了一轮,我们之前已知,输入差分为 $\mathtt{60000000H}$ 时,输出差分为 $\mathtt{00808200H}$ 的概率为 $14/64$,因此我们在第三轮的基础上,继续考虑 这 $14/64$的概率:输出 $R_3=\mathtt{00808200H}$ 。这样,大约每 $21$ 次查询,就可以获得一次满足$L_4=R_3=\mathtt{00808200H}$ 的情况。
攻击代码:
1 |
|
一个可能的运行结果:
1 |
|
5 到 8 轮的情况就很复杂了,等以后遇到题目再更新吧:(