xorshift Fisher-Yates 逆置换 + 38 字节自定义变换逆解
ctf/reverse · verified
一句话结论
程序用固定 seed 的 xorshift32 做 Fisher-Yates 洗牌生成 256 字节置换及逆表,再用一个 38 轮、16 字节状态的自定义变换 t() 把 .rodata 中 38 字节参考串变成真正的 flag;因为 t() 每轮只做 ROR8、查逆表、加减和状态更新,按反编译逐条复刻即可直接算出 KCTF{aN0Th3r_r3_I_h0PE_y0U_eNj0YED_IT},关键是注意 xmmword 在 IDA 显示顺序与内存顺序相反。
原理
- 多分支/decoy:
main要求输入长度 38;chk_first_*三组检查命中只打印“Success! ...but you won't get points...”的假 flag;真校验是cat3拼出 38 字节参考串v5,t(v6, v5, v9)变换得到目标v6,再eq(s, v6)比较。因此v6就是 flag。 - 置换表:
p(v8, v9)先填perm=[0..255],再用 xorshift32(seed0xF5A4ADA5)从末尾pos=255..0做 Fisher-Yates:state=xorshift32(state); j=state%(pos+1); swap(perm[pos],perm[j]);最后inv[perm[i]]=i,v9是逆表。 - 38 字节参考串:
cat3从x_r0取 12 字节、x_r1取 13 字节、x_r2取 13 字节,拼成 38 字节;这些都在.rodata。 - 变换
t():维护 16 字节状态i[16](初始来自xmmword_2180),每轮: - 取参考字节
v12; - 用常量
0x6A124DE908B17733的第(idx&7)字节、v10/v4/v12混合,ROR8后索引inv表; v14 = (inv[table_index] - v13) & 0xFF作为输出;- 更新
i[idx&0xF]、i[(idx+3)&0xF],以及v5/v4/v8/v10/v6/v7等滚动变量。 - 端序坑:IDA 显示
xmmword_2180 = 6A124DE908B177332F910ED35CA71942h,但 SSEmovdqu的内存顺序是低 qword 在前;按显示顺序初始化会得到一半乱码,按反序42 19 A7 5C D3 0E 91 2F 33 77 B1 08 E9 4D 12 6A才得到完整可打印KCTF{...}。 - 为什么可行:
t()是确定性变换,无随机/无外部输入;只要复刻状态更新和常量/端序,就能直接算出目标串。
触发条件
- 输入长度固定(38),程序有多组
chk_first假 flag 分支;真校验调用cat3+t+eq。 - 反编译中出现
perm=[0..255]、xorshift三步移位异或、div取余、swap、inv[perm[i]]=i。 t()中有 16 字节状态、ROR8、常量0x6A124DE908B17733、逆表查表。.rodata中有三段x_r0/x_r1/x_r2常量,合计 38 字节。
利用步骤
- 从
main定位真校验分支(cat3+t+eq),确认v6是目标 flag。 - 从
.rodata读出x_r0(12 字节)、x_r1(13 字节)、x_r2(13 字节),拼接为 38 字节参考串。 - 实现 xorshift32:
x ^= x<<13; x ^= x>>17; x ^= x<<5(32 位掩码);从 seed0xF5A4ADA5、pos=255..0做 Fisher-Yates,得到perm;再inv[perm[i]]=i。 - 按反编译实现
t_transform(ref, inv, i_init):逐轮 ROR8、查表、输出、状态更新;i_init用 内存反序(42 19 A7 5C D3 0E 91 2F 33 77 B1 08 E9 4D 12 6A)。 - 输出 38 字节,检查
KCTF{/}和可打印性;若乱码,尝试 IDA 显示顺序/反序、idx边界、&0xF索引。 - 用程序本地运行复验;或动态调试 dump
v6直接得到 flag。
PoC
def ror8(x, r):
r &= 7; x &= 0xFF
return ((x >> r) | ((x << (8-r)) & 0xFF)) & 0xFF
def xorshift32(v):
v &= 0xFFFFFFFF
v ^= (v << 13) & 0xFFFFFFFF
v ^= v >> 17
v ^= (v << 5) & 0xFFFFFFFF
return v & 0xFFFFFFFF
def build_inv():
perm = list(range(256)); state = 0xF5A4ADA5
for pos in range(255, -1, -1):
state = xorshift32(state)
j = state % (pos + 1)
perm[pos], perm[j] = perm[j], perm[pos]
inv = [0] * 256
for i, p in enumerate(perm):
inv[p] = i
return inv
ref = bytes([0x0F,0x5F,0x6F,0xF7,0x01,0x0F,0xB2,0x18,0xEE,0xD3,0x37,0x84,
0xD2,0x4C,0xA4,0x79,0x4A,0xF7,0x18,0xCF,0x68,0x78,0x26,0xFC,0x37,
0xD0,0x8B,0x99,0x5A,0xE7,0xF5,0x46,0x37,0x82,0x48,0xFB,0xFE,0x0B])
i_init = bytes.fromhex("4219A75CD30E912F3377B108E94D126A") # 内存反序
inv = build_inv()
# t_transform 的完整逐轮逻辑见原文;核心为 ROR8 + inv[..] - v13 与 16 字节状态更新
说明:PoC 给出 xorshift/Fisher-Yates 逆表与参考串;完整 t_transform 需按原文逐行复刻(ROR8、inv 查表、i[idx&0xF]/i[(idx+3)&0xF] 更新)。未在本机对附件复跑。
变体与关联
- xorshift 变体:移位常量 13/17/5、seed、32/64 位;按反编译调整。
- Fisher-Yates 方向:从 255 到 0、
j=state%(pos+1);方向/取模写错会得到不同置换。 - 端序:
xmmword/movdqu的内存顺序与 IDA 显示顺序可能相反;用可打印性/KCTF{判定。 - 关联:[[ctf-reverse-fnv1a-decoy-29byte-transform-inverse]](同场比赛的另一逐字节变换)、[[ctf-reverse-byte-pair-add-rol8-buffer-rotate-inverse]](可逆变换 + 诱饵串)、[[crypto-prng-mt19937-buggy-randbelow-z3-shuffle]](洗牌逆向)。
检测与防御
- 识别:
perm=[0..255]+ xorshift +div取余 + 交换 + 逆表;16 字节状态的逐字节变换。 - CTF 防守:这种“固定 seed 洗牌 + 可逆变换”没有密钥,静态复刻即可还原;应使用带密钥的密码学构造。
- 真实系统:不要用固定 seed PRNG 生成置换/密钥;使用 CSPRNG 和标准加密。