Rust 菜单题隐藏开关:id 的二进制位选择全局常量异或,等价 32 元 GF(2) 方程组用高斯消元解出开门 id
ctf/pwn · verified
一句话结论
题目的 delete 功能只有在全局开关 UAF_FLAG 为 1 时才真正释放内存,而 UAF_FLAG 只在 id ^ do_something(id) == 0xFFFFFFFF 时被置 1。do_something(id) 的实现是把 id 转成二进制、按 位 决定要不要把全局数组(32 个 32 位 01 字符串常量)中的对应项异或进结果:等价于 32 个未知位 × 32 个方程的一次(线性)异或方程组 A·x = b,把常量 dump 出来做 GF(2) 高斯消元即得解(本例 id = 3957556225),门禁一开 delete 就能反复 free。
原理
- 位选择即线性组合:
for i in 0..32 { if (id >> i) & 1 == 1 { acc ^= K[i] } },其中异或是逐位模 2 加法、(id>>i)&1是 0/1 系数,所以acc是常量矩阵K在 GF(2) 上的线性组合,acc的每一比特都是一个 32 元一次方程。 - 为什么可以解:目标是
acc = id ^ 0xFFFFFFFF,即id的每一比特等于(acc 的对应比特) ^ 1。把 32 个 32 位常量按比特展开成 32×32 的 0/1 系数矩阵、右端项取0xFFFFFFFF ^ id的比特,就是一个标准 GF(2) 线性系统;系数矩阵满秩时解唯一(本例唯一解为3957556225)。 - 为什么要动态取常量:IDA 里
do_something是「Enumerate::next+String/Deref+Vec index+mix」一大堆泛型样板,静态还原成「取第 i 个 32 字节串」很费劲;直接把全局数组所在内存 dump 出来按 32 个 4 字节读,比逆泛型快得多。 - 为什么这道门禁在利用链里必须先解:
delete是唯一的 free 入口,且UAF_FLAG只会被置一次;不解门禁就只能 free 一次、拿不到 tcache/unsorted bin 的可重复操作,整个 UAF → tcache 投毒的后半条链无从谈起。
触发条件
- 程序里存在「输入一个整数 id → 用它的比特位选择若干常量异或 → 与 id 本身做比较/门控」的逻辑(反编译特征:
while循环 + 位测试 +pwn::mix之类的小函数 + 一次全局 bool 赋值); - 常量数组位于
.bss/.data且可在动调中直接 dump(本例是0x20字节的 01 字符串数组); - 门控表达式形如
id ^ f(id) == MASK或f(id) == id ^ MASK,能转成线性方程组。
利用步骤
- 定位门控分支:
if (UAF_FLAG || (v = do_something(id), (id ^ v) != 0xFFFFFFFF))—— 进入 else 分支时把UAF_FLAG=1,说明id ^ do_something(id) == 0xFFFFFFFF是目标等式。 - 动调确认
do_something的输入就是用户输入的id:输入123,观察循环里出现的中间值恰为0b1111011,且只在对应位为 1 时调用mix。 - 确认
mix是一次异或:执行前后对比寄存器,每次异或的是来自.bss全局数组的0x20字节 01 字符串。 - dump 该全局数组(32 项 × 32 位),整理成 32 行 01 字符串(每项一行)。
- 构造方程组求解:第
j位方程 = 所有x_i=1的行在j列的异或和 =0xFFFFFFFF的第j位;用高斯消元/直接位运算求解,得id = 3957556225。 - 把
id作为delete的参数传入,UAF_FLAG被置 1,之后delete(任意下标)都真实释放,可继续走 UAF 链。
PoC
求解思路(矩阵来自第 4 步的 dump;原文用一个 C++ 高斯消元二进制 + pwntools 喂数据拿到结果,这里给出等价的最小实现,未执行):
# K[i]:第 i 个 32 位常量(来自 .bss dump),行 i 的第 j 位 = (K[i] >> j) & 1
MASK = 0xFFFFFFFF
x = 0
for j in range(32): # 也可以直接对 32x32 矩阵做 GF(2) 消元
...
# 等价判定:解出 x 后必须满足
acc = 0
for i in range(32):
if (x >> i) & 1:
acc ^= K[i]
assert x ^ acc == MASK
print(x) # 3957556225
原文的求解路径是从 dump 里把 32 行 01 串按 列 重排喂给高斯消元器,再由 pwntools 收集 32 行输出拼成整数;思路与上式一致,只是把「列优先读矩阵」交给外部求解器完成。
变体与关联
- 变体:把异或换成 GF(2) 上的矩阵乘或加法链,仍是线性系统;若常量按位循环移位后再异或,系数矩阵变成循环阵,可用 Berlekamp–Massey 或直接构造循环方程求解。
- 变体:门控条件改成
>=/区间判断,则只有部分位参与方程(欠定),需要枚举自由变量或用 Z3 求解。 - 关联:[[ctf-pwn-rust-vec-uaf-leak-environ-tcache-stack-backdoor]](本门禁解开后的完整 UAF → environ → 栈 ROP 链)、[[ctf-reverse-z3-constraint-equation-solve]](约束求解的同类套路)、[[ctf-reverse-printable-ascii-caesar-hidden-permutation-table]](同样是「先静态读出隐藏常量表再反解」的题)。
检测与防御
- 逆向视角:这类位选择门禁的保护价值很低,常量在二进制里明文存放,dump 后解线性方程即可;真正提高成本要把门控改成带密钥的哈希/签名。
- 代码审计视角:
if (flag || checked)这种「先判断全局开关再决定是否执行危险操作」的写法是典型的调试后门/隐藏开关,应作为审计重点;生产代码里任何unsafe释放路径都应有统一的Option包装与置空。 - 检测点:函数内出现「按输入的比特位循环 + 与全局数组异或 + 单次置位全局 bool」的组合,即可能是隐藏门禁,可直接打 patch 把比较指令改成恒真来跳过。