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$。

1

我们以 $S_0$ 盒输入差分为 $01\text H$ 为例,经过实验,可以得到下面的内容:也就是当 $S_0$ 0输出差分值为 $3$ 时,可能的输入(不是输入差分)为 $29,61,60,28,45,44$ 这六种(仔细的人可以注意到:每一组内都存在异或值为 $1$ 的一对数,因为你的输入差分为 $1$)。

1
2
3
4
5
6
7
8
9
10
11
3:{29, 61, 60, 28, 45, 44}
5:{6, 7}
6:{37, 12, 13, 36}
7:{50, 51, 22, 23}
9:{40, 41, 14, 15, 16, 17, 54, 55, 56, 57}
10:{4, 5, 38, 39, 48, 49, 20, 21, 52, 53, 58, 59}
11:{32, 33, 2, 3}
12:{8, 9, 46, 47, 18, 19, 24, 25, 26, 27}
13:{34, 35, 10, 11, 62, 63}
14:{0, 1}
15:{42, 43, 30, 31}

因此,我们可以使用下面的代码,构造: 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
detSCnt=[[[0 for k in range(16)]for j in range(64)]for i in range(8)]
detSRec=[[[set() for k in range(16)]for j in range(64)]for i in range(8)]
def getS(sid,val):
v1,v2=2*(not not (val&32))+(val&1),(val>>1)&15
return S[sid][v1][v2]
def calcS():
for i in range(8):
for j in range(64):
for k in range(64):
in1,in2=j,k
out1,out2=getS(i,in1),getS(i,in2)
detin=j^k
detout=out1^out2
detSCnt[i][detin][detout]+=1
detSRec[i][detin][detout]|=set([j])

4o02 0xGame2024 DES的实现代码

后面我们以 0xGame 2024 那个简化版DES为例,这里没有考虑初始置换盒轮密钥的生成,但其实加上这两个过程,本质也一样。因为这两个过程仍然是线性变换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#Util.py
from functools import reduce
from operator import add
from random import Random

__s_box = [[[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7], [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8], [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0], [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]],
[[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10], [3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5], [0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15], [13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]],
[[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8], [13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1], [13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7], [1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]],
[[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15], [13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9], [10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4], [3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]],
[[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9], [14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6], [4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14], [11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]],
[[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11], [10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8], [9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6], [4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]],
[[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1], [13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6], [1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2], [6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]],
[[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7], [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2], [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8], [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]]]
__ep = [31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11, 12, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 19, 20, 21, 22, 23, 24, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, 0]
__p = [15, 6, 19, 20, 28, 11, 27, 16, 0, 14, 22, 25, 4, 17, 30, 9, 1, 7, 23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24]
def EP(data):
return [data[x] for x in __ep]
def P(data):
return [data[x] for x in __p]
def S_box(data):
output = []
for i in range(0, 48, 6):
row = data[i] * 2 + data[i + 5]
col = reduce(add, [data[i + j] * (2 ** (4 - j)) for j in range(1, 5)])
output += [int(x) for x in format(__s_box[i // 6][row][col], '04b')]
return output
def bytes2bin(m):
return [int(i) for i in bin(int(m.hex(), 16))[2:].zfill(8 * len(m))]
def bin2bytes(m):
return int(''.join([str(i) for i in m]), 2).to_bytes(length=len(m)//8, byteorder='big')
def encrypt(plain, key,nrd=2): #这边以前没有nrd参数,也给加上了,以前就是 2 轮。
pt = bytes2bin(plain)
sub_key = bytes2bin(key)
L, R = pt[:32], pt[32:]
for i in range(nrd):
prev_L = L
L = R
expanded_R = EP(R)
xor_result = [a ^ b for a, b in zip(expanded_R, sub_key)]
substituted = S_box(xor_result)
permuted = P(substituted)
R = [a ^ b for a, b in zip(permuted, prev_L)]
cipher = R + L
return bin2bytes(cipher)
def decrypt(cipher, key,nrd=2):
ct = bytes2bin(cipher)
sub_key = bytes2bin(key)
L, R = ct[:32], ct[32:]
for i in range(nrd):
prev_L = L
L = R
expanded_R = EP(R)
xor_result = [a ^ b for a, b in zip(expanded_R, sub_key)]
substituted = S_box(xor_result)
permuted = P(substituted)
R = [a ^ b for a, b in zip(permuted, prev_L)]
cipher = R + L
return bin2bytes(cipher)
# 以下内容0xGame原题没有,为作者自加内容
S = __s_box.copy()
__pinv = [8, 16, 22, 30, 12, 27, 1, 17, 23, 15, 29, 5, 25, 19, 9,0, 7, 13, 24, 2, 3, 28, 10, 18, 31, 11, 21, 6, 4, 26, 14, 20]
def Pinv(data):
return [data[x] for x in __pinv]

4o02 2轮DES

2

对于两轮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$ 盒各自的输出差分值。

3

然后我们就可以进行查表:以 $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的明文,输入差分就是输入内容,此处巧起来了,这里一定要考虑输入的内容,因为只有知道输入内容,才能尝试获取密钥!!!对输入差分的使用体现在了我们的数组下标里面。

4

0xGame原题是十次机会,但其实完全够用了,下面是两轮攻击的脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
from Util import *
from random import *
from os import urandom
from Crypto.Util.number import *
detSCnt=[[[0 for k in range(16)]for j in range(64)]for i in range(8)]
detSRec=[[[set() for k in range(16)]for j in range(64)]for i in range(8)]
def getS(sid,val):
v1,v2=2*(not not (val&32))+(val&1),(val>>1)&15
return S[sid][v1][v2]

def calcS():
for i in range(8):
for j in range(64):
for k in range(64):
in1,in2=j,k
out1,out2=getS(i,in1),getS(i,in2)
detin=j^k
detout=out1^out2
detSCnt[i][detin][detout]+=1
detSRec[i][detin][detout]|=set([j])


def getrandpair(x):
a=getrandbits(64)
b=a^x
return a,b

calcS()
myKey=urandom(6)
Aarr=[0x00000000,0x22222222,0x44444444,0x88888888,0x11111111,0x12481248,0x84218421,0xedb7edb7,0xffffffff]
n=len(Aarr)
M=[Aarr[i].to_bytes(8,byteorder='big') for i in range(len(Aarr))]
C=[]
for i in range(n):
C.append(encrypt(M[i],myKey))
bC=[]
for i in range(n):
cval=bytes_to_long(C[i])
bC.append(((cval&0xffffffff).to_bytes(4,byteorder='big'),(cval>>32).to_bytes(4,byteorder='big')))

Sinput=[]
for i in range(n):
beforeS=M[i][4:]
beforeS=bytes_to_long(bin2bytes(EP(bytes2bin(beforeS))))
arr=[]
for j in range(8):
arr.append(beforeS&63)
beforeS>>=6
Sinput.append(arr[::-1])
Soutput=[]
for i in range(n):
afterE=C[i][4:]
afterE=bytes_to_long(bin2bytes(Pinv(bytes2bin(afterE))))
arr=[]
for j in range(8):
arr.append(afterE&15)
afterE>>=4
Soutput.append(arr[::-1])
import copy
dSoutput=copy.deepcopy(Soutput)
for i in range(n-1,-1,-1):
for j in range(8):
dSoutput[i][j]^=dSoutput[0][j]
print(Sinput)
print(dSoutput)
K=[]
for i in range(8):
D=set(list(range(64)))
for j in range(1,n):
x=Sinput[j][i]
y=dSoutput[j][i]
dtmp=list(detSRec[i][x][y])
ctmp=[i^x for i in dtmp]
D&=set(ctmp)
K.append(list(D))
print(K)
keyguess=0
for i in range(8):
keyguess<<=6
keyguess|=K[i][0]
print(hex(keyguess)[2:],myKey.hex())

可能的输出结果,最后一行为猜测密钥和实际密钥,可以看出是正确的:

1
2
3
4
Sinput=dSinput=[[0, 0, 0, 0, 0, 0, 0, 0], [4, 4, 4, 4, 4, 4, 4, 4], [8, 8, 8, 8, 8, 8, 8, 8], [17, 17, 17, 17, 17, 17, 17, 17], [34, 34, 34, 34, 34, 34, 34, 34], [2, 36, 9, 16, 2, 36, 9, 16], [48, 8, 4, 3, 48, 8, 4, 3], [61, 27, 54, 47, 61, 27, 54, 47], [63, 63, 63, 63, 63, 63, 63, 63]]
dSoutput=[[0, 0, 0, 0, 0, 0, 0, 0], [3, 7, 13, 6, 13, 14, 7, 7], [10, 10, 10, 11, 14, 9, 10, 12], [13, 3, 12, 4, 0, 4, 0, 6], [10, 9, 0, 8, 0, 0, 6, 6], [12, 11, 13, 14, 7, 8, 3, 3], [11, 10, 13, 10, 7, 9, 7, 0], [2, 1, 8, 6, 5, 13, 13, 1], [1, 13, 6, 1, 0, 9, 13, 7]]
[[13], [44], [16], [13], [40], [61], [12], [7]]
36c40da3d307 36c40da3d307

4o03 3轮DES

进入三轮 DES,我们可以知道 $R_2$ 和 $R_3$ 的值,这个时候,我们就需要开始重视 $E$ 扩展了。 $E$ 扩展是将每组 4bit 和前一组的最后一bit、后一组的最高一bit结合。也就是

1
PQRS ABCD WXYZ --> ZPQRSA SABCDW DWXYZP

因此,为了每次只影响一个 $S$ 盒的输出,我们可以选择 $S$ 盒的输入差分为 $4,8,12$ (这个 $12$ 没有加任何前后缀哦),对应的十六进制位为 $2,4,6$。下面我们继续以 $S_0$ 为例:

1
2
3
detSCnt[0][4]=[0, 0, 0, 6, 0, 10, 10, 6, 0, 4, 6, 4, 2, 8, 6, 2]
detSCnt[0][8]=[0, 0, 0, 12, 0, 8, 8, 4, 0, 6, 2, 8, 8, 2, 2, 4]
detSCnt[0][12]=[0, 0, 0, 8, 0, 6, 6, 0, 0, 6, 6, 4, 6, 6, 14, 2]

可以看到,当 $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$ 次差不多就能有一次符合条件的结果。至于输出差分不符合期望的情况,我们直接丢弃,重新询问。

5

因此,最后我们只需要找到 $R_2=\mathtt{60000000H}$ 的输出即可,对于其他 $S$ 盒也一样,这边给出一组参考数据吧:

1
2
3
4
5
6
7
8
9
10
S盒的参考值如下:
S0 0ch eh 14/64 00808200h 60000000h 00808200h=P(e0000000h)
S1 08h ah 16/64 40080000h 04000000h 40080000h=P(0a000000h)
S2 04h 9h 12/64 04000100h 00200000h ... ... ... ... ... ..
S3 04h 7h 12/64 80401000h 00020000h
S4 0ch 3h 10/64 20000080h 00006000h
S5 08h 6h 16/64 00200008h 00000400h
S6 0ch ch 14/64 00100001h 00000060h
S7 04h 7h 12/64 00020820h 00000002h

所以三轮的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from Util import *
from random import *
from os import urandom
from Crypto.Util.number import *
from datetime import *
detSCnt=[[[0 for k in range(16)]for j in range(64)]for i in range(8)]
detSRec=[[[set() for k in range(16)]for j in range(64)]for i in range(8)]
def getS(sid,val):
v1,v2=2*(not not (val&32))+(val&1),(val>>1)&15
return S[sid][v1][v2]

def calcS():
for i in range(8):
for j in range(64):
for k in range(64):
in1,in2=j,k
out1,out2=getS(i,in1),getS(i,in2)
detin=j^k
detout=out1^out2
detSCnt[i][detin][detout]+=1
detSRec[i][detin][detout]|=set([j])
#bin2bytes(P(bytes2bin(bytes.fromhex('00070000')))).hex()

def getrandpair(x):
a=getrandbits(64)
b=a^x
return a,b
def l2b(x,l=-1):
bs=long_to_bytes(x)
if(len(bs)<l):
bs=bytes([0]*(l-len(bs)))+bs
return bs

calcS()
myKey=urandom(6)#b'F(x)=x'
xorNum=[0x0080820060000000,0x4008000004000000,0x0400010000200000,0x8040100000020000,
0x2000008000006000,0x0020000800000400,0x0010000100000060,0x0002082000000002]
numxe=[(0x0c,0xe),(0x08,0xa),(0x04,0x9),(0x04,0x7),
(0x0c,0x3),(0x08,0x6),(0x0c,0xc),(0x04,0x7)]

tStart=datetime.now()
totalQuery=0
K=[None for _ in range(8)]
for T in range(8):
NCipher=7
Aarr=[]
while len(Aarr)<NCipher:
totalQuery+=1
a,b=getrandpair(xorNum[T])
ba,bb=l2b(a,8),l2b(b,8)
x,y=encrypt(ba,myKey,3),encrypt(bb,myKey,3)
ix,iy=bytes_to_long(x),bytes_to_long(y)
if(((ix^iy)&0xffffffff)==(xorNum[T]&0xffffffff)):
Aarr.append((ba,bb))
Sinput=[]
for i in range(NCipher):
r2,r3=Aarr[i][1][4:],Aarr[i][1][:4]
eb=bin2bytes(EP(bytes2bin(r2)))
ebi=bytes_to_long(eb)
tmparr=[]
for j in range(8):
tmparr.append(ebi&0x3f)
ebi>>=6
Sinput.append(tmparr[::-1])
sarr=detSRec[T][numxe[T][0]][numxe[T][1]]
D=set(range(64))
for i in range(NCipher):
s0=Sinput[i][T]
xarr=set([s0^i for i in sarr])
D=D&xarr
K[T]=D

testM=urandom(8)
testC=encrypt(testM,myKey,3)
totalQuery+=1
guessKey=None
def dfs(step,keyarr):
global guessKey
if(step==8):
keyval=0
for i in range(8):
keyval<<=6
keyval|=keyarr[i]
key2=int.to_bytes(keyval,6,byteorder='big')
cc=encrypt(testM,key2,3)
if(cc==testC):
guessKey=key2
return
for i in K[step]:
dfs(step+1,keyarr+[i])
dfs(0,[])
print(guessKey.hex(),myKey.hex(),guessKey==myKey)
if(guessKey==myKey):

print(f'Success with queryed {totalQuery} times')
else:
print('Fail')
tEnd=datetime.now()
print(f'Time Cost:{tEnd-tStart}')

一个可能的运行结果:

1
2
3
fd31f37d571f fd31f37d571f True
Success with queryed 407 times
Time Cost:0:00:00.225095

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}$ 的情况。

6

攻击代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
from Util import *
from random import *
from os import urandom
from Crypto.Util.number import *
from datetime import *
detSCnt=[[[0 for k in range(16)]for j in range(64)]for i in range(8)]
detSRec=[[[set() for k in range(16)]for j in range(64)]for i in range(8)]
def getS(sid,val):
v1,v2=2*(not not (val&32))+(val&1),(val>>1)&15
return S[sid][v1][v2]

def calcS():
for i in range(8):
for j in range(64):
for k in range(64):
in1,in2=j,k
out1,out2=getS(i,in1),getS(i,in2)
detin=j^k
detout=out1^out2
detSCnt[i][detin][detout]+=1
detSRec[i][detin][detout]|=set([j])
def getrandpair(x):
a=getrandbits(64)
b=a^x
return a,b
def l2b(x,l=-1):
bs=long_to_bytes(x)
if(len(bs)<l):
bs=bytes([0]*(l-len(bs)))+bs
return bs

calcS()
myKey=urandom(6)
xorNum=[0x0080820060000000,0x4008000004000000,0x0400010000200000,0x8040100000020000,
0x2000008000006000,0x0020000800000400,0x0010000100000060,0x0002082000000002]
T=0
totalQuery=0
NCipher=5
tStart=datetime.now()
K=[set(range(64))for i in range(8)]
for T in range(8):
Aarr=[]
Carr=[]
while(len(Aarr)<NCipher):
totalQuery+=1
a,b=getrandpair(xorNum[T])
ba,bb=l2b(a,8),l2b(b,8)
x,y=encrypt(ba,myKey,4),encrypt(bb,myKey,4)
ix,iy=bytes_to_long(x),bytes_to_long(y)
if(((ix^iy)&0xffffffff)==(xorNum[T]>>32)):
Aarr.append((ba,bb))
Carr.append((x,y))
for i in range(5):
r3,r4=Carr[i][1][4:],Carr[i][1][:4]
r30,r40=Carr[i][0][4:],Carr[i][0][:4]
dr4=bytes_to_long(r4)^bytes_to_long(r40)
dr4^=xorNum[T]&0xffffffff
bdr4=l2b(dr4,4)
din=xorNum[T]>>32
X=EP(bytes2bin(l2b(din,4)))
dSin=[32*X[6*_]+16*X[6*_+1]+8*X[6*_+2]+4*X[6*_+3]+2*X[6*_+4]+X[6*_+5] for _ in range(8)]
iSout=bytes_to_long(bin2bytes(Pinv(bytes2bin(bdr4))))
dSout=[]
r3Sin=[]
r3E=EP(bytes2bin(r3))
r3Sin=[32*r3E[6*_]+16*r3E[6*_+1]+8*r3E[6*_+2]+4*r3E[6*_+3]+2*r3E[6*_+4]+r3E[6*_+5] for _ in range(8)]
for j in range(8):
dSout.append(iSout&15)
iSout>>=4
dSout=dSout[::-1]
for j in range(8):
tmpset=list(detSRec[j][dSin[j]][dSout[j]])
keyset=set([ts ^ r3Sin[j]for ts in tmpset])
K[j]&=keyset
testM=urandom(8)
testC=encrypt(testM,myKey,3)
totalQuery+=1
guessKey=None

def dfs(step,keyarr):
global guessKey
if(step==8):
keyval=0
for i in range(8):
keyval<<=6
keyval|=keyarr[i]
key2=int.to_bytes(keyval,6,byteorder='big')
cc=encrypt(testM,key2,3)
if(cc==testC):
guessKey=key2
return
for i in K[step]:
dfs(step+1,keyarr+[i])
print(f'K={K}')
dfs(0,[])
print(guessKey.hex(),myKey.hex(),guessKey==myKey)
if(guessKey==myKey):
print(f'Success with queryed {totalQuery} times')
else:
print('Fail')
tEnd=datetime.now()
print(f'Time Cost:{tEnd-tStart}')

一个可能的运行结果:

1
2
3
4
K=[{52}, {0}, {18}, {33}, {14}, {58}, {43}, {10}]
d004a13baaca d004a13baaca True
Success with queryed 2255 times
Time Cost:0:00:00.565169

5 到 8 轮的情况就很复杂了,等以后遇到题目再更新吧:(


BlockCipher4
http://example.com/2024/11/06/BlockCipher4/
作者
huangx607087
发布于
2024年11月6日
许可协议