[原创] KCTF2022——第二题末日邀请之论如何掉坑里

2022-5-14 14:59 7343

[原创] KCTF2022——第二题末日邀请之论如何掉坑里

brucy

2022-5-14 14:59

7343

1.前言

这题我入坑了，并且还在不停的往坑里钻，深陷其中不可自拔...以至于我死磕了2天（当然也不是一直都在分析这题，不然可能真的要崩溃了，很多时候是在忙工作的事），没能在比赛规定时间内解出来。本来也不打算发这篇文章了，但还是要给自己一个提醒罢，于是这篇文章就论如何掉坑里。

2.分析

程序允许读取最大 42个字节的输入数据，然后分为 4段进行校验。共有 6个条件限制：

对输入的数据做个校验和，并规定校验和等于 0xF52E0765。后来看到大佬们讨论才知道这里是一处魔改的 CRC32。
前 3个输入转换成整数型然后进行异或，要求结果等于 7。很容易想到 1, 2,4的组合，具体是哪种组合形式目前未知。

上图中的 do...while循环正常情况下 v17的结果一定是 7，但是某些输入数据会导致其结果是个负数，这是我在动态调试下发现的，例如输入的是 WFq7gSX9DjxGRzfH1vnTkKZ6thopsy8LMVAad4UE
经过多次测试，只有结果是 7才是正常且正确的，满足这个条件的输入的长度最多在 40个字节，由此我深信不疑的认为输入长度为 40个字节（这为我后面掉坑里埋下了伏笔）。

3.校验输入（注意此时已经将原输入数组转换成数字的数组了）：

input[3] == 20
input[4] == 12
input[5] == 29
input[6] == 15

不难得出原输入应该是 KCTF

4.截取输入区间[7:16)的数据，满足前一位能被1整除，前两位能被2整除，以此类推到前9位能被9整除。

5.对输入区间[7:16)的9个数据进行升序排序，结果必须等于 123456789

结合条件4和条件5可以得知这9个数据均为数字，并且不重复，于是可以对这9个数字进行一个全排列，依次代入条件4中校验。9! = 362880，这个空间大小还是能够接受的。最后不到一秒就得到正确结果为 381654729

6.这里开始掉坑里了，先看反编译的结果

v20表示的是剩下要校验的长度，因为一开始我深信不疑的认为输入数据总长度为 40个字节，经过了前5个校验，那么剩下需要校验的长度就是 24个字节。所以这里应该走的是 else分支，也就是需要通过 while循环的校验。在此之前 input后 24位数据经过了 Trans函数的变换，所以需要去研究这个函数的具体算法。

我花了比较多的时间去手撕这个函数，最外层循环会对输入的数据 input按 8字节分组，根据我输入的总长度为 40，所以这里会出现 3个分组。下面展示这个过程：

100

101

102

103

104

分组1
Loop1:
v10 = (a[0] << 7 ) | (a[1]>> 1)
ans[0] = a[0] ^ (v10 << 1 | 1) == 0
 
Loop2:
v10 = (a[1] << 6 ) | (a[2]>> 2)
ans[1] = a[0] ^ (v10 << 1 | 1) == 0
 
Loop3:
v10 = (a[2] << 5 ) | (a[3]>> 3)
ans[2] = a[0] ^ (v10 << 1 | 1) == 0x9D
 
Loop4:
v10 = (a[3] << 4 ) | (a[4]>> 4)
ans[3] = a[0] ^ (v10 << 1 | 1) == 0x08
 
Loop5:
v10 = (a[4] << 3 ) | (a[5]>> 5)
ans[4] = a[0] ^ (v10 << 1 | 1) == 0x1D
 
Loop6:
v10 = (a[5] << 2 ) | (a[6]>> 6)
ans[5] = a[0] ^ (v10 << 1 | 1) == 0x00
 
Loop7:
v10 = (a[6] << 1 ) | (a[7]>> 7)
ans[6] = a[0] ^ (v10 << 1 | 1) == 0x68
 
Loop8:
v10 = (a[7] << 0 ) | (a[8]>> 8)
ans[7] = a[0] ^ (v10 << 1 | 1) == 0xC5
循环结束
ans[7] = a[0] ^ (a[7]<<1 |1) == 0xC5
 
分组2
Loop1:
v10 = (a[8] << 7 ) | (a[9]>> 1)
ans[8] = a[8] ^ (v10 << 1 | 1) == 0x1F
 
Loop2:
v10 = (a[9] << 6 ) | (a[10]>> 2)
ans[9] = a[8] ^ (v10 << 1 | 1) == 0x3C
 
Loop3:
v10 = (a[10] << 5 ) | (a[11]>> 3)
ans[10] = a[8] ^ (v10 << 1 | 1) == 0x1C
 
Loop4:
v10 = (a[11] << 4 ) | (a[12]>> 4)
ans[11] = a[8] ^ (v10 << 1 | 1) == 0x11
 
Loop5:
v10 = (a[12] << 3 ) | (a[13]>> 5)
ans[12] = a[8] ^ (v10 << 1 | 1) == 0x1B
 
Loop6:
v10 = (a[13] << 2 ) | (a[14]>> 6)
ans[13] = a[8] ^ (v10 << 1 | 1) == 0x41
 
Loop7:
v10 = (a[14] << 1 ) | (a[15]>> 7)
ans[14] = a[8] ^ (v10 << 1 | 1) == 0x08
 
Loop8:
v10 = (a[15] << 0 ) | (a[16]>> 8)
ans[15] = a[8] ^ (v10 << 1 | 1) == 0x02
 
ans[15] = a[8] ^ (a[15]<<1 |1) == 0x02
 
分组3:
Loop1:
v10 = (a[16] << 7 ) | (a[17]>> 1)
ans[16] = a[16] ^ (v10 << 1 | 1) == 0x7E
 
Loop2:
v10 = (a[17] << 6 ) | (a[18]>> 2)
ans[17] = a[16] ^ (v10 << 1 | 1) == 0x11
 
Loop3:
v10 = (a[18] << 5 ) | (a[19]>> 3)
ans[18] = a[16] ^ (v10 << 1 | 1) == 0x7A
 
Loop4:
v10 = (a[19] << 4 ) | (a[20]>> 4)
ans[19] = a[16] ^ (v10 << 1 | 1) == 0x62
 
Loop5:
v10 = (a[20] << 3 ) | (a[21]>> 5)
ans[20] = a[16] ^ (v10 << 1 | 1) == 0x0C
 
Loop6:
v10 = (a[21] << 2 ) | (a[22]>> 6)
ans[21] = a[16] ^ (v10 << 1 | 1) == 0x39
 
Loop7:
v10 = (a[22] <<1 ) | (a[23]>> 7)
ans[22] = a[16] ^ (v10 << 1 | 1) == 0x78
 
Loop8:
v10 = (a[23] << 0 ) | (a[24]>> 8)
ans[23] = a[16] ^ (v10 << 1 | 1) == 0x08
 
ans[23] = a[16] ^ (a[23] << 1 | 1) == 0x08

a[24]可以从 @6的那个循环中计算出来是 0x1A，对应的原输入是字母 Q，所以理论上我可以从第3个分组的最后一轮循环开始反推出所有的数据。我开始编码去反推，结果没有一个是符合要求的。我一开始怀疑是不是给的数据会在运行的时候被偷偷修改，但是很快我就发现并没有，程序中再没有别的地方引用这个数据。然后我又怀疑是不是自己对这个函数的分析有不到位的地方。然后我又重新分析一遍，还编码还原了这个过程，并和程序的运算结果作对比，确保不是我分析有问题。

反推不行我又尝试正推，正推不行我尝试爆破所有的数字组合，结果依然不行，最后我用了z3发现是无解的。。。就这样我都还没及时醒悟，还怀疑是不是自己z3代码写的有问题。现在想想真有点搞笑。从来不去怀疑题目会不会有坑。就这样反复修正自己的代码反复调试直到这道题目的时间结束为止。这时，群里有大佬说这个函数的确是无解的，这是个坑！

这时我“以手抚膺坐长叹”：是掉坑里了，并且还不断的往坑里钻。

所以说，条件6是坑，不可满足！这就要求 v20是小于等于 0的，也就确定了正确的输入总长度为 16字节。而我之前的分析中与正确结果就差了前三个字符，因为不确定前三个字符是 124的哪种组合，所以要根据校验和找到正确的结果。

最后正确结果应该是 421KCTF381654729

3.题解代码

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

138

139

140

141

142

143

144

145

146

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <algorithm>
using namespace std;
 
int g_tbl[256] = { 0 };
unsigned char ans[24] = { 0x0,0x0,0x9d,0x8,0x1d,0x0,0x68,0xc5,0x1f,0x3c,0x1c,0x11,0x1b,0x41,0x8,0x2,0x7e,0x11,0x7a,0x62,0xc,0x39,0x78,0x8 };
 
void GenGlobalTbl() {
    int v2 = 0;
    for (int i = 0; i < 256; i++)
    {
        v2 = i;
        for (int j = 0; j < 8; j++)
        {
            v2 = (v2 >> 1) ^ ((v2 & 1) != 0 ? 0xEDB88320 : 0);
        }
        g_tbl[i] = v2;
    }
}
 
bool Check2(int* a)
{
    int v23,v22=0,v37=0,v24,v36=1,v38=0,v21=0;
    do
    {
        v23 = a[v22] + 10 * v37;    // 循环9次
        v24 = v23 - 0x37373737;
        if (v23 <= 0x4B435445)
            v24 = v23;
        v37 = v24;
        if (v24 % v36)                    // 失败的分支
            return false;
        v21 = v38 + 1;
        v22 = v36;
        v38 = v21;
        ++v36;
    } while (v21 < 9);
    return true;
}
 
void prt(int arr[], int end)
{
    for (int i = 0; i < end; i++)
        printf("%d", arr[i]);
    printf("\n");
}
 
unsigned char CharToInt(char chr)
{
    if (chr >= 0x3A)
        return chr - 0x37;
    return chr - 0x30;
}
 
void perm(int arr[], int begin, int end)
{
    //递归终止条件：当只有一个数字做全排列的时候，则它的全排列就等于其本身。
    if (begin == end)
    {
        if (Check2(arr))
            prt(arr, 9);
        return;
    }
 
    for (int i = begin; i < end; i++)
    {
        swap(arr[begin], arr[i]);  //将第i个元素放到begin起始位置
        perm(arr, begin + 1, end); //将剩下的从begin+1到最后的元素进行全排列
        swap(arr[begin], arr[i]);  //将交换的数进行还原
    }
}
 
 
void BruteForce2()
{
    for (char c1 = '1'; c1 < 'z'; c1++)
        for (char c2 = '1'; c2 < 'z'; c2++)
            for (char c3 = '1'; c3 < 'z'; c3++)
                for (char c4 = '1'; c4 < 'z'; c4++)
                    if (
                        CharToInt(c1) == 20 &&
                        CharToInt(c2) == 12 &&
                        CharToInt(c3) == 29 &&
                        CharToInt(c4) == 15
                        )
                    {
                        printf("%c%c%c%c\n", c1, c2, c3, c4);
                        return;
                    }
}
 
int Check(char* a, int k) {
    char v10 = (CharToInt(a[k]) << (7 - k)) | (CharToInt(a[k+1]) >> (k + 1));
    char v1 = CharToInt(a[0]) ^ (v10 * 2 | 1);
    if (v1 == ans[k])
    {
        return 1;
    }
    return 0;
}
 
 
 
 
int CheckSum(char* a,int len)
{
    int sum = -1;
    for (int i = 0; i < len; i++)
        sum = g_tbl[(sum ^ a[i])&0xFF] ^ (sum >> 8);
    return ~sum;
}
 
void BruteForce1()
{
    char a[17] = "***KCTF381654729";
    for (char c1 = '0'; c1 <= 'z'; c1++)
        for (char c2 = '0'; c2 <= 'z'; c2++)
            for (char c3 = '0'; c3 <= 'z'; c3++)
            {
                a[0] = c1;
                a[1] = c2;
                a[2] = c3;
                if (
 
                    ((CharToInt(a[0]) ^ CharToInt(a[1]) ^ CharToInt(a[2])) == 7) && CheckSum(a,16) == 0xF52E0765
                    )
                {
                    printf("%s\n", a);
                    return;
                }
            }
 
}
 
int main() {
    GenGlobalTbl();
    int a[9] = { 1,2,3,4,5,6,7,8,9 };
    perm(a, 0, 9);
    BruteForce2();
    BruteForce1();
 
    system("pause");
    return 0;
}