三关串联校验逆向:魔方公式密钥 + FNV1a32、五元线性方程组与 seed 派生动态迷宫
ctf/reverse · verified
一句话结论
三关密码逐级派生:第一关 8 字符经魔方公式 R U F R' D2(XOR 0x5A 隐藏)加密后做 FNV1a32 比较,第一关哈希用于生成第二关五元线性方程组系数,第二关数字异或黄金比例常量作 seed 生成第三关 4×4 动态迷宫;必须按顺序解,不能跳关。
原理
- XOR 隐藏字符串:程序把明文字符串逐字节
^ 0x5A存成数组;例如enc[11]={0x1C,0x36,0x3B,0x3D,0x60,0x7A,0x13,0x09,0x19,0x19,0x21}解出Flag: ISCC{。密钥数组enc_key[i]同样解出魔方公式R U F R' D2。 - 第一关:可逆置换 + 哈希校验:输入长度 8、可打印字符;
cipher=k1c7(input,key)是自定义魔方置换,h=fnv1a32(cipher),校验(h ^ 0xA5A5A5A5) == 0xD9BDB554。FNV1a32 本身不可逆,但k1c7若可逆,可先对候选明文正向计算;原文直接给出第一关答案IXMEHAVZ,未展开从哈希目标反推的过程(8 个可打印字符空间 95^8,纯爆破不可行)。 - 哈希作为后续 KDF:第一关通过后保存
g_stage1_hash=h,调用d4n7(h)生成第二关的系数g_a[0..4]与目标值。后续关卡参数依赖前关结果,不能独立求解。 - 第二关:五元线性方程组:9 位数字拆成
x1=x[0]、x2=x[1]*10+x[2]、x3=x[3]*10+x[4]、x4=x[5]*10+x[6]、x5=x[7]*10+x[8];五个方程形如g_a[0]*x1 + x2 + x5 = b1、x1 + g_a[1]*x2 + x3 = b2、……,解出(8,55,32,19,32),拼接为855321932。 - 第三关:seed 派生迷宫:
seed = atoi(password2) ^ (g_stage1_hash * 0x9E3779B1u)(0x9E3779B1是黄金比例 32 位常量),b5k8(seed)用确定性 PRNG 生成 4×4 迷宫;从 (0,0) 到 (3,3),字符 L/R/U/D,路径RDRDRD。 - 最终输出:
h5b5()依次打印 XOR 隐藏的Flag: ISCC{、三段密码和}。
触发条件
- 程序连续读取三段输入,前一段通过后才读下一段;每段长度/字符集不同(8 可打印、9 数字、方向字符)。
- 二进制中出现 XOR 0x5A 的字符串数组、FNV1a32 常量(offset basis
0x811C9DC5、prime0x01000193)、5×5 线性方程、4×4 迷宫与 PRNG seed 混合常量。 - 第二关系数/目标不是硬编码,而是由第一关哈希经函数生成。
利用步骤
- 先解 XOR 隐藏字符串:找
^ 0x5A的数组,恢复魔方公式、输出前缀、提示文本。 - 第一关:还原
k1c7的置换规则;若可逆则从目标哈希做定向搜索/约束,若不可逆则结合题面/字典;原文样本答案为IXMEHAVZ。 - 记录第一关计算出的
h,复刻d4n7(h)得到第二关系数与目标。 - 第二关:按 9 位数字拆分规则建 5 个线性方程,用高斯消元/z3 求解;把解按 x1..x5 拼成 9 位数字。
- 第三关:按
seed = atoi(pw2) ^ (h * 0x9E3779B1)复刻 PRNG,生成迷宫;BFS/DFS 求 (0,0)→(3,3) 的合法路径。 - 拼接
ISCC{pw1+pw2+pw3},用原程序验证。
PoC
def xor_str(enc, k=0x5A):
return bytes(b ^ k for b in enc).decode()
print(xor_str([0x1C,0x36,0x3B,0x3D,0x60,0x7A,0x13,0x09,0x19,0x19,0x21]))
# "Flag: ISCC{"
def fnv1a32(data: bytes) -> int:
h = 0x811C9DC5
for b in data:
h = ((h ^ b) * 0x01000193) & 0xffffffff
return h
# 第二关:给定系数矩阵 A 与目标 b,解 A x = b
# 方程组形状(系数由 d4n7(stage1_hash) 动态生成):
# g0*x1 + x2 + x5 = b1
# x1 + g1*x2 + x3 = b2
# x2 + g2*x3 + x4 = b3
# x3 + g3*x4 + x5 = b4
# x1 + x4 + g4*x5 = b5
from z3 import Ints, Solver, sat
def solve_stage2(g, b):
x1, x2, x3, x4, x5 = Ints("x1 x2 x3 x4 x5")
s = Solver()
s.add(g[0]*x1 + x2 + x5 == b[0])
s.add(x1 + g[1]*x2 + x3 == b[1])
s.add(x2 + g[2]*x3 + x4 == b[2])
s.add(x3 + g[3]*x4 + x5 == b[3])
s.add(x1 + x4 + g[4]*x5 == b[4])
s.add(x1 >= 0, x1 <= 9, x2 >= 0, x2 <= 99, x3 >= 0, x3 <= 99,
x4 >= 0, x4 <= 99, x5 >= 0, x5 <= 99)
if s.check() != sat:
raise ValueError("no solution")
m = s.model()
vals = [m.eval(v).as_long() for v in (x1, x2, x3, x4, x5)]
return f"{vals[0]}{vals[1]:02d}{vals[2]:02d}{vals[3]:02d}{vals[4]:02d}"
# 原文样本:解为 8,55,32,19,32 -> "855321932"
# 第三关:seed 派生迷宫后 BFS/DFS,路径为 RDRDRD
# flag: ISCC{IXMEHAVZ855321932RDRDRD}
变体与关联
- 哈希作为 KDF 变体:MD5/SHA1/SHA256/CRC32/FNV 的输出被截断/异或后生成系数、seed、S 盒;按程序顺序复算,不要试图反哈希。
- 线性方程变体:变量可能按位/按字节拆分,系数矩阵可能稀疏;z3 或高斯消元均可,注意整数范围与除法。
- 动态迷宫变体:PRNG 可能是 MT19937、xorshift、LCG;先确认 seed 混合常量与生成顺序,再 BFS。
- 多关卡变体:后关参数可能依赖前关哈希、前关输入、时间/环境;用调试器记录中间值比纯静态更快。
- 关联卡片:[[ctf-reverse-z3-constraint-equation-solve]](z3 解线性方程)、[[ctf-reverse-zhie-map-vm-search]](地图状态机 + 搜索)、[[ctf-reverse-upx-vm-rolling-hash-per-char-inversion]](滚动哈希/逐字符校验)。
检测与防御
- 检测特征:多段
read/输入提示、XOR 0x5A 的字符串数组、FNV1a32 常量、5 个线性方程、4×4 迷宫与 seed 混合常量。 - 分析建议:先解 XOR 字符串拿提示和公式;第一关哈希不可逆时,优先找可逆置换/字典/调试器中间值,不要盲目爆破 95^8。
- 防御视角:多关卡串联只是增加分析步骤;把哈希输出当 KDF、把迷宫 seed 依赖前关结果都不能替代密钥保护。FNV1a 不是密码学哈希,容易被定向搜索/约束求解。