TetCTF2024 rust_vm:Rust 自定义 VM 逆向,识别 8×8 位矩阵马步校验后用骑士巡游(Hamiltonian 路径)构造输入
ctf/reverse · verified
一句话结论
TetCTF2024 的 rust_vm 用 Rust 实现了一个自定义字节码 VM:主循环把输入按"低 4 位 x、高 4 位 y"逐个解释为棋盘坐标,要求每一步都是相对当前位置的合法马步(knight move)且不能落在已点亮的格子,最终点亮 8×8 棋盘全部 64 位(8 字节和 = 0x7f8)并停在 (7,2)。逆向时先识别 VM 的 opcode/寄存器/内存/栈布局、写 switch-case 反汇编器,再从字节码还原出"位矩阵 + 马步校验",最后用一条满足起点 (2,6)、终点 (7,2) 的骑士巡游路径(Hamiltonian 路径)编码成输入即可通关。
原理
- 自定义 VM 结构:程序分配一块内存
mem,输入放在mem头部;堆栈位于&mem + 0x1000,9 个 16 位寄存器位于&mem + 0x3000。指令以第一个字节为 opcode,长度可变(2/3/4 字节),主循环switch(opcode)分派。 - opcode 语义(由反汇编器恢复):
0 mov reg,reg、1 mov reg,imm16、2 add、3 sub、4/5 mov reg,BYTE/WORD [reg]、6 mul、7 div、8 mod、9 xor、10 not、11 and、12 or、13 shl、14 shr、15 push、16 pop、17 cmp、18 jmp、19 je、20 jne、21 jl、22 jge、23 final check、24/25 mov BYTE/WORD [reg],reg、26 call、27 ret、28 exit。条件跳转/相对寻址按低字节+高字节拼 16 位偏移。 - 反汇编器:因为指令少,直接用 Python
match opcode的 switch-case 解析code字节流即可,边解析边打印伪指令与地址标签,得到 5 个函数:0x168置位、0x18c取位、0xf1校验马步、0x1ac终局判定、主函数。 - 还原出的校验逻辑:
- 初始化在
mem[0xa0..0xa8)(8 字节 = 8×8 位矩阵)中置起点 bit:主函数先mov reg7,2; mov reg8,6; call 0x168,即起点 (x=2, y=6);0x168执行mem[0xa0+reg8] |= 1<<reg7。 0x70/0x80两张表存 8 组马步偏移(±1/±2 组合);0xf1要求输入坐标在 0..7 且(reg3+reg7, reg3'+reg8)命中某一组偏移——即合法马步。- 主循环逐字节读输入:
reg1 = b & 0xf(x)、reg2 = b >> 4(y);先0xf1校验是否合法马步,再0x18c检查目标位是否已为 1(重复访问则失败),然后0x168置位并把当前位置更新为 (x,y)。 - 终局判定:
0x1ac把mem[0xa0..0xa8)8 个字节求和,要求sum == 0x7f8(即每字节 0xff,64 位全亮),同时reg7==7 && reg8==2(终点 (7,2)),返回 1 即 WIN。 - 为什么是骑士巡游:64 个格子只能各走一次、每步必须是马步、走满全盘——这正是 8×8 棋盘上的 open knight's tour(Hamiltonian 路径),带固定起点/终点约束。找到一条路径后,把第 2..64 步的坐标按
(y<<4)|x编码成字节串发送即可。作者用现成的巡游序列手工对照棋盘,再脚本映射为输入。
触发条件
- CTF 逆向题/自定义字节码 VM 程序,输入从
mem头部读入、以位图/矩阵作为校验状态。 - 主循环存在 opcode 分派与可变长指令;无符号表/调试信息(Rust release)。
- 校验逻辑可还原为图上的路径问题(马步、迷宫、邻接矩阵等)。
利用步骤
- 静态定位主处理函数与
switch(opcode)分派,确认mem、寄存器区、栈区、ip 的布局与输入位置。 - 按 opcode 语义写 Python 反汇编器(switch-case + 地址标签),解析内嵌字节码
unk_4B170。 - 还原 5 个函数:置位、取位、马步校验、终局判定、主循环;把伪代码翻译成等价 Python 模拟器验证。
- 识别语义:8×8 位矩阵 + 8 组马步偏移 + 全位点亮 + 固定终点 → 骑士巡游;起点由主函数
reg7=2, reg8=6确定。 - 求一条从 (2,6) 出发、覆盖 64 格、终点为 (7,2) 的马步路径(可用已知巡游序列映射、Warnsdorff 启发式或带约束的 DFS/ILP)。
- 按第 2..64 步顺序生成字节
(y<<4)|x,作为输入发送;收到Seem correct. Here is your flag即成功。
PoC
from pwn import *
# 已求得的巡游顺序:数字 1..64 表示访问次序,矩阵下标即棋盘坐标
chess = [
[39,22,59,8,35,26,63,10],
[58,7,38,23,62,9,34,27],
[21,40,5,60,25,36,11,64],
[6,57,24,37,12,61,28,33],
[41,20,53,4,45,32,51,14],
[56,3,44,17,52,13,48,29],
[19,42,1,54,31,46,15,50],
[2,55,18,43,16,49,30,47],
]
flat = [v for row in chess for v in row]
to_send = []
for i in range(2, 65): # 第 1 步是起点 (2,6),不发送
pos = flat.index(i)
x, y = pos % 8, pos // 8
to_send.append((y << 4) | x) # 高 4 位 y,低 4 位 x
io = remote('139.162.1.95', 31337)
io.recv()
io.sendline(bytes(to_send))
io.interactive()
# Seem correct. Here is your flag
# TetCTF{TheRe_i$_4_KNighT_iN$iD3_VirTu41_w0RLd}
变体与关联
- 同类 VM 逆向:[[ctf-reverse-custom-stack-vm-bytecode-constraint-recovery]](栈式 VM + 跳转表 + 逐字符约束)、[[ctf-reverse-custom-python-vm-bytecode-disassembler]](Python VM 反汇编 + 变换逆推)、[[ctf-reverse-vm-opcode-low2-format-high6-dispatch]](opcode 位域分派)、[[code-analysis-reverse-vm-binary-ninja-custom-isa-architecture-plugin]](Binary Ninja 自定义 ISA 插件)。
- 变体:位图校验换成迷宫/邻接矩阵/数独约束时,同样是"还原状态转移 + 图搜索";带固定起终点时 BFS/DFS 可能找不到,需 Warnsdorff、回溯或 ILP/CP-SAT。
- 变体:Rust VM 若把 opcode 表加密或字节码运行时解密,先动态 dump 解密后的字节码再写反汇编器。
- 边界:若校验加入哈希/真实密码学或路径不唯一且无法判定,需另找约束;本题是 open tour,路径可手工/离线求解。
检测与防御
- CTF/验证:用还原的 Python 模拟器正向跑输入,应看到 64 位全亮且终局返回 1;远程返回 flag 即路径正确。
- 防御:客户端校验不能作为安全边界;自定义 VM 只提高逆向成本,密钥/授权应放服务端。
- 检测信号:二进制存在
Unknown opscode/called Result::unwrap() on an Err value等 Rust VM 特征串;大块字节码常量;主循环switch分派 + 可变长指令。