FJM 高地址 RV32 状态机:逆向输入格式与 16-bit 状态约束恢复 flag body
ctf/reverse · verified
一句话结论
附件歌词文本不是重点;真正的校验逻辑藏在 colorful.fjm 高地址数据区的一段 RV32 小端程序里。反汇编后确认输入需要满足 NepCTF{...} 格式,并还原一个 16-bit 状态机:25 个目标 u16、跳步掩码、按特定 body/index 顺序的转移。用 DFS 枚举可打印字符,按 base_state 与 used 关系匹配目标,即可恢复唯一的 25 字节 flag body。
原理
- FJM 与 RV32:FJM 是 Flash/嵌入式资源容器;高地址数据区嵌入一段 RV32 小端程序。先用 RV32 反汇编器定位入口、输入读取和比较循环。
- 输入格式:程序检查
NepCTF{前缀和}后缀,body 长度 25;body 字符限制在可打印 ASCII(32..126)。 - 状态机:当前 16-bit 状态
state先经过base_state(state) = (((state >> 13) ^ 2) | ((state << 3) ^ 0x75A8)) & 0xFFFF;对每个位置按body_order/idx_order处理: - 若
skip_mask对应位为 0(checked),目标nxt = targets[idx],要求(nxt - base) & 0xFFFF <= 0xFF;used = (nxt - base) & 0xFFFF;原始字符raw = used ^ pos(pos<10)或used;raw必须在可打印范围。 - 若 unchecked,则枚举可打印字符
raw,下一状态(base + used_from_raw(pos, raw)) & 0xFFFF。 - DFS:按固定顺序递归,已知位置(如 body 10..13 =
Real)作为剪枝;每一步候选唯一或很少,最终得到唯一 25 字节 body,加上NepCTF{}即 flag。 - 为什么可解:状态转移是确定性的且每步约束强(目标值 + 可打印范围 + 已知明文片段),搜索空间被大幅剪枝。
触发条件
- 附件包含自定义容器/固件,内嵌非主流架构(RV32)校验程序。
- 输入格式和字符集可从反汇编恢复。
- 状态机每步有目标值/掩码约束,且字符集有限。
- 存在已知明文片段或可打印性约束用于剪枝。
利用步骤
- 解包
colorful.fjm,定位高地址 RV32 程序;用 RV32 反汇编确认入口与比较逻辑。 - 提取 25 个目标 u16、
skip_mask、body_order、idx_order、base_state、used_from_raw。 - 确认输入格式
NepCTF{...}与 body 长度;记录已知字符(如Real)。 - 按顺序 DFS:checked 位置反推
used/raw并校验范围;unchecked 位置枚举可打印字符并更新状态。 - 得到唯一 body,拼接
NepCTF{body}。
PoC
targets = [int.from_bytes(target_bytes[i*2:i*2+2], "little") for i in range(25)]
skip_mask = 0x210042
body_order = [0,5,10,15,20, 1,6,11,16,21, 2,7,12,17,22, 3,8,13,18,23, 4,9,14,19,24]
idx_order = [0,13,1,14,2, 15,3,16,4,17, 5,18,6,19,7, 20,8,21,9,22, 10,23,11,24,12]
known = {10: ord("R"), 11: ord("e"), 12: ord("a"), 13: ord("l")}
allowed = list(range(32, 127))
solutions = []
def base_state(state):
return (((state >> 13) ^ 2) | ((state << 3) ^ 0x75A8)) & 0xFFFF
def used_from_raw(pos, ch):
return ch ^ pos if pos < 10 else ch
def raw_from_used(pos, ch):
return ch ^ pos if pos < 10 else ch
def dfs(step, state, body):
if step == 25:
solutions.append(bytes(body)); return
pos, idx = body_order[step], idx_order[step]
checked = ((skip_mask >> idx) & 1) == 0
base = base_state(state)
if checked:
nxt = targets[idx]
used = (nxt - base) & 0xFFFF
if used > 0xFF:
return
raw = raw_from_used(pos, used)
if raw not in allowed or (pos in known and raw != known[pos]):
return
old = body[pos]
if old is not None and old != raw:
return
body[pos] = raw
dfs(step + 1, nxt, body)
body[pos] = old
return
candidates = [known[pos]] if pos in known else allowed
for raw in candidates:
old = body[pos]
if old is not None and old != raw:
continue
body[pos] = raw
dfs(step + 1, (base + used_from_raw(pos, raw)) & 0xFFFF, body)
body[pos] = old
body = [None] * 25
for pos, ch in known.items():
body[pos] = ch
dfs(0, 0, body)
print(solutions[0].decode())
print("NepCTF{%s}" % solutions[0].decode())
变体与关联
- 其他嵌入式 VM/状态机:8051、MSP430、Xtensa、自定义字节码;先识别架构再反汇编。
- 若状态转移不可逆/候选多,可用 SMT(Z3)或 meet-in-the-middle 代替 DFS。
- 若字符集更大,可先用已知明文/长度/校验和剪枝。
- 关联:RV32 固件逆向、状态机约束求解、可打印字符 DFS 卡。
检测与防御
- 这是 CTF 谜题;防御意义在于:不要把 flag 校验完全放在客户端固件中,关键逻辑放服务端或做白盒/混淆。
- 检测:FJM/固件中出现 RV32 代码、状态机比较表;输入处理函数对大字符集做逐字节约束。