• 阿里云CTF2024暴力ENOTYOURWORLD题解

阿里云CTF2024暴力ENOTYOURWORLD题解

0x00 前言

CTF authors, please don't put PhD level math in reverse engineering challenges. thank you.

（好吧其实不是PhD level math，逃～）

题目附件：b3e67cd8a0f9ccc3bcfdf2deb8b0166dc6fb5fb745584426fb152e36c7abe56e

0x01 脚本文件分析

分析附件，不难发现为脚本文件。脚本文件执行Base85解码和LZMA解压释放文件。编写Python代码提取如下（节约篇幅，有删减）。

1
2
3
4
5
6
import base64
import lzma
 
O = b"..."
with open("object", "wb") as f:
    f.write(lzma.decompress(base64.a85decode(O)))

0x02 释放文件分析

常规步骤，检查字符串。执行命令如下。

1
strings object | grep GCC

得到结果如下。

1
GCC: (LoongArch GNU toolchain rc1.0) 8.3.0

自然需要部署工具环境。执行命令如下。

1
2
3
4
5
6
7
8
wget http://ftp.loongnix.cn/toolchain/gcc/release/loongarch/gcc8/toolchain-loongarch64-linux-gnu-cross-830-rc1.0-2022-04-22.tar.xz
tar -xf toolchain-loongarch64-linux-gnu-cross-830-rc1.0-2022-04-22.tar.xz
pushd toolchain-loongarch64-linux-gnu-cross-830-rc1.0-2022-04-22
export TC_HOME=`pwd`
pushd bin
export PATH=$PATH:`pwd`
popd
popd

根据脚本文件，不难给出可用的链接命令如下。不妨假设所有链接定义符号为零。

1
$TC_HOME/loongarch64-linux-gnu/bin/ld -plugin $TC_HOME/libexec/gcc/loongarch64-linux-gnu/8.3.0/liblto_plugin.so -plugin-opt=$TC_HOME/libexec/gcc/loongarch64-linux-gnu/8.3.0/lto-wrapper -plugin-opt=-fresolution=~/resolution.res -plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lgcc_eh -plugin-opt=-pass-through=-lc --sysroot=$TC_HOME/sysroot -m elf64loongarch -static -o ~/output $TC_HOME/sysroot/lib64/crt1.o $TC_HOME/sysroot/lib64/crti.o $TC_HOME/lib/gcc/loongarch64-linux-gnu/8.3.0/crtbeginT.o -L$TC_HOME/lib/gcc/loongarch64-linux-gnu/8.3.0 -L$TC_HOME/lib/gcc -L$TC_HOME/sysroot/lib64 -L$TC_HOME/loongarch64-linux-gnu/lib -L$TC_HOME/sysroot/lib ~/object --defsym=v0=0 --defsym=v1=0 --defsym=v2=0 --defsym=v3=0 --defsym=v4=0 --defsym=v5=0 --defsym=v6=0 --defsym=v7=0 --start-group -lgcc -lgcc_eh -lc --end-group $TC_HOME/lib/gcc/loongarch64-linux-gnu/8.3.0/crtend.o $TC_HOME/sysroot/lib64/crtn.o

常规步骤，检查反汇编。执行命令如下。

1
loongarch64-linux-gnu-objdump --disassemble object

不难发现直接提示错误，无额外逻辑。结合链接定义符号，怀疑重定位表覆写。检查重定位。执行命令如下。

1
loongarch64-linux-gnu-objdump --reloc object

关注到.rela.text.这一部分内容过长，不符合常规。不难将这一部分导出为CSV表格文件。

0x03 重定位表分析

不妨使用Frida计算文件偏移和有效地址之间的关系（JavaScript脚本略，可通过内存布局得到）。

1
frida -f $TC_HOME/loongarch64-linux-gnu/bin/ld -- -plugin $TC_HOME/libexec/gcc/loongarch64-linux-gnu/8.3.0/liblto_plugin.so -plugin-opt=$TC_HOME/libexec/gcc/loongarch64-linux-gnu/8.3.0/lto-wrapper -plugin-opt=-fresolution=~/resolution.res -plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lgcc_eh -plugin-opt=-pass-through=-lc --sysroot=$TC_HOME/sysroot -m elf64loongarch -static -o ~/output $TC_HOME/sysroot/lib64/crt1.o $TC_HOME/sysroot/lib64/crti.o $TC_HOME/lib/gcc/loongarch64-linux-gnu/8.3.0/crtbeginT.o -L$TC_HOME/lib/gcc/loongarch64-linux-gnu/8.3.0 -L$TC_HOME/lib/gcc -L$TC_HOME/sysroot/lib64 -L$TC_HOME/loongarch64-linux-gnu/lib -L$TC_HOME/sysroot/lib ~/object --defsym=v0=0 --defsym=v1=0 --defsym=v2=0 --defsym=v3=0 --defsym=v4=0 --defsym=v5=0 --defsym=v6=0 --defsym=v7=0 --start-group -lgcc -lgcc_eh -lc --end-group $TC_HOME/lib/gcc/loongarch64-linux-gnu/8.3.0/crtend.o $TC_HOME/sysroot/lib64/crtn.o

得到文件偏移和有效地址偏差mem_delta = 0x01FFFBB5。此外另从ELF结构读取文件偏移reloca_foff = 0x0000045B和大小reloca_size = 0x00245940。

LARCH重定位涉及基于栈的虚拟机。对于LARCH虚拟机，不用慌张，相较于传统VM逆向题目，各个操作功能及其参数是已知的。不妨转换为C代码并使用编译器优化。编写Python代码转换如下。需要注意的是，操作数可能被覆写，因此需要特殊处理。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
import csv
 
source = []
 
mem_delta = 0x01FFFBB5
reloca_foff = 0x0000045B
reloca_size = 0x00245940
reloca_start = mem_delta + reloca_foff
reloca_end = reloca_start + reloca_size
value_addrs = []
addend_writable_addrs = []
for i in range(reloca_start, reloca_end, 24):
    value_addrs.append(i + 16)
    addend_writable_addrs.append(i + 16)
    addend_writable_addrs.append(i + 20)
 
with open("reloc.csv") as f:
    c = csv.reader(f)
    c = list(c)
 
assert len(c) == len(value_addrs)
 
modified_value_addrs = []
 
SP = 0
 
for (OFFSET, TYPE, VALUE), VALUE_ADDR in zip(c, value_addrs):
    if TYPE in ["R_LARCH_SOP_PUSH_PCREL", "R_LARCH_SOP_PUSH_PLT_PCREL"]:
        SP += 1
    elif TYPE == "R_LARCH_SOP_PUSH_ABSOLUTE":
        if VALUE.startswith("*ABS*"):
            t1 = VALUE_ADDR
            t2 = VALUE_ADDR + 4
            lpart = t1 in modified_value_addrs
            rpart = t2 in modified_value_addrs
            if lpart or rpart:
                assert lpart and rpart
                source.append(
                    f"STK_U64_{SP} = ((uint64_t)LOC_U32_{t2:08X} << 32) | LOC_U32_{t1:08X};"
                )
                SP += 1
            else:
                if VALUE == "*ABS*":
                    source.append(f"STK_U64_{SP} = 0;")
                    SP += 1
                else:
                    source.append(f"STK_U64_{SP} = {VALUE[5:]};")
                    SP += 1
        elif VALUE in ["v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7"]:
            source.append(f"STK_U64_{SP} = flag_{VALUE};")
            SP += 1
        else:
            assert False, f"Unknown VALUE {VALUE}"
    elif TYPE == "R_LARCH_SOP_SR":
        SP -= 1
        opr2 = f"STK_U64_{SP}"
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1} >> {opr2};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_SL":
        SP -= 1
        opr2 = f"STK_U64_{SP}"
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1} << {opr2};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_SUB":
        SP -= 1
        opr2 = f"STK_U64_{SP}"
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1} - {opr2};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_PUSH_DUP":
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1};")
        SP += 1
        source.append(f"STK_U64_{SP} = {opr1};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_AND":
        SP -= 1
        opr2 = f"STK_U64_{SP}"
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1} & {opr2};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_ADD":
        SP -= 1
        opr2 = f"STK_U64_{SP}"
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1} + {opr2};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_IF_ELSE":
        SP -= 1
        opr3 = f"STK_U64_{SP}"
        SP -= 1
        opr2 = f"STK_U64_{SP}"
        SP -= 1
        opr1 = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = {opr1} ? {opr2} : {opr3};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_NOT":
        SP -= 1
        v = f"STK_U64_{SP}"
        source.append(f"STK_U64_{SP} = !{v};")
        SP += 1
    elif TYPE == "R_LARCH_SOP_ASSERT":
        SP -= 1
        v = f"STK_U64_{SP}"
        source.append(f"assert({v});")
    elif TYPE in [
        "R_LARCH_SOP_POP_32_S_5_20",
        "R_LARCH_SOP_POP_32_S_10_12",
        "R_LARCH_SOP_POP_32_S_0_10_10_16_S2",
    ]:
        SP -= 1
    elif TYPE == "R_LARCH_SOP_POP_32_U":
        t = int(OFFSET, 16)
        if reloca_start <= t < reloca_end:
            assert t in addend_writable_addrs
            modified_value_addrs.append(t)
            SP -= 1
            v = f"STK_U64_{SP}"
            source.append(f"LOC_U32_{t:08X} = {v} & 0xffffffff;")
        else:
            SP -= 1
    elif TYPE == "R_LARCH_ADD32":
        pass
    else:
        assert False, f"Unknown TYPE {TYPE}"
 
for i in range(4):
    print(f"uint64_t STK_U64_{i} = 0;")
print()
for i in modified_value_addrs:
    print(f"uint32_t LOC_U32_{i:08X};")
print()
for i in source:
    print(i)

执行脚本，生成C代码头文件。不妨配合以下C代码源文件使用。

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
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
uint64_t v0;
uint64_t v1;
uint64_t v2;
uint64_t v3;
uint64_t v4;
uint64_t v5;
uint64_t v6;
uint64_t v7;
char buf[80];
void func()
{
#include "reloc.h"
}
int main(int argc, const char *argv[])
{
    scanf("%s", buf);
    v0 = ((uint64_t *)buf)[0];
    v1 = ((uint64_t *)buf)[1];
    v2 = ((uint64_t *)buf)[2];
    v3 = ((uint64_t *)buf)[3];
    v4 = ((uint64_t *)buf)[4];
    v5 = ((uint64_t *)buf)[5];
    v6 = ((uint64_t *)buf)[6];
    v7 = ((uint64_t *)buf)[7];
    func();
    return 0;
}

不妨使用GCC编译并启用O2优化。命令如下。

1
gcc -O2 -o reloc reloc.c

0x04 还原代码分析

此时我们已经将虚拟代码还原。使用常规工具反编译。关注到如下片段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(chk_0 != 0xF2EC726FD6F42DBBLL)
       + (chk_1 != 0x21723CFAFE557F5BLL)
       + (chk_2 != 0x17F625C5B017ED4ALL)
       + (chk_3 != 0xACC2F6A815E0ABBELL)
       + (chk_4 != 0x6FE42391AD85770FLL)
       + (chk_5 != 0x4AFDC5B82BC36032LL)
       + (chk_6 != 0xF513E6C7E2C54367LL)
       + (chk_7 != 0x8B90A1353119C9FBLL)
       + (chk_8 != 0x141196587DA3CFD3LL)
       + (chk_9 != 0x6D4A289D687EE32LL)
       + (chk_10 != 0xAD6D362D3965DCA8LL)
       + (chk_11 != 0x4FF07F315026EA3FLL)
       + (chk_12 != 0x1BE1E40658C8F166LL)
       + (chk_13 != 0xE761EC01EF80841FLL)
       + (chk_14 != 0x5FAF914221BB1C6CLL)
       + (chk_15 != 0xEE40D4E4B790E50BLL)
       + (chk_16 != 0x7C7BA53DDE44DA46LL)
       + (chk_17 != 0x4861E5170730111BLL)
       + (chk_18 != 0x8E1396D18B199C64LL)
       + (chk_19 != 0x2B65B265EE427F7CLL) == 0

不妨发现为核心比较。

进一步观察，发现其中4个校验为相邻两部分的拼接经过运算的结果。具体拼接方式如下。

1
2
3
4
((unsigned __int64)flag_v0 >> 32) + (flag_v1 << 32)
((unsigned __int64)flag_v2 >> 32) + (flag_v3 << 32)
((unsigned __int64)flag_v4 >> 32) + (flag_v5 << 32)
((unsigned __int64)flag_v6 >> 32) + (flag_v7 << 32)

运算方式如下（节约篇幅，有删减）。大致为数域运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
v0 = ((unsigned __int64)flag_v6 >> 32) + (flag_v7 << 32);
v1 = BYTE4(flag_v6) & 1;
v2 = 2 * v0;
v3 = 0LL;
if ( flag_v6 & 0x100000000LL )
  v3 = ((unsigned __int64)flag_v6 >> 32) + (flag_v7 << 32);
v138 = v0 >> 63;
if ( (v0 & 0x8000000000000000LL) != 0LL )
  v2 = v2 - 6851306870693981165LL - 2 * (v2 & 0xA0EB44B36D179413LL);
/* ... */
if ( v138 )
  v3 = v3 + v73 - 2 * (v73 & v3);
v74 = 2 * v3;
if ( flag_v6 & 0x100000000LL )
  v1 = v3;
if ( v3 < 0 )
  v74 = v74 - 6851306870693981165LL - 2 * (v74 & 0xA0EB44B36D179413LL);
/* ... */
if ( v138 )
  v1 = v1 + v136 - 2 * (v136 & v1);

另外16个校验为每个部分两次经过运算的结果。运算方式大致为杂凑算法。

0x05 数学？暴力！

让我们来总结一下手里的东西。

  • 需要求解8个flag_v0到flag_v7（8字节，64位）。
  • 每个flag_v?（8字节，64位）拥有2个杂凑算法结果（8字节，64位）。
  • 偶数时前一个flag_v?的后半部分和后一个flag_v(?+1)的前半部分拼接（8字节，64位）拥有1个数域运算结果（8字节，64位）。

不妨猜测：按照正常的逻辑，数域运算应当是可解的。我们应该得到每个flag_v?的一半部分（4字节，32位），再暴力枚举剩余一半部分（4字节，32位）。

但是……参见“0x00 前言”。看不懂数学怎么办？z3？（数域运算大概率是非对称的，约束求解大概率是困难的）暴力！

由于直接暴力枚举杂凑算法开销过大，不妨枚举数域运算。然后再按照猜测的剩余逻辑求解。相信我，经过测试，不做优化的情况下单核单线程的CCF老年机也只需要万年就能全部枚举一遍。优化代码使用高性能计算机并采用并行计算，效率大幅提升。

0x06 后记

但是为了节约用电，请不要这么做。不仅如此，这种方式可能无法让你在有限时间的比赛中提交答案。（狗头）

最新回复：
wd2711 2024-04-01 11:17:34
太帅了