首页
社区
课程
招聘
[原创]kctf2023 第二题 CN星际基地
2023-9-6 13:06 2423

[原创]kctf2023 第二题 CN星际基地

xym 活跃值
4
2023-9-6 13:06
2423
1
2
3
前期的题目逆向分析比较容易,ida解析和x64dbg调试都没有任何问题。排除掉一个无效约束后,很快就能确认输入为156字节的字符串,且字符串中只能有012三种字符。然后字符串被转换为4*39的矩阵,要求每一行的12个数相同,每一列从小到大,并且不能重复,不包含0000111122223组数。最后对输入字符串进行了一个MD5的约束。
由于题目的约束过于宽泛,因此本题实质上是一个编程题,要求尽快枚举出所有符合条件的字符串进行MD5爆破。其中每一列可以看成是一个三进制数,这样去掉000011112222对应的04080后得到了一个长度为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++;
}

因为MD5运算比较耗时,所以需要对构造的矩阵再进行校验,确保进行MD5计算的数组完全符合题目要求。

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。


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2023-9-7 15:40 被kanxue编辑 ,原因:
收藏
免费 1
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回