[原创]kctf2023 第二题 CN星际基地-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

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

发表于: 2023-9-6 13:06 2824

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

xym

2023-9-6 13:06

2824

前期的题目逆向分析比较容易，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组数据，每次从每组数据里面取一个。

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，然后逐个移动比特实现遍历。

//移动比特实现遍历的代码
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计算的数组完全符合题目要求。

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;
}