|
1
2
3
|
前期的题目逆向分析比较容易，ida解析和x64dbg调试都没有任何问题。排除掉一个无效约束后，很快就能确认输入为
156
字节的字符串，且字符串中只能有
0
、
1
、
2
三种字符。然后字符串被转换为
4
*
39
的矩阵，要求每一行的
1
和
2
个数相同，每一列从小到大，并且不能重复，不包含
0000
、
1111
、
2222
这
3
组数。最后对输入字符串进行了一个MD5的约束。
由于题目的约束过于宽泛，因此本题实质上是一个编程题，要求尽快枚举出所有符合条件的字符串进行MD5爆破。其中每一列可以看成是一个三进制数，这样去掉
0000
、
1111
、
2222
对应的
0
、
40
、
80
后得到了一个长度为
78
的数组，需要在其中取一半数据满足前面的约束。在新的提示出来之前，由于解空间过于巨大，基本没有什么进展，直到晚上新增了
2
个约束，重新建立了模型。
根据新的约束，可以把
78
的数组再分成分别互补的
39
组数据，每次从每组数据里面取一个。
|
|
1
2
3
4
5
|
Pars[
39
]
=
{{
1
,
2
},{
3
,
6
},{
4
,
8
},{
5
,
7
},{
9
,
18
},{
10
,
20
},{
11
,
19
},{
12
,
24
},{
13
,
26
},{
14
,
25
}
,{
15
,
21
},{
16
,
23
},{
17
,
22
},{
27
,
54
},{
28
,
56
},{
29
,
55
},{
30
,
60
},{
31
,
62
},{
32
,
61
},{
33
,
57
},{
34
,
59
},{
35
,
58
},{
36
,
72
},{
37
,
74
},{
38
,
73
},{
39
,
78
},{
41
,
79
},{
42
,
7
5
},{
43
,
77
},{
44
,
76
},{
45
,
63
},{
46
,
65
},{
47
,
64
},{
48
,
69
},{
49
,
71
},{
50
,
70
},{
51
,
66
},{
52
,
68
},{
53
,
67
},}
|
定义一个39比特的变量，可以根据相应比特为0或者1来取相应每组数据的前者或者后者。又根据高位0、1、2分别占三分之一，可知39比特的后26位必有一半取1，一半取0。因此再将39比特分为2组，前13比特可以采用完全遍历的方式，时间基本可以忽略，后26比特设置前一半为1，后一半为0，然后逐个移动比特实现遍历。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/
/
移动比特实现遍历的代码
BOOL
flag
=
true;
int
cn1
=
0
;
for
(
int
i
=
0
; i <
25
; i
+
+
)
{
if
(Choice[i]
=
=
1
&& Choice[i
+
1
]
=
=
0
)
{
for
(
int
j
=
0
; j < cn1; j
+
+
)
{
Choice[j]
=
1
;
}
for
(
int
j
=
cn1; j < i; j
+
+
)
{
Choice[j]
=
0
;
}
Choice[i]
=
0
;
Choice[i
+
1
]
=
1
;
flag
=
false;
break
;
}
if
(Choice[i]
=
=
1
)
cn1
+
+
;
}
|
|
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
|
int
Check()
{
BYTE Tmp[
40
];
int
a1
=
0
;
int
a2
=
0
;
for
(
int
i
=
0
; i <
39
; i
+
+
)
{
if
(Data[i] >
=
54
)
{
Tmp[i]
=
Data[i]
-
54
;
a1
+
+
;
}
else
if
(Data[i] >
=
27
)
{
Tmp[i]
=
Data[i]
-
27
;
a2
+
+
;
}
else
{
Tmp[i]
=
Data[i];
}
}
if
(a1 !
=
a2 || a1 !
=
13
)
{
return
1
;
}
a1
=
0
;
a2
=
0
;
for
(
int
i
=
0
; i <
39
; i
+
+
)
{
if
(Tmp[i] >
=
18
)
{
Tmp[i]
=
Tmp[i]
-
18
;
a1
+
+
;
}
else
if
(Tmp[i] >
=
9
)
{
Tmp[i]
=
Tmp[i]
-
9
;
a2
+
+
;
}
else
{
Tmp[i]
=
Tmp[i];
}
}
if
(a1 !
=
a2 || a1 !
=
13
)
{
return
2
;
}
a1
=
0
;
a2
=
0
;
for
(
int
i
=
0
; i <
39
; i
+
+
)
{
if
(Tmp[i] >
=
6
)
{
Tmp[i]
=
Tmp[i]
-
6
;
a1
+
+
;
}
else
if
(Tmp[i] >
=
3
)
{
Tmp[i]
=
Tmp[i]
-
3
;
a2
+
+
;
}
else
{
Tmp[i]
=
Tmp[i];
}
}
if
(a1 !
=
a2 || a1 !
=
13
)
{
return
3
;
}
a1
=
0
;
a2
=
0
;
for
(
int
i
=
0
; i <
39
; i
+
+
)
{
if
(Tmp[i] >
=
2
)
{
a1
+
+
;
}
else
if
(Tmp[i] >
=
1
)
{
a2
+
+
;
}
}
if
(a1 !
=
a2 || a1 !
=
13
)
{
return
4
;
}
return
0
;
}
|
经过优化后的代码运行速度依然比较慢，主要原因还是符合条件的解比较多，需要大量调用MD5计算。
由于手头没有搭建好的GPU开发的环境，所以程序写好后设置不同参数开了多个进程开始并行跑。幸好睡觉起来后发现结果已经跑出来了，赶在出门前提交了flag。
更多【kctf2023 第二题 CN星际基地】相关视频教程：www.yxfzedu.com