Feistel 立方轮函数 GF(2^16) 代数攻击:多项式基秩下降恢复 16-bit 轮密钥
ctf/crypto · verified
一句话结论
对轮函数为 F(x,k)=(x+k)^3(GF(2^16) 上三次映射)的 8 轮 Feistel,可用“明文端多项式基约束 + 密文端逐 key 猜测”的秩下降攻击:把中间量写成 L0,R0 的单项式向量,求明文矩阵的左零空间 Q;对每个 16-bit 轮密钥猜测,从密文逆一轮后构造 M_bwd,正确 key 会使 Q·M_bwd 的秩明显下降,从而逐轮从末轮到首轮恢复 8 个 16-bit 轮密钥。
原理
- Feistel 结构:32-bit 状态拆成
L0||R0(各 16-bit),8 轮:L_{i+1}=R_i,R_{i+1}=L_i ⊕ F(R_i,k_i);F(x,k)=(x+k)^3,加法是 GF(2) 异或,乘法按题目不可约多项式0x1002D约简。 - 为什么不能直接 MITM:8 轮 key 共 128-bit;每轮 key 16-bit,完整 MITM 需要
2^64级表,不可行。 - 代数增长慢:三次幂在 GF(2^16) 上的展开项数增长远低于随机函数;把某个中间量
S(L0,R0)写成Σ c_{a,b} L0^a R0^b,基集合B的大小可控(不是所有幂次组合)。 - 左零空间约束:对明文端走
f轮(不猜 key,只用结构推导中间量必须落在的多项式空间),构造矩阵M_fwd(每行是一组明文的单项式向量),求左零空间Q,使Q·M_fwd≈0;Q的每一行就是一个合法中间量必须满足的线性约束。 - 秩下降判据:对第
t轮 key 猜k,从密文端逆b轮得到候选中间量S_guess,构造M_bwd;若k正确,Q·M_bwd接近零、秩明显下降;错误 key 时M_bwd近似随机矩阵,Q·M_bwd基本满秩。实践中不必追求秩=0,稳定降 2 以上即可锁定。 - 逐轮剥离:从末轮
k7开始,猜 key 并逆一轮,把所有样本整体退一轮;再猜k6……直到k0。经验分配:fwd=3轮,bwd=round_idx-3;当round_idx<3时数据已足够,直接纯 peel。 - 性能:每个 key 一次 rank check,高斯消元是瓶颈;只取略多于列数的样本行、用 bitset/uint64 分块、rank drop 早停。
触发条件
- 题目给出加密 oracle/大量明密文对(本题最多 675 对,512 秒),轮函数为 GF(2^16) 上的低次多项式(三次)。
- Feistel 轮数较少(8 轮),key 每轮 16-bit。
- 已知/可推断不可约多项式、状态拆字方式(L/R 各 16-bit)。
- 有足够算力做
2^16 × 8次密钥猜测 + 小矩阵高斯消元。
利用步骤
- 确认轮函数与域参数:
F(x,k)=(x+k)^3、POLY=0x1002D、n=8、16-bit 半块。 - 采集明密文对;按
L0||R0、L8||R8拆成 16-bit。 - 写 GF(2^16) 乘法/求逆、
F、dec_one(逆一轮)。 - 生成前向/后向单项式基:从
L={(1,0)}、R={(0,1)}开始,每轮把(R+k)^3展开为指数和,得到(a,b)集合;固定fwd=3,bwd=round_idx-3。 - 取略多于
|fwd_basis|+|bwd_basis|的样本;构造M_fwd,求左零空间Q。 - 对
k=0..0xFFFF:用dec_one逆一轮,构造M_bwd,计算Q·M_bwd的秩;选秩最小/下降最大的k。 - 记录
k,对所有样本 peel 一轮,round_idx-=1,重复 5–6 直到k0。 - 用恢复的 8 个 key 解密/复验,按题目格式提交。
PoC
POLY = 0x1002D
MASK = 0xFFFF
def gf_mul(a, b):
r = 0
for i in range(16):
if (b >> i) & 1:
r ^= a << i
for i in range(30, 15, -1):
if (r >> i) & 1:
r ^= POLY << (i - 16)
return r & MASK
def gf_add(a, b): return a ^ b
def F(x, k):
t = gf_add(x, k)
return gf_mul(gf_mul(t, t), t)
def dec_one(L, R, k):
# 逆 L'=R, R'=L^(R+k)^3
return R, gf_add(L, F(R, k))
# rank / left_kernel_basis / basis_shape / eval_monomials 见原文;
# 核心循环:
# Q = left_kernel_basis(M_fwd)
# for k in range(0x10000):
# peeled = [dec_one(L, R, k) for L, R in cts]
# Mb = [eval_monomials(Lp, Rp, bwd_basis) for Lp, Rp in peeled]
# rk = rank_gf(Q * Mb)
# if rk < best_rank: best_key = k
说明:PoC 只保留 GF(2^16)、轮函数与逆轮;basis_shape/left_kernel_basis/rank_gf 需按原文实现(单项式指数跟踪 + GF(2^16) 高斯消元)。未在本机对远端 oracle 复跑。
变体与关联
- 不同次数:
(x+k)^2、(x+k)^4等低次映射同样可用多项式基;次数越高基越大。 - 不同域:GF(2^8)/GF(2^32) 调整乘法/求逆;32-bit key 猜测量变大,需要更细的剪枝。
- 更多轮:增加
fwd/bwd分配和样本量;秩下降信号可能变弱。 - 关联:[[ctf-crypto-self-referential-key-tea-variant]](TEA/Feistel 变体)、[[ctf-crypto-simon-period-measurement-gf2-nullspace]](GF(2) 零空间攻击)。
检测与防御
- 设计:避免低次代数轮函数;使用 AES/ChaCha 等成熟分组/流密码,增加轮数和非线性。
- 检测:大量自适应明密文查询、固定差分/线性模式、针对末轮的 16-bit 猜测行为可作为代数攻击特征。
- CTF:本题是授权赛题;真实系统不要自创 Feistel + 低次轮函数。