FNV-1a 取模跳表分发 + 131 进制哈希反解:剔除假 flag 分支
ctf/reverse · verified
一句话结论
stripped ELF 用输入前 9 字符的 FNV-1a 32 位哈希对 1009 取模,从跳表里选一个函数执行;绝大多数分支打印假 flag/回显输入/退出/喂 /bin/sh,只有 0x42fe9c 做真校验:把 32 字符按 i%4 分成 4 组,每组 8 字符做 h = h*131 + c,与 4 个常量比较;因为字符 < 131,直接按 131 进制取余即可反解。
原理
- 入口限制:
main检查参数存在且strlen == 0x20(32 字符)。 - 跳表分发:取前 9 字符调用
0x401216(FNV-1a 32:offset basis0x811c9dc5、prime0x1000193),结果% 1009,从0x44e080的表里取函数指针并调用。 - 假分支:
.rodata里有texsaw{nope_not_here}、大量[SUCCESS] Flag: %s、/bin/sh;跳表分支会打印假 flag、把输入当成功回显、直接 exit,或把输入喂给/bin/sh -c。只看输出会被误导。 - 真校验:
0x42fe9c初始化 4 个 64 位变量为 0,循环h[i%4] = h[i%4]*131 + input[i],最后与:c0=0x0112996d9ae479fd、c1=0x00efb70b2a601818、c2=0x011c799cc5063ac2、c3=0x01100d35eadc1177比较。 - 反解:32 字符按
i%4分组,每组正好 8 个字符;h = ((...(0*131+s0)*131+s1)...)*131+s7就是 8 位 131 进制数。因为 ASCII < 131,反复divmod(h,131)得到 8 个字符(逆序),再按组交错拼回原串。 - 结果:
texsaw{VVhYd_U_M4k3_mE_s0_4n6ry}。
触发条件
- stripped ELF/PE,输入长度固定,存在“哈希 → 取模 → 函数表调用”的分发结构。
- 表项数量较大(本题 1009),大量分支是假 flag/回显/exit/shell 等诱饵。
- 真校验分支使用可逆的线性哈希(
h = h*base + c)和固定常量比较。 - 字符集范围小于 base(如 ASCII < 131),保证进制反解唯一。
利用步骤
- 用
file/checksec确认架构与保护;运行观察输入长度/提示。 - 定位
strlen比较、哈希函数(FNV-1a 常量0x811c9dc5/0x1000193)、取模常量(0x3f1=1009)和跳表地址。 - 枚举/反编译跳表分支,标记假 flag/回显/exit/shell;找真正做完整比较的函数。
- 在真校验里提取 4 个目标常量和哈希公式
h[i%4]=h[i%4]*base+c。 - 对每个常量反复
divmod(_, base)取 8 个字符,反转;按i%4交错拼回。 - 用程序本地验证/重新计算哈希,确认 flag。
PoC
consts = [
0x0112996d9ae479fd,
0x00efb70b2a601818,
0x011c799cc5063ac2,
0x01100d35eadc1177,
]
groups = []
for x in consts:
s = []
for _ in range(8):
x, r = divmod(x, 131)
s.append(chr(r))
groups.append("".join(reversed(s)))
flag = "".join(groups[j][i] for i in range(8) for j in range(4))
print(flag) # texsaw{VVhYd_U_M4k3_mE_s0_4n6ry}
变体与关联
- 哈希变体:FNV-1a 32/64、djb2、CRC32;取模常量/表大小不同。
- 分发变体:函数指针表、switch jump table、虚表;假分支可能打印假 flag、回显输入、
system、exit。 - 校验变体:
h = h*base + c的 base-N 哈希、滚动哈希、分组交错;只要 base > 字符范围就可反解。 - 关联卡片:[[web-java-deser-fastjson2-fnv-collision-autotype-bypass]](FNV-1a 碰撞)、[[ctf-reverse-upx-vm-rolling-hash-per-char-inversion]](滚动哈希反推)、[[ctf-reverse-z3-constraint-equation-solve]](约束求解)。
- 边界:若 base ≤ 字符范围、或哈希含异或/取模等不可逆操作,不能直接 divmod;需要额外约束/爆破。假 flag 不能直接提交。
检测与防御
- 防御:不要用“输入前缀哈希 + 跳表”做校验;使用服务端/加密 MAC;去除调试/假 flag/
/bin/sh分支。 - 检测信号:大量
[SUCCESS] Flag: %s字符串但只有一个真比较;FNV-1a 常量 + 取模 + 函数表;/bin/sh被当命令执行。 - CTF 技巧:先识别假分支,再找真校验;看到
h*131+c就想 base-131 反解。