题目非常小巧,IDA打开后所有算法也清晰可见。相比第十题各种逆向方法百花齐放,这题简单到可以把F5后的结果直接复制出来使用。
题目逻辑也很清晰:将输入经过一轮s盒转换后当成密钥,分别对两组明文进行加密,如果与指定的两组密文相同,则将输入经过hash比较无误后输出"Correct!"。整体就是已知两对明密文和加密算法,求密钥的操作。
加密函数sub_140002970也不复杂,梳理一下就是一个Feistal结构的加密,据此容易构造出解密方法。加密轮数只有5轮,定义域在GF(2^64)上。
其中只有一个sub_1400028C0子函数比较特殊。而这个函数粗一看可能比较奇怪,仔细研究后发现就是一个基于0x247F43CB7的乘法。
把异或看成是加法的话,sub_1400028C0函数完全满足乘法三大定律。即
因此可以进一步把加密过程的每一轮都化简为如下形式
如果把加密过程的每一轮都表示成如上形式后,可以发现密文在理论上可以表示为明文的表达式,而且里面只有KEY0和KEY1两个未知变元,因此利用两组明密文列出的两个方程在理论上可以求解得到秘钥。
使用sagemath实现题目的过程,如下:
直接构造方程的思路比较简单,但是方程次数指数级增长导致难以求解。考虑到尽量降低方程次数,编写相应的解密函数,采用中间相遇攻击方法,利用在不同轮数中的相遇情况,可以列出6个方程,然后使用Groebner基方法即可求解出方程组的解。
具体过程如下:
由于上述方程只有唯一解0xf39a46cc6199261d, 0xbdeded27481af0e0,所以该解经过s盒的逆变换后变化得到的字符串de23f9d82798377ea01743d43d5353cd直接通过了后面部分的HASH校验。
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;
}
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;
}
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;
}
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(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))
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))
v14
=
(P1
+
KEY0
+
const0) ^
3
+
P0;
P0
=
P1;
P1
=
v14;
...
v14
=
(P1
+
KEY0
+
const0) ^
3
+
P0;
P0
=
P1;
P1
=
v14;
...
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)
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)
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
)
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()
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))
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))
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)
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
)
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
[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)
最后于 2021-12-14 23:27
被xym编辑
,原因: