KCTF2026 CrackMe08 Writeup
结果
kanxue@2o26o8!@#
在未修改的解包程序 extract/kctf2026_CrackMe08.exe 中输入该字符串，输出为：
Input:correct
1. 样本与解密层
原始压缩包：kctf2026_CrackMe08.rar。分析均在副本目录 work/CrackMe08 完成，原始 RAR 未修改。
PE 的有效校验逻辑有两段运行时解密：
| 阶段 |
RVA |
长度 |
还原方式 |
| stage 1 |
0x1800 |
0x510 |
每字节 XOR 0x5a |
| stage 2 |
0x1d10 |
0x4962 |
FNV 派生的字节流 XOR |
解密后，主校验函数位于 0x140004380。没有在原程序上 patch 校验分支；解密副本只用于反汇编和 Unicorn 单函数复现。
2. 输入格式
程序要求输入恰好 16 个可打印字符。每个字符映射为：
digit = ord(ch) - 0x21
随后按大端 base-94 将 16 个数字编码成一个 128 位附近的整数 A：
A = 0
for ch in text:
A = A * 94 + (ord(ch) - 0x21)
第一个廉价约束是：
sum(digit) = 752
等价地，原始 ASCII 字节和必须是 1280。这一步只能缩小候选空间，不能直接爆破，因为总空间仍是 94^16。
3. 校验模型
3.1 有限域与多项式
核心数值域为：
P = 2**127 - 39
这是一个素数模数。程序使用 Horner 形式的五次多项式，从 A 生成 128 位种子：
x = (A + c0) % P
x = (x * A + c1) % P
x = (x * A + c2) % P
x = (x * A + c3) % P
x = (x * A + c4) % P
seed = x
其中 c0..c4 均为样本中提取的 128 位常量，完整常量表保存在可运行求解器 solve_crackme08.py 的 POLY_C 中。
3.2 两个 20 轮可逆 phase
seed 被拆成 (high, low) 两个 64 位字。程序用两组不同轮常量，分别执行 20 轮变换；两个 phase 的最终状态都必须命中硬编码目标。
每轮先派生 key，再按下式更新：
high_next = phi(high, key) ^ low
low_next = phi(high_next, key ^ GOLDEN) ^ high
high, low = high_next & MASK64, low_next & MASK64
其中：
def phi(high, key):
x = ((high << 64) | key) % P
y = (MUL_C * x) % P
lo = y & MASK64
hi = y >> 64
t = ror64(hi, 47) ^ key ^ lo
return ror64(t, 51) ^ subbytes64(t)
subbytes64 是对每个字节查 256 项 S-box。phase 1 与 phase 2 的区别是轮常量数组和交替使用 H_A/H_B 的顺序不同，均已在 solver 中逐字恢复。
目标状态是：
phase 1: high = 0x0c14db1c20dd97a8, low = 0xb8fd0694401d3d03
phase 2: high = 0x9a2789b6de31c2dc, low = 0xaca5240a53fb78a6
关键点是这里没有单向压缩。给定一轮输出 (new_high, new_low) 和该轮 key，原输入唯一确定：
old_high = new_low ^ phi(new_high, key ^ GOLDEN)
old_low = new_high ^ phi(old_high, key)
因此从第 20 轮向第 1 轮倒推即可，不需要符号执行 40 轮。
对两个目标分别逆推后，得到完全相同的 seed：
seed_hi = 0x4be831b0ad3a2d36
seed_lo = 0x1489375bba3fb8de
seed = 0x4be831b0ad3a2d361489375bba3fb8de
两个独立 phase 汇聚到同一个 seed，是模型和端序正确的重要交叉验证。
3.3 FNV 约束
最后还有一个 FNV-1a 64 位链。字节序是小端：
FNV64_LE(
A.to_bytes(16, "little") ||
target0_low || target0_high || target1_low || target1_high
) == 0x6cd601b3049aa32c
尾部 32 字节都已知，因此从终值反向执行 FNV（乘法逆元存在）可得到对 A 的独立要求：
FNV64_LE(A.to_bytes(16, "little")) == 0xc8a68671c59dd0ad
4. 求解
现在多项式的输出 seed 已知，只需求：
f(A) - seed = 0 (mod P)
这是一元五次方程，而不是 16 个字符的爆破问题。使用 SymPy 在 GF(P) 中因式分解，取一次因子的根，再依次应用三个格式约束：
- 根可表示为 16 位 base-94；
- 16 个 digit 的和为
752；
- 满足反推的 FNV-1a 值。
唯一保留的整数为：
A = 0x00000174a5e1d4cf4f146e72f70092ac
将它连续除以 94，得到的 base-94 digits 为：
[74, 64, 77, 87, 84, 68, 31, 17, 78, 17, 21, 78, 23, 0, 31, 2]
每项加上 0x21 后即为：
kanxue@2o26o8!@#
5. 可复现验证
完整常量、S-box、两组轮常量和逆推实现见：
python D:\kctf\CTF6\work\CrackMe08\solve_crackme08.py --emu
预期输出：
flag: kanxue@2o26o8!@#
A: 0x00000174a5e1d4cf4f146e72f70092ac
seed_hi: 0x4be831b0ad3a2d36
seed_lo: 0x1489375bba3fb8de
unicorn_ret: 1
最后必须回到未 patch 的原版解包 exe 闭环：
"kanxue@2o26o8!@#" | & D:\kctf\CTF6\work\CrackMe08\extract\kctf2026_CrackMe08.exe
输出：
Input:correct
6. 要点
- 先解密并定位真实 checker，避免对外层垃圾代码建模。
- 两段 20 轮结构都可逆，应从目标倒推 seed，而非对字符作 SMT 或穷举。
- 已知 FNV 尾部可以逆推，FNV 在这里是筛选器，不是障碍。
- 将字符空间映射为单个 base-94 整数后，核心问题化成有限域上的低次多项式求根。
- 最终答案由两个 phase、有限域多项式、字符集/字符和和 FNV 链共同闭环验证。
