LinuxChal 多层逆向:花指令修复 + XOR 0x27 内嵌 ELF + 魔改 RC4 数组 + z3 解 NAND 电路
ctf/reverse · verified
一句话结论
chal 先用大量 00 花指令干扰反汇编(把 00 改 90 即可恢复),运行时起线程加载一段每字节 XOR 0x27 的内嵌 ELF;第二层 ELF 同样有花指令,找到 key 字符串与 24 字节密文后,用魔改 RC4 解出一个大数组 v194,其每 3 字节是一条 mem[c] = ~(mem[b] & mem[a]) 的 NAND 电路;用 z3 对 24 字节 flag 建模、按 0x3F0 条三元组执行 NAND、约束前 24 字节等于密文,即可解出 flag。
原理
- 花指令:
chal中大量00 00字节让 IDA 反汇编错位;把这些00改成90(NOP)后,函数边界与指令流恢复。两段 ELF 都用了同类花指令。 - 内嵌 ELF:程序创建线程并加载一段数据;交叉引用发现数据被逐字节 XOR 0x27,提取后 XOR 回来得到合法 ELF(
\x7fELF头),再用 IDA 分析第二层。 - 魔改 RC4:第二层里有一个大数组和 key 字符串
KeyKEyKeYKEykEYKEY!@#$%^;数组经过魔改 RC4 解密后得到v194。具体魔改点(S 盒初始化/PRGA 细节)需按反编译实现,原文通过 Linux 远程调试直接 dump 解密后的v194。 - NAND 电路:
v194每 3 字节(a,b,c)表示mem[c] = ~(mem[b] & mem[a])(8 位按位 NAND);循环0x3F0次,相当于一个由 1008 个 NAND 门组成的电路。 - 内存布局:
mem[0..0x17]是 24 字节 flag(未知),mem[0x18..0x2F]是固定尾串KeyKEyKeYKEykEYKEY!@#$%^,mem[0x30..]全 0;电路执行后要求mem[0..0x17]等于 24 字节密文4F 4F 05 5F 54 6A 20 09 00 6F 6C 66 45 16 7C 3D 3F 64 03 18 5B 5E 5D 2F。 - 为什么用 z3:NAND 门是位运算,输入字节可建模为 BitVec(8),1008 条门只是 1008 个位向量表达式,规模很小;z3 可直接求解满足约束的 24 字节。手工逆推电路非常困难,但符号执行/约束求解很自然。
- 约束:flag 前 5 字节
flag{、末字节}、其余可打印(0x20–0x7E);这些约束能排除多解并加速。
触发条件
- 目标是 Linux ELF,含大量
00花指令/内嵌加密 ELF,静态反汇编困难。 - 能提取内嵌 ELF(XOR 0x27 或类似单字节 XOR),并找到 key 与加密数组。
- 能 dump 魔改 RC4 解密后的
v194(动态调试或复现算法)。 - 电路是 NAND/AND/OR/XOR 等位运算组合,输入长度小,适合 z3 求解。
利用步骤
- 修复花指令:用 010/脚本把连续
00改为90,重新用 IDA 反汇编;或按字节模式批量 patch。 - 提取内嵌 ELF:定位线程加载的数据与 XOR 0x27 循环,dump 后 XOR 回来,确认
\x7fELF;保存为新文件。 - 分析第二层:同样修花指令;找 key 字符串
KeyKEyKeYKEykEYKEY!@#$%^、24 字节密文与大数组。 - 还原 v194:按魔改 RC4 实现解密,或在 Linux 远程调试中在下游断点 dump
v194(原文用 gdb 远程调试)。 - 建模 z3:24 个 8-bit BitVec 表示 flag,前 5 字节/末字节/可打印约束;初始化 mem(flag + 固定尾串 + 0),按
v194的三元组执行mem[c] = ~(mem[b] & mem[a]);约束mem[0..23] == CIPH。 - 求解:
Solver().check(),取 model 的 24 字节;原文得到flag{B62o3$cC..*cE70O7?}。
PoC
from z3 import *
CIPH = bytes.fromhex("4F 4F 05 5F 54 6A 20 09 00 6F 6C 66 45 16 7C 3D "
"3F 64 03 18 5B 5E 5D 2F")
TAIL = bytes.fromhex("4B 65 79 4B 45 79 4B 65 59 4B 45 79 6B 45 59 4B "
"45 59 21 40 23 24 25 5E")
V194 = [...] # 从调试 dump 的字节,按小端解析成 0..N 的整数索引
mem = [None] * (max(V194[:3*0x3F0]) + 1)
flag = [BitVec(f"f{i}", 8) for i in range(24)]
for i in range(24):
mem[i] = flag[i]
s.add(flag[i] >= 0x20, flag[i] <= 0x7E)
for i, ch in enumerate(b"flag{"):
s.add(flag[i] == ch)
s.add(flag[23] == ord("}"))
for j, b in enumerate(TAIL):
mem[0x18 + j] = BitVecVal(b, 8)
for i in range(0x30, len(mem)):
mem[i] = BitVecVal(0, 8)
for k in range(0x3F0):
a, b, c = V194[3*k], V194[3*k+1], V194[3*k+2]
mem[c] = ~(mem[b] & mem[a])
for i in range(24):
s.add(mem[i] == BitVecVal(CIPH[i], 8))
assert s.check() == sat
m = s.model()
print(bytes([m.eval(flag[i]).as_long() for i in range(24)]))
原文输出:flag{B62o3$cC..*cE70O7?}。
变体与关联
- 变体:花指令换成跳转/无效前缀/重叠指令;内嵌 ELF 用多字节 XOR/AES;电路用 AND/OR/NOT 组合或带寄存器;输入更长时需要分块/增量求解。
- 关联:[[ctf-reverse-self-modifying-vm-bytecode-z3-symbolic-execution]](自修改 VM + z3)、[[ctf-reverse-gba-dma-boolean-circuit-unary-input]](布尔电路约束)、[[ctf-reverse-pe-driver-4byte-xor-repair-chained-xor-z3]](XOR 修复 + z3)、[[ctf-reverse-custom-stack-vm-bytecode-constraint-recovery]](栈式 VM 约束恢复)。
- 同题:
LinuxChal的mem[c]=~(mem[b]&mem[a])NAND 电路与 24 字节 flag。
检测与防御
- CTF 之外:花指令/内嵌 ELF 不是安全边界;动态调试 + dump 可绕过。
- 逆向方法:先批量 patch 花指令、再用 XOR 提取内嵌层;对位运算电路优先考虑 z3/符号执行,而不是手工逆推。
- 检测:对 ELF 中出现大量
00/重叠指令、运行时mmap+ XOR 解密后\x7fELF的行为,按多阶段加载器处理;监控进程创建线程执行匿名内存。