DubheCTF-Destination&Moon

前言

第一次给这么大的比赛出题，一想到能够折磨这么多人，就觉得浑身舒畅，虽然看这个解出数量并没有折磨到任何人。。。

题目在此

源码在此（屎山罢了，你不会想看的）

Destination

程序加入的反调可以在41E000-41E138里面找到，全都改成0即可绕过。

在main函数中可以找到如下代码:

程序手动注册了异常处理函数sub_4140D7，但是这个函数夹带了大量的跳转语句和花指令，可以使用以下idc脚本去花：

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
#include <idc.idc>

static main()
{
    auto last_eip;
    auto eip = 0x4140D7;
    auto offset;
    auto sum = 1;
    auto just_jump = 0;
    while(Byte(eip) != 0xC3)
    {
        if(Byte(eip) == 0xE8 && Byte(eip+1) == 0x00 && Byte(eip+1) == 0x00 && Byte(eip+1) == 0x00 && Byte(eip+1) == 0x00)
        {
            PatchByte(eip + 0, 0x90);
            PatchByte(eip + 1, 0x90);
            PatchByte(eip + 2, 0x90);
            PatchByte(eip + 3, 0x90);
            PatchByte(eip + 4, 0x90);
            PatchByte(eip + 5, 0x90);
            PatchByte(eip + 6, 0x90);
            PatchByte(eip + 7, 0x90);
            PatchByte(eip + 8, 0x90);
            PatchByte(eip + 9, 0x90);
            eip = eip + 10;
            continue;
        }
        else if(Byte(eip) == 0xE9 && just_jump == 0)
        {
            offset = Byte(eip+1);
            offset = Byte(eip+2) * 256 + offset;
            offset = Byte(eip+3) * 256 * 256 + offset;
            offset = Byte(eip+4) * 256 * 256 * 256 + offset;
            eip = eip + offset;
            eip = eip + 5;
            eip = eip & 0xffffffff;
            print(eip);
            sum = sum + 1;
            just_jump = 1;
            continue;
        }
        else if(Byte(eip) == 0x0F && Byte(eip+1) == 0x84 && just_jump == 0)
        {
            last_eip = eip;
            offset = Byte(eip+2);
            offset = Byte(eip+3) * 256 + offset;
            offset = Byte(eip+4) * 256 * 256 + offset;
            offset = Byte(eip+5) * 256 * 256 * 256 + offset;
            eip = eip + offset;
            eip = eip + 6;
            eip = eip & 0xffffffff;
            print(eip);
            sum = sum + 1;
            just_jump = 1;
            PatchByte(last_eip, 0x90);
            PatchByte(last_eip+1, 0xE9);
            continue;
        }
        else if(Byte(eip) == 0xEB && just_jump == 0)
        {
            offset = Byte(eip+1);
            eip = eip + offset;
            eip = eip + 2;
            print(eip);
            sum = sum + 1;
            just_jump = 1;
            continue;
        }
        else if(Byte(eip) == 0x74 && just_jump == 0)
        {
            last_eip = eip;
            offset = Byte(eip+1);
            eip = eip + offset;
            eip = eip + 2;
            print(eip);
            sum = sum + 1;
            just_jump = 1;
            PatchByte(last_eip, 0xEB);
            continue;
        }
        eip = eip + 1;
        just_jump = 0;
    }
    print(sum);
    return 0;
}

此后，这个函数可以恢复成这样：

由于SEH的展开操作，这个自己注册的函数会被执行两次。详见这篇文章。

接下来程序采用天堂之门技术，让32位程序执行64位代码。jmp far ptr loc_4142A7应当理解为jmp 0x33:413F77，即跳转至0x413F77同时将cs寄存器由0x23转变为0x33。将此段代码dump下来喂给64 位IDA即可得到：

其中0x4234A8即为输入。汇编代码最后的push 23h; push 4179F3h; retfq;在跳转回0x4179F3的时 候又将cs寄存器转为了0x23，此后执行32位代码。据此，我们可以写出解题脚本：

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
#include <iostream>
#include <cstring>

using namespace std;

#define DELTA 0xa4b46062
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

int main()
{
    // unsigned char flag[100] = {67, 149, 84, 158, 72, 179, 124, 94, 47, 74, 168, 217, 222, 153, 235, 133, 132, 88, 130, 182, 161, 78, 247, 196, 138, 130, 177, 34, 150, 114, 13, 41, 115, 228, 142, 25, 41, 181, 85, 150, 106, 25, 172, 56, 54, 98, 43, 25};
    unsigned char flag[100] = {214, 250, 144, 167, 119, 162, 200, 232, 250, 132, 3, 207, 215, 127, 108, 46, 139, 150, 51, 109, 39, 194, 87, 91, 94, 166, 60, 101, 252, 241, 198, 133, 119, 37, 243, 225, 118, 174, 215, 212, 196, 109, 175, 63, 140, 157, 89, 13};
    unsigned int f;
    int i, j;
    for(i = 0; i < 12; i++)
    {
        f = *((unsigned int*)flag + i);
        for(j = 0; j < 32; j++)
        {
            if(f & 1)
            {
                f ^= 0x84a6972f;
                f >>= 1;
                f |= 0x80000000;
            }
            else
            {
                f >>= 1;
                f &= 0x7fffffff;
            }
        }
        *((unsigned int*)flag + i) = f;
    }
    unsigned int rounds, sum, e, p, y, z;
    unsigned int key[4] = {0x6b0e7a6b, 0xd13011ee, 0xa7e12c6d, 0xc199aca6};

    rounds = 0x32;
    sum = rounds * DELTA;
    y = ((unsigned int*)flag)[0];
    do
    {
        e = (sum >> 2) & 3;
        for (p = 11; p > 0; p--)
        {
            z = ((unsigned int*)flag)[p - 1];
            y = ((unsigned int*)flag)[p] -= MX;
        }
        z = ((unsigned int*)flag)[11];
        y = ((unsigned int*)flag)[0] -= MX;
        sum -= DELTA;
    }
    while (--rounds);

    rounds = 0x32;
    sum = rounds * DELTA;
    y = ((unsigned int*)flag)[0];
    do
    {
        e = (sum >> 2) & 3;
        for (p = 11; p > 0; p--)
        {
            z = ((unsigned int*)flag)[p - 1];
            y = ((unsigned int*)flag)[p] -= MX;
        }
        z = ((unsigned int*)flag)[11];
        y = ((unsigned int*)flag)[0] -= MX;
        sum -= DELTA;
    }
    while (--rounds);

    for(i = 0; i < 48; i++)
    {
        printf("%c", flag[i]);
    }
    return 0;
}

运行得出flag：DubheCTF{82e1e3f8-85fe469f-8499dd48-466a9d60}

Moon

程序存在大量的大数运算，所有数据全都是反着存储的。主要逻辑集中在sub_140001B20中：

应当可以看出程序中有这么一个结构体：

1
2
3
4
struct BigNumber{
	char* data;
	int len;
};

在主要逻辑函数中，可以发现：

其中sub_140001780是高精度快速幂，sub_140001000是高精度乘法，sub_140001260是高精度除法，xmmword_140007848是一个大质数，Src是做除法时生成的余数。最后可以得到程序在干这么个事：

把这一坨喂给一个密码手，可以得到：

由此可知，程序在试图求解：

x2≡amod  px^2 \equiv a \mod p

其中a位输入，p给定，判断解出的x是否与预设的值相同。据此写出解题代码：

1
2
3
x = 885929268745208437773737031796868079277836491798608104263226417228443603006843430266722004055919359990
p = 1537131588382913092665966115381275601741897676956736016043055688971156548045659189201332511868437849089
print(pow(x, 2, p))

输出的md5值即为flag：DubheCTF{c58a378bec96b92d8e19b2e7dbddc4ff}

如果没有发现这一点也没有关系，从x[i]逆推到x[i+1]无非就j=0和j=1两种情况，从x[0]推到x[9]总共也就282 ^ 8种情况，我们完全可以爆破。以下是S1uM4i战队的代码：

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
x = 885929268745208437773737031796868079277836491798608104263226417228443603006843430266722004055919359990
p = 1537131588382913092665966115381275601741897676956736016043055688971156548045659189201332511868437849089
rnd = 535687859422589012977141675826129236269925277717894712488225104574807190354008307256942078237560832125
def check(input_num):
    input_num_inv = pow(input_num, p - 2, p)
    nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, pow(input_num, (((p - 1) // 1024) + 1) // 2, p)]
    for i in range(9, 0, -1):
        v30 = pow(nums[i] * nums[i] * input_num_inv, pow(2, i - 1), p)
        if v30 == 1:
            nums[i - 1] = nums[i]
        else:
            assert v30 == p - 1
            nums[i - 1] = nums[i] * pow(rnd, pow(2, 9-i), p) % p
    return nums[0] == x

for t in range(0, 257):
    c = x
    for i in range(9, 0, -1):
        r = pow(rnd, pow(2, 9 - i), p)
        rv = pow(r, p - 2, p)
        if (t >> (i-1)) & 1:
            c = c * rv % p
    c = c * c # P-1 // 1024 = 1, +1 = x, /2 = pow2, then c=c*c
    c = c % p # 第⼀次算出来不对，模个p符合100位输⼊要求
    try:
        if check(c):
            print(c)
    except:
        pass

后记

天堂之门之后的部分写的还是太简单了。虽然我特意使用的rdi，rsi，r14，r15这四个寄存器，让它在32位里面看起来是edi和esi两个寄存器，试图混淆选手的视听，但是依旧有队伍靠着剩余的代码猜了出来。下次一定要上自己魔改的乱七八糟的算法。

本来想着Moon出成这么一个数论的样子会被骂惨了的，但是好像这次比赛的web和misc更加逆天，再加上总共就256种路径，可以爆破，也就没有什么人骂我这道题了，诶嘿~

某种意义上这也算是载入历史了，往外就说”这是XCTF的历年真题"！