5×26 位图目标表逐位置反解:130 项 bitmask 相等校验直接还原 5 行输入
ctf/reverse · verified
一句话结论
校验函数把每行输入编码成“某字母在该行的哪些位置出现”的 26 个 64-bit 位图,再与硬编码目标表逐项比较,满分 130 项全等才通过。由于正常字符串每个位置只对应一个字母,目标表对每个位置只会有一个字母的位被置 1,因此遍历 26 个位图就能唯一还原该位置字符,直接读出全部 5 行输入,完全不需要爆破。
原理
- 编码方式:对第
line行(0..4)、字母下标idx(0..25),维护mask[line][idx];若该行第pos个字符等于'a'+idx,则置mask[line][idx]的第pos位为 1。 - 打分方式:对
line=0..4、idx=0..25,若mask[line][idx] == target[line][idx]则score++;最大值为5*26=130,满分即逐项完全相等。 - 可逆性:合法输入只含
a..z,同一行的同一位置只能是一个字母,所以对固定pos,130 个目标位图中恰好有一个(line,idx)的 bitpos为 1。把该 bit 映射回chr('a'+idx)即可得到该行该位置的字符。 - 长度恢复:每个字母位图的最高置位位置决定该行最大下标,
max_pos+1就是该行长度;若目标表在某高位没有置位,则该行更短。 - 输入读取细节:读取函数跳过前导空白,然后读非空白 token,最多 64 字符 + NUL;校验只接受
a..z,因此等价于“每行一个 token”,输入中不会出现空格。 - 为什么这是“信息泄露型”校验:按位置是否相等打分而不是整体哈希,目标表本身保存了每一位的答案;比较粒度越细,泄露越多。
触发条件
- 程序要求输入多行字符串,且对每行字符做按位置编码/比较。
- 代码中存在
50/130、5*26这类维度的位图数组或 qword 目标表。 - 计分/比较循环对每个
(line, letter)做相等判断,而不是一次性哈希比较。 - 读取逻辑限制字符集(如只允许小写字母),使每个位置只有一个字母候选。
利用步骤
- 从提示或字符串定位校验函数,确认行数(示例 5)与每行最大长度(示例 64)。
- 找到目标表全局符号(示例
I1iiIi,130 个 qword,逻辑上5×26)。 - 在 IDA 中用脚本 dump 全部 qword;按
line*26+idx取第line行第idx个字母的位图。 - 对每行扫描 26 个位图的所有置位,记录
pos -> chr('a'+idx),遇到多个字母命中同一pos说明目标表不是合法字符串或行维度判断有误。 - 按
0..max_pos拼接得到该行字符串,5 行依次输入即可拿满分。 - 若满分后还有二次编码(示例中程序再打印由输入导出的星图/十六进制串),继续按输出提示解码即可得到最终 flag。
PoC
import idc, ida_bytes, struct
base = idc.get_name_ea_simple("I1iiIi") # 130 个 qword 目标表
vals = [struct.unpack("<Q", ida_bytes.get_bytes(base + i * 8, 8))[0]
for i in range(130)]
for line in range(5):
pos_to_char = {}
for idx in range(26):
m = vals[line * 26 + idx]
pos = 0
while m:
if m & 1:
pos_to_char[pos] = chr(ord('a') + idx)
m >>= 1
pos += 1
max_pos = max(pos_to_char)
print("".join(pos_to_char[p] for p in range(max_pos + 1)))
若目标表在文件/内存中的字节序与 IDA 显示不同,先确认 qword 是小端读取;若行数或字母表不同,把 5/26/'a' 替换为反编译得到的实际维度即可。
变体与关联
- 同一思路适用于“每列/每位独立比较”的其他编码:字符集合位图、逐位布尔表、按位置的目标字符数组;只要比较是逐位置的,就能直接读出。
- 若目标表不是明文位图而是加密/压缩后的表,先解密或解压;若只给出哈希,则不可逆,需要回到爆破/约束求解。
- 若程序用相似方式对输入做置换/打分但存在多解,需要结合其他约束(如长度、额外校验)消歧。
- 与本库“位图/像素编码迷宫”类卡片的区别:这里的目标是直接恢复校验输入,而不是从图像/状态中解码路径。
检测与防御
- 识别特征:
score上限等于行数 × 字母表大小;目标表为行数 × 字母表大小个整数;比较循环按(line, idx, pos)三层展开。 - 防御(真实系统):不要用逐位置相等或可分桶的编码做秘密校验,应使用带盐的密码学哈希/HMAC,并对比较结果做恒定时间处理;不要把目标位图以明文形式放在二进制中。
- CTF 中若遇到更高维度的位图表,先确认每个位置的候选集合是否唯一,唯一则可直接反解,否则转约束求解。