首页
社区
课程
招聘
[原创]第十一题 图穷匕见 一道不用逆向的纯算法
2021-12-14 23:27 17962

[原创]第十一题 图穷匕见 一道不用逆向的纯算法

xym 活跃值
4
2021-12-14 23:27
17962

题目非常小巧,IDA打开后所有算法也清晰可见。相比第十题各种逆向方法百花齐放,这题简单到可以把F5后的结果直接复制出来使用。
题目逻辑也很清晰:将输入经过一轮s盒转换后当成密钥,分别对两组明文进行加密,如果与指定的两组密文相同,则将输入经过hash比较无误后输出"Correct!"。整体就是已知两对明密文和加密算法,求密钥的操作。
加密函数sub_140002970也不复杂,梳理一下就是一个Feistal结构的加密,据此容易构造出解密方法。加密轮数只有5轮,定义域在GF(2^64)上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void sub_140002970(UINT64 *Plaintext, UINT64 *key, int len, UINT64 *const0, UINT64 *Ciphertext)
{
    UINT64 v8; // rax
    UINT64 v9; // rax
    UINT64 v10; // rax
    UINT64 v14; // [rsp+40h] [rbp-38h]
    UINT64 v17; // [rsp+58h] [rbp-20h]
    UINT64 v18; // [rsp+60h] [rbp-18h]
 
    v17 = Plaintext[0];
    v18 = Plaintext[1];
    for (int i = 0; i < len; ++i)
    {
        v8 = v18 ^ key[i % 2] ^ const0[i];
        v9 = sub_1400028C0(v8, v8);
        v10 = sub_1400028C0(v9, v8);
        v14 = v17 ^ v10;
        v17 = v18;
        v18 = v14;
    }
    Ciphertext[0] = v17;
    Ciphertext[1] = v18;
}

其中只有一个sub_1400028C0子函数比较特殊。而这个函数粗一看可能比较奇怪,仔细研究后发现就是一个基于0x247F43CB7的乘法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
UINT64 sub_1400028C0(UINT64 a1, UINT64 a2)
{
    UINT64 v3;
    v3 = 0;
    while (a2)
    {
        if ((a2 & 1) != 0)
            v3 = v3 ^ a1;
        a2 >>= 1;
        if (a1 & 0x8000000000000000)
            a1 = (2 * a1) ^ 0x247F43CB7;
        else
            a1 *= 2;
    }
    return v3;
}

把异或看成是加法的话,sub_1400028C0函数完全满足乘法三大定律。即

1
2
3
sub_1400028C0(a, b) == sub_1400028C0(b, a)
sub_1400028C0(sub_1400028C0(a, b), c) == sub_1400028C0(a, sub_1400028C0(b, c))
sub_1400028C0(a xor b, c) == sub_1400028C0(a, c) xor sub_1400028C0(b, c))

因此可以进一步把加密过程的每一轮都化简为如下形式

1
2
3
4
v14 = (P1 + KEY0 + const0) ^ 3 + P0;
P0 = P1;
P1 = v14;
...

如果把加密过程的每一轮都表示成如上形式后,可以发现密文在理论上可以表示为明文的表达式,而且里面只有KEY0和KEY1两个未知变元,因此利用两组明密文列出的两个方程在理论上可以求解得到秘钥。
使用sagemath实现题目的过程,如下:

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
def enc(pt, key):
  pt0, pt1 = pt
  key0, key1 = key
  var('x')
  var('a')
  K.<a> = GF(2^64, name='a',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)
  c0=0x20F4641148FA59A5
  c1=0x96950F0D368EB90D
  c2=0x7467551A8419E0B5
  c3=0x01A61218FE968D86
  c4=0x192DB7EB78969270
  cntList=[]
  cntList.append(K.fetch_int(c0))
  cntList.append(K.fetch_int(c1))
  cntList.append(K.fetch_int(c2))
  cntList.append(K.fetch_int(c3))
  cntList.append(K.fetch_int(c4))
  Left = K.fetch_int(pt0)
  Right = K.fetch_int(pt1)
  keyList=[]
  keyList.append(K.fetch_int(key0))
  keyList.append(K.fetch_int(key1))
  for i in range(5):
    tmp = Right+keyList[i%2]+cntList[i]
    tmp = tmp^3
    tmp = tmp + Left
    Left = Right
    Right = tmp
  return [hex(Left.integer_representation()),hex(Right.integer_representation())]
pt=[0x73C51960EF361B30, 0xFBD5C824382C435D]
key = [0xb118c960bcb118c9, 0xb118c960bcb118c9]
enc(pt,key)

直接构造方程的思路比较简单,但是方程次数指数级增长导致难以求解。考虑到尽量降低方程次数,编写相应的解密函数,采用中间相遇攻击方法,利用在不同轮数中的相遇情况,可以列出6个方程,然后使用Groebner基方法即可求解出方程组的解。
具体过程如下:

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#下面代码可以直接在sage中运行
 
#1. 构造数域
K.<x> = GF(2^64, name='x',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)
#2. 方程的构造
#首先形式化计算出表示方法
P0=var('P0')
P1=var('P1')
M0=var('M0')
M1=var('M1')
y = var('y')
z = var('z')
c0 = var('c0')
c1 = var('c1')
c2 = var('c2')
c3 = var('c3')
c4 = var('c4')
R.<P0,P1,y,z,c0,c1,c2,c3,c4,M0,M1>=GF(2)[]
#正向加密过程形式化计算
v17 = P0
v18 = P1
 
v8 = v18 + y + c0
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_forward_1 = v18
 
v8 = v18 + z + c1
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_forward_2 = v18
 
v8 = v18 + y + c2
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_forward_3 = v18
#逆向解密过程形式化计算
v17 = M1
v18 = M0
 
v8 = v18 + y + c4
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_backward_1 = v18
 
v8 = v18 + z + c3
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_backward_2 = v18
 
v8 = v18 + y + c2
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_backward_3 = v18
 
#其次带入实际数据
 
ct0 = 0x55250D8CEEDFFB35
ct1 = 0xDBAFC899D2AAD5EC
ct2 = 0xD30CE81D5CFD183E
ct3 = 0x3C205341A484C650
pt0 = 0x73C51960EF361B30
pt1 = 0xFBD5C824382C435D
pt2 = 0x79EEBA9CCF47A451
pt3 = 0x55B4D0E1061D12D0
cnt0 = 0x20F4641148FA59A5
cnt1 = 0x96950F0D368EB90D
cnt2 = 0x7467551A8419E0B5
cnt3 = 0x01A61218FE968D86
cnt4 = 0x192DB7EB78969270
 
y,z=K['y,z'].gens()
 
#利用第1组明密文对列3个方程
eq1 = \
eq_forward_1(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_3(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq2 = \
eq_forward_2(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_2(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq3 = \
eq_forward_3(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_1(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
#利用第2组明密文对列3个方程
eq4 = \
eq_forward_1(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_3(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq5 = \
eq_forward_2(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_2(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq6 = \
eq_forward_3(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_1(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
#至此列出6个方程。
 
#3.利用sagemath自带的Groebner基解方程
I=ideal(eq1,eq2,eq3,eq4,eq5,eq6)
B=I.groebner_basis()
key0 = hex(B[0].coefficients()[1].integer_representation())
key1 = hex(B[1].coefficients()[1].integer_representation())
print(key0,key1)

由于上述方程只有唯一解0xf39a46cc6199261d, 0xbdeded27481af0e0,所以该解经过s盒的逆变换后变化得到的字符串de23f9d82798377ea01743d43d5353cd直接通过了后面部分的HASH校验。


[培训]《安卓高级研修班(网课)》月薪三万计划

最后于 2021-12-14 23:27 被xym编辑 ,原因:
收藏
点赞7
打赏
分享
最新回复 (1)
雪    币: 73
活跃值: (868)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hixhi 2021-12-21 09:48
2
0
完全看不懂,话说请教下楼主,做这样的题,大概需要哪些知识呢?是要对各种密码学中的加密算法都很熟悉吗?
游客
登录 | 注册 方可回帖
返回