查看原文
其他

阿里云CTF2024-暴力ENOTYOURWORLD题解

UserXCh 看雪学苑 2024-04-26
CTF authors, please don't put PhD level math in reverse engineering challenges. thank you.(好吧其实不是PhD level math)

题目附件:b3e67cd8a0f9ccc3bcfdf2deb8b0166dc6fb5fb745584426fb152e36c7abe56ehttps://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_v0flag_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 原创,转载请注明来自看雪社区



# 往期推荐

1、常见的固件加解密方式与D-Link固件解密实战分析

2、.NET 恶意软件 101:分析 .NET 可执行文件结构

3、CVE-2024-0015复现 (DubheCTF DayDream)

4、Unity的et热更新分析和补丁

5、Pwnable.kr 解题笔记

6、安卓逆向基础知识之动态调试及安卓逆向常规手段



球分享

球点赞

球在看



点击阅读原文查看更多

继续滑动看下一个
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存