20 轮自定义 Feistel 逆推:key 指针按 4 字节取模 12 循环取 dword,正向两分支交换、逆向只需把 prev/next 角色对调
ctf/reverse · verified
一句话结论
当题目把 8 字节明文块拆成两个 32 位分支、用 for cnt in range(20) 做 next = prev ^ F(roundkey, next); swap(prev,next) 的 Feistel 结构时,解密不需要求 F 的逆——只要把初始的两个分支按正向输出顺序反着喂(密文后半段当 next、前半段当 prev),再按 cnt = 19..0 逆序跑同一轮函数即可,轮密钥仍是 key[cnt*4 % 12 : +4] 那个 dword。
原理
- 正向:
tmp = next; next = prev ^ F(k_i, next); prev = tmp。注意prev更新为旧的next,而next变成prev ^ F(...),这是一个交换型 Feistel(不需要F可逆),因为旧next被完整保留在prev中。 - 逆向:给定
(prev_i, next_i),能唯一恢复(prev_{i-1}, next_{i-1}) = (next_i ^ F(k_i, prev_i), prev_i)。也就是把prev/next的角色对调后重跑同一行代码:tmp = prev; prev = next ^ F(k_i, tmp); next = tmp。这就是为什么 exp 里只有两行被注释/反注释交换,而没有重写F。 - 轮密钥派生:
count = cnt * 4,dword_key = key[(count+3)%12]<<24 | ... | key[count%12]。key是 12 字节,按 4 字节步进并对 12 取模,所以 20 轮里轮密钥以 3 个 dword 为周期循环(第 0/3/6/… 轮同钥)。逆向时cnt必须与正向一一对应,否则轮密钥错位。 - 轮函数
F自身含一个基于 key 字节取值的置换:box[i] = i & 3,然后用key的每个字节的低 2 位决定把v10的第 i 个字节与第box[arr2[i]]个字节交换,最后整体再^ key。因为F只做异或与置换(都是自逆或可交换的),只看密文无法分辨它内部顺序,但 Feistel 结构保证不需要分辨。 - key 由程序内部用固定字符串(原文为
"love")初始化,直接下断点/动调从内存读出即可,不必逆 key 调度代码。
触发条件
- 目标算法是“两个 32 位分支 + 多轮 + 每轮只对其中一个分支做
F后异或”的 Feistel/类 Feistel 结构。 - 轮函数
F只使用异或、字节置换、加减等可复算运算(无需可逆性)。 - 轮密钥可从二进制常量或动调内存直接获得。
利用步骤
- 静态定位加密函数,确认循环轮数(本例 20)、每轮分支更新顺序与是否有额外 swap。
- 记录轮密钥派生表达式;确认
key长度与取模方式(本例 12 字节,cnt*4 % 12)。 - 动调在 key 初始化之后下断,dump 12 字节 key。
- 按“正向最后一次输出”的顺序取出密文两块:
next = 前 4 字节、prev = 后 4 字节(因为正向最后一步把prev写到了块的前半段)。 - 从
cnt = 19递减到 0,跑反向更新式,循环结束后prev/next就是明文两块。 - 逐个 8 字节块处理后拼接,得到 flag 文本。
PoC
enc = [0x58,0x31,0x29,0x33,0x11,0x02,0x76,0x60,
0x46,0x5F,0x18,0x42,0x29,0x6F,0x74,0x63]
key = [0x83,0xD1,0xDB,0xBB,0x2E,0x0F,0x34,0x05,0xAD,0xDE,0xEF,0xBE]
box = [i & 3 for i in range(256)]
inp = [0x44,0x41,0x53,0x43,0x54,0x46,0x7b,0x61,
0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x7d] # 占位明文,用于自校验
def num_to_arr(num):
r = []
while num:
r.append(num & 0xff); num >>= 8
return r
def F(k, n): # 轮函数:xor -> 字节置换 -> xor
a1, a2 = num_to_arr(k ^ n), num_to_arr(k)
for i in range(4):
j = box[a2[i]]
a1[i], a1[j] = a1[j], a1[i]
return (a1[0] | a1[1] << 8 | a1[2] << 16 | a1[3] << 24) ^ k
def enc_block(prev, nxt):
for cnt in range(20):
c = cnt * 4
k = (key[(c+3)%12]<<24)|(key[(c+2)%12]<<16)|(key[(c+1)%12]<<8)|key[c%12]
prev, nxt = nxt, prev ^ F(k, nxt)
return prev, nxt
def dec_block(prev, nxt): # 仅把角色对调、轮序反走
for cnt in range(19, -1, -1):
c = cnt * 4
k = (key[(c+3)%12]<<24)|(key[(c+2)%12]<<16)|(key[(c+1)%12]<<8)|key[c%12]
prev, nxt = nxt ^ F(k, prev), prev
return prev, nxt
def to_dword(b, off, le=True):
q = b[off:off+4]
return int.from_bytes(bytes(q), "little" if le else "big")
# 自校验:加密后再解密应回到原文
for off in range(0, 16, 8):
p, n = dec_block(*enc_block(*(to_dword(inp, off), to_dword(inp, off+4))))
assert p == to_dword(inp, off) and n == to_dword(inp, off+4)
# 解密:密文前半段是正向最后的 next,后半段是 prev
out = []
for off in range(0, len(enc), 8):
prev = to_dword(enc, off+4) # 注意:前 4 字节给 next,后 4 字节给 prev
nxt = to_dword(enc, off)
p, n = dec_block(prev, nxt)
out += list((p.to_bytes(4, "little") + n.to_bytes(4, "little")))
print(bytes(out))
变体与关联
- 变体:轮数改为 16/32、
key长度改成 16 或 24 时,只改range()与取模常数,逆推结构不变。 - 变体:若正向在循环外多做了一次
next = F(key0, next)(不在 Feistel 内),逆向要先单独消掉这一项。 - 变体:
F里混入加法/乘法时,仍按“先逆最后一步、逐轮回退”的思路重写F_inv,而不是靠猜。 - 关联:[[ctf-reverse-custom-vm-tea-like-30round-block-bruteforce]](另一类多轮自定义分组加密逆推)、[[ctf-reverse-custom-stack-vm-bytecode-constraint-recovery]](结构识别 + 逆向还原的一般方法)。
- 边界:只适用于分支完整保留的交换型 Feistel;若实现里
prev被就地覆盖(丢失旧next),该简单对调法失效,必须求F的逆。
检测与防御
- 本题为 CTF 反解题,无线上防御面。工程上可借鉴的点:不要把“算法保密”当安全边界,自定义 Feistel 在没有密钥保密的情况下等于无加密。
- 自我保护建议:轮密钥由运行时输入/环境派生而非硬编码,避免动调一次即 dump;对
F加白盒/查表混淆提高逆向成本。