阿里云CTF2024-暴力ENOTYOURWORLD题解

CTF authors, please don't put PhD level math in reverse engineering challenges. thank you.（好吧其实不是PhD level math）

题目附件：b3e67cd8a0f9ccc3bcfdf2deb8b0166dc6fb5fb745584426fb152e36c7abe56e（https://www.virustotal.com/gui/file/b3e67cd8a0f9ccc3bcfdf2deb8b0166dc6fb5fb745584426fb152e36c7abe56e）

一

脚本文件分析

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

import base64
import lzma

O = b"..."
with open("object", "wb") as f:
f.write(lzma.decompress(base64.a85decode(O)))

二

释放文件分析

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

strings object | grep GCC

得到结果如下。

GCC: (LoongArch GNU toolchain rc1.0) 8.3.0

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

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

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

$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

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

loongarch64-linux-gnu-objdump --disassemble object

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

loongarch64-linux-gnu-objdump --reloc object

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

三

重定位表分析

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

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代码转换如下。需要注意的是，操作数可能被覆写，因此需要特殊处理。

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代码源文件使用。

#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优化。命令如下。

gcc -O2 -o reloc reloc.c

四

还原代码分析

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

(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个校验为相邻两部分的拼接经过运算的结果。具体拼接方式如下。

((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)

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

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个校验为每个部分两次经过运算的结果。运算方式大致为杂凑算法。

五

数学？暴力！

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

◆需要求解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老年机也只需要万年就能全部枚举一遍。优化代码使用高性能计算机并采用并行计算，效率大幅提升。但这种方式可能无法让你在有限时间的比赛中提交答案。

看雪ID：UserXCh

https://bbs.kanxue.com/user-home-726188.htm

*本文为看雪论坛优秀文章，由 UserXCh 原创，转载请注明来自看雪社区

# 往期推荐

球分享

球点赞

球在看

点击阅读原文查看更多