♧ Godown 安全知识树

校验状态与明文字节耦合导致不可逆:正向逐位爆破 + 双字结对缩小候选 + 语义猜解收尾

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{} 包裹、下划线分词),用于在多解中收敛。

利用步骤

  1. 反编译定位真正做校验的 round 类函数,取出三样东西:比较常量数组、初始状态(本例 v1 = 33)、以及状态更新式(v1 = (v1 + v2) % 0x400 这类)。
  2. 把校验函数原样译成自己的语言(Python 足够),不要"顺手化简":(x % 5 + 5) % 5 这种写法说明作者在防负数取模,分支选择必须完全一致。
  3. 复现查表数据:本例的表是「0x400 逆序填充后再逐字节异或一个固定串(循环使用)」,按伪代码重建;表错一位后面全错。
  4. 逐位爆破第 0 位:枚举可打印字符,只填第 0 位、其余置 0,看第 0 位输出是否等于目标 flag[0];命中即确定第一位(若多解,用 flag 常见前缀 f/flag{ 收窄)。
  5. 逐位向后推进:把已确定的位作为前缀,只爆破当前一位。前几位通常唯一,往后候选迅速变多(出现"多解从第 4 位开始"是常态)。
  6. 候选变多后改成结对爆破:同时枚举两位,要求 out[i] == target[i] 且 out[i+1] == target[i+1];仍多解就继续扩到三位(注意 Python 三位爆破 95³ 已很慢,先只对候选多的区段做)。
  7. 语义收尾:对剩余候选按"是否构成有意义英文/常见 pwn 短语"人工挑选,挑完交回原程序或自写实现整体验证一次(12 位全过才算解出)。
  8. 交叉核对:若某位怎么爆都无解,先怀疑表构造、% 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),可把爆破空间直接砍掉一半;候选排序用自然语言启发式,最终必须整体验证,避免"意义通顺但校验不过"。