首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[原创] KCTF2022——第二题 末日邀请之论如何掉坑里
发表于: 2022-5-14 14:59 8257

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

brucy 活跃值
2022-5-14 14:59
8257

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

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

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

input[6] == 15

不难得出原输入应该是 KCTF

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

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

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

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

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

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

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

最后正确结果应该是 421KCTF381654729

分组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
分组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
 
 
 
 
#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;
}
#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;
    }
}

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

最后于 2022-5-14 15:28 被brucy编辑 ，原因： 补充缺失的内容
收藏
免费 ・3
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//