21kctf秋

第二题迷失丛林

摘要

这是个有点脑洞的题，通过一个0x100字节的表构建一个0x200字节的表，再根据0x200字节的表构造一个0x10000字节的表，然后检查0x10000的表。接着是一个二叉树，处理输入后与明文字符串做比较。

0x100字节的表前8字节由输入决定，如果直接爆破是2的64次方，但实际上这个表中0~255出现的次数都只有一次，所以爆破减少到8的8次方

后面的二叉树依次处理输入的后半段，单个字节爆破是2的8次方

初步分析

查找字符串TryAgain会发现旁边有个GoodJob~

然后查看字符串交叉引用，找到目标函数在0x401270（TryAgain）

0x401270会检测输入长度，然后做一些初始化，进入GoodJob~所在的0x401580

输入的字符串长度是32

sub_4014A0是个16进程字符串转整形的函数，且字符串是小端存储的

校验1

0x100的那个表是根据输入前半段构造的，与后半段无关

首先爆破0x100的那个表，直接复制反编译代码，然后用个dfs爆即可，这里没有做剪枝，会慢一点：

bool Gen()
{
    memset(mm10000, 0, 0x10000);
 
    byte sums[4];
    *(dword*)sums = 0;
    int idxNext = 1;
    byte* p10000 = mm10000;
    do {
        mm200[0] = mm[idxNext - 1];                 // Initmm200
        mm200[1] = idxNext;
        byte*  p200a = mm200;
        int* ppow = pown1s;
        byte* p200b = &mm200[pown1s[0]];                  // p200b = &mm200[2];
        do                                          // Setmm200
        {
            int p = *ppow;                                // p = 2^(i+1) = [2, 4, 8, 0x10, ...]
            if (*ppow > 0) {
                do {
                    byte* p200c = p200b + 1;
                    *(p200c - 1) = mm[(unsigned __int8)*p200a];// *(p200b) = mm[*p200a]
                    *p200c = *p200a + 1;                  // *(p200b + 1) = *p200a + 1
                    p200b = p200c + 1;                    // p200b += 2
                    ++p200a;
                    --p;
                } while (p);
            }
            ++ppow;
        } while ((int)ppow < (int)&pown1s[7]);      // 254 times
        int v8 = 256;                                   // Setmm10000
        do {
            ++p10000[(unsigned __int8)*p200a++];
            --v8;
        } while (v8);
        ++idxNext;
        p10000 += 256;
    } while (idxNext - 1 < 256);
    byte* v9 = &mm10000[40];
    int i_step = 256;
    do {
        if (*(v9 - 40))                           // 0
            ++sums[0];
        if (*(v9 - 26))                           // 14
            ++sums[1];
        if (*v9)                                  // 40
            ++sums[2];
        if (v9[39])                               // 79
            ++sums[3];
        v9 += 256;
        --i_step;
    } while (i_step);
    // sums[0] == (char)0xA9 && sums[1] == (char)0xAC && sums[2] == (char)0xA7 && sums[3] > 0xC8u
    if (sums[0] == 0xA9 && sums[1] == 0xAC && sums[2] == 0xA7) {
        cout << "sums[3]" << (int)sums[3] << endl;
        return true;
    }
    else {
        // cout << (int)sums[0] << " " << (int)sums[1] << " " << (int)sums[2] << " " << (int)sums[3] << endl;
        return false;
    }
}
 
void dfs(int layer)
{
    if (layer == 8) {
        if (Gen()) {
            for (int i = 0; i < 8; i++)
                cout << (int)mm[i] << " ";
            cout << endl;
        }
        return;
    }
 
    for (int i = 0; i < 8; i++) {
        if (flag[i])
            continue;
        mm[layer] = prob[i];
        flag[i] = 1;
        dfs(layer + 1);
        flag[i] = 0;
    }
}

剪枝的思路是提前判断代码中sums的值，如果sums+剩余次数小于目标值或sums大于目标值则可以提前退出

这段代码实际上是根据0x100生成一个0x200的表（实际上是0x1fe），再统计0x200表后0x100项中4个数字的出现次数，如果出现就在sums中记录，最后检查sums

下面是化简过后的代码：

for i in range(256):
    mm10000[0] = 0
    mm10000[14] = 0
    mm10000[40] = 0
    mm10000[79] = 0
 
    # mm200[0:510] = f()
    mm200[0] = mm[i]
    mm200[1] = i + 1
 
    for j in range(1, 255): # j-1 = [0, 254)
        mm200[j*2] = mm[mm200[j-1]]
        mm200[j*2+1] = mm200[j-1] + 1
 
    # mm10000[i*256+0:(i+1)*256] = f(mm200[254:510])
    for j in range(254, 254 + 256):
        mm10000[mm200[j]] = 1 # ++p10000[*p200a++];
 
    if mm10000[0] != 0 :
        sums[0] += 1
    if mm10000[14] != 0 :
        sums[1] += 1
    if mm10000[40] != 0 :
        sums[2] += 1
    if mm10000[79] != 0 :
        sums[3] += 1

校验2

检查完sums后，0x100那个表会发生一些变化，这个变化只与表自身的值有关，所以在通过校验1得到正确的值后，动态调试dump出变化后的结果即可

接着有一个两层循环，化简代码后如下：

# a2是输入后半段
 
resultStr = [mm[i] for i in range(8)]
 
for i_bit in range(0, 8):
    for i_ord in range(0, 8):
        if((a2[i_ord] & 1) != 0): # if a2[i2] 最低位为1
            resultStr[i_ord] += 1;
        else:
            resultStr[i_ord] = mm[resultStr[i_ord]];
        a2[i_ord] >>= 1;
 
i_bit = 8
--resultStr[0];
--resultStr[7];
 
if resultStr == 'GoodJob~':
    print('GoodJob~')

易得出前面两个循环结束后resultStr=b'HoodJob\x7f'

而那两个循环可以通过如下代码爆破：

bool Check(byte b, byte target, int step)
{
    if (step == 8) {
        if (b == target) {
            byte p = 0;
            for (int i = 7; i >= 0; i--) {
                p <<= 1;
                p |= path[i];
            }
            cout << (int)p << ", ";
 
            return true;
        }
        return false;
    }
 
    path[step] = 0;
    if (Check(mm2[b], target, step + 1))
        return true;
 
    path[step] = 1;
    if (Check(b+1, target, step + 1))
        return true;
 
    return false;
}