校验状态与明文字节耦合导致不可逆:正向逐位爆破 + 双字结对缩小候选 + 语义猜解收尾
ctf/reverse · verified
一句话结论
当校验函数把「滚动状态」和「当前明文字节」塞进同一个变量一起参与运算(本态 = f(态, 字符),且下一轮的位置索引也由这个结果决定),逆推就没有唯一入口,只能按位置正向爆破:每一位把 30–126 的可打印字符全试一遍、保留所有让该位输出等于目标值的候选;候选一多就两两结对同时爆破来压缩解空间,最后靠 flag 格式、常见英文单词与上下文(前一位猜出来后下一位大概率是固定搭配)人工收尾。
原理
- 可逆的前提是「每步变换只依赖已知量」。本例每轮的
v1(下一次查表的索引)由(v1 + v2) % 0x400更新,而v2是本轮字符与查表值运算后的结果——状态被明文字节污染,所以从目标值出发不知道v1是多少,逆推需要同时猜字符和状态,等于没解。 - 正向爆破反而便宜:位置
i的输出只与「进入第 i 位时的状态」和「第 i 位字符」有关;只要前i-1个字符已确定,状态是唯一确定的,于是第i位只需枚举字符集(可打印 95 个)就能算出输出,与目标常量比对即可。 - 多解的根源是运算被压进小模数(
% 0x400,只有 1024 个取值):不同字符经不同分支(加/减/异或/左移/右移)后撞到同一个目标值很常见,位置越靠后(状态越"发散")候选越多。 - 压缩候选的手段是结对爆破:同时枚举
(第 i 位, 第 i+1 位)的 95×95 组合,要求两位的输出都匹配,等于给候选加了「连续两位同时命中」的约束,通常能砍掉绝大部分假解。 - 最后一步的"猜"不是瞎猜:
flag类明文本身是自然语言或a_b_c下划线分词,一旦某位爆破出_或g这类强提示,相邻位基本可以确定;把候选按"是否构成有意义单词"排序,人工挑一个交回程序验证即可。
触发条件
- 校验循环里出现「位置索引/状态与输入字节一起累加、异或、取模」的写法,且状态被下一轮继续使用。
- 比较目标是固定常量数组(
.rodata或构造出的int[]),长度等于输入长度(本例 12)。 - 存在可观的正向实现(能运行的程序、能原样重写的反编译伪代码,或自己按伪代码译出等价实现)。
- 输入字符集可约束(可打印 ASCII、
flag{}包裹、下划线分词),用于在多解中收敛。
利用步骤
- 反编译定位真正做校验的
round类函数,取出三样东西:比较常量数组、初始状态(本例v1 = 33)、以及状态更新式(v1 = (v1 + v2) % 0x400这类)。 - 把校验函数原样译成自己的语言(Python 足够),不要"顺手化简":
(x % 5 + 5) % 5这种写法说明作者在防负数取模,分支选择必须完全一致。 - 复现查表数据:本例的表是「0x400 逆序填充后再逐字节异或一个固定串(循环使用)」,按伪代码重建;表错一位后面全错。
- 逐位爆破第 0 位:枚举可打印字符,只填第 0 位、其余置 0,看第 0 位输出是否等于目标
flag[0];命中即确定第一位(若多解,用flag常见前缀f/flag{收窄)。 - 逐位向后推进:把已确定的位作为前缀,只爆破当前一位。前几位通常唯一,往后候选迅速变多(出现"多解从第 4 位开始"是常态)。
- 候选变多后改成结对爆破:同时枚举两位,要求
out[i] == target[i]且out[i+1] == target[i+1];仍多解就继续扩到三位(注意 Python 三位爆破 95³ 已很慢,先只对候选多的区段做)。 - 语义收尾:对剩余候选按"是否构成有意义英文/常见 pwn 短语"人工挑选,挑完交回原程序或自写实现整体验证一次(12 位全过才算解出)。
- 交叉核对:若某位怎么爆都无解,先怀疑表构造、
% 0x400与移位方向(shl在伪代码里可能写成>>、shr写成<<,本例即如此)是否照抄错了,而不是字符集不对。
PoC
正向爆破骨架(结对版;box 由题目的逆序+异或构造,target 为比较常量):
M = 0x400
def make_box(seed: str):
box = [0] * M
for i in range(M):
box[M - 1 - i] = i # 逆序填充
for i in range(M):
box[i] ^= ord(seed[i % len(seed)]) # 逐字节异或固定串
return box
def step(box, v, v1, ch):
"""复刻一轮:用字符 ch 在当前状态 v1 上做一次运算,返回 (v, v1)。"""
if ((box[v1] ^ ch) % 5 + 5) % 5 == 0:
v = ((ch + box[v1]) % M + M) % M
elif ((box[v1] ^ ch) % 5 + 5) % 5 == 1:
v = ((ch - box[v1]) % M + M) % M
elif ((box[v1] ^ ch) % 5 + 5) % 5 == 2:
v = (box[v1] ^ ch) % M
elif ((box[v1] ^ ch) % 5 + 5) % 5 == 3:
v = (ch >> 3) % M
else:
v = (ch << 3) % M
return v, (v1 + v) % M
def run(box, plain: str, rounds=0x20):
v1, outs = 33, []
for ch in plain:
v, v1 = ch, v1
for _ in range(rounds):
v, v1 = step(box, v, v1, v)
outs.append(v)
return outs
def brute2(box, target, prefix, i, charset=range(30, 127)):
"""已知 prefix,结对爆破第 i、i+1 位。"""
hit = []
for a in charset:
for b in charset:
outs = run(box, prefix + chr(a) + chr(b))
if outs[i] == target[i] and outs[i + 1] == target[i + 1]:
hit.append(prefix + chr(a) + chr(b))
return hit
用法要点:
1) 第一位只填一位、其余留空位,比较 outs[0] == target[0],命中即定;
2) 逐位推进,候选超过阈值(如 >20)时改调 brute2;
3) 结果多解时按「下划线分词 + 常见英文短语」人工挑选,最后用原程序整体验证。
变体与关联
- 变体一(先解混淆层):本题两段校验中,第一段是"每 4 字符组内第 2/3 位对调"的魔改 Base64,解得
round_and后才知道第二段的明文形态与长度;遇到多段校验时先解出能解的那段,为后续爆破提供前缀与长度约束。 - 变体二(把爆破变成求解):若状态更新只含
&/+/^等位运算常量,可把整个 12 位写成 12 个 8 位 BitVec 交给 z3,避免人工结对;但% 5分支选择在 z3 里要显式建模(If链或查表),成本可能高于爆破。 - 变体三(状态不复位):若状态在整串上滚动(不按位重置),正向爆破依然成立——因为前缀确定后状态唯一,只是必须严格按顺序爆破,不能跳位并行。
- 关联:[[ctf-reverse-obfuscated-state-machine-per-round-byte-enumeration]](同样是"按位枚举 + 目标字节表",但那题每位是独立的 8 位约束、无多解,属可完全自动化;本题状态被明文污染、模数小导致大量假解,必须结对爆破 + 语义猜解)、[[ctf-reverse-output-prefix-oracle-byte-brute]](输出前缀作为逐字节 oracle)、[[ctf-reverse-per-char-hex-ciphertext-argv-prefix-brute]](逐字符密文 + 已知前缀的爆破)、[[ctf-reverse-base64-group-char-swap-position-permutation]](本题第一段的魔改 Base64)。
检测与防御
- 识别信号:校验函数里出现"索引/状态 += 运算结果"且该结果依赖输入字符;比较对象是与输入等长的常量数组。
- 强度评估:把状态与明文耦合只能提高爆破成本,不能提高强度——本题实际只需 ~95×95 的枚举就能拿回 12 位明文,属于弱校验。
- CTF 出题建议:若要防爆破,应使用带密钥的整体哈希(HMAC/签名)而非小模数的可逐位分离运算;把分支选择与状态混淆得更强也挡不住"前缀确定即状态确定"这一性质。
- 求解侧建议:优先确认长度与前缀来源(本题从另一段校验拿到
round_and),可把爆破空间直接砍掉一半;候选排序用自然语言启发式,最终必须整体验证,避免"意义通顺但校验不过"。