阿里云CTF2024-暴力ENOTYOURWORLD题解

阿里云CTF2024-暴力ENOTYOURWORLD题解
2024-4-15 17:54:39 Author: mp.weixin.qq.com(查看原文) 阅读量:5 收藏

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 lzmaO = 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 csvsource = []
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 原创，转载请注明来自看雪社区

# 往期推荐

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

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

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

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

5、Pwnable.kr 解题笔记

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

球分享

球点赞

球在看

点击阅读原文查看更多

文章来源: https://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458550386&idx=1&sn=ef197d9dc41313d624d8e297d6cc5f9a&chksm=b18db0f886fa39eedca81d2ebee9e73e689d9db0bfdcb9831d8ebe4a759a5c55f98aff2a771b&scene=58&subscene=0#rd
如有侵权请联系:admin#unsafe.sh