滤波 LFSR 非线性输出状态恢复:48 位状态 + 80 位密钥流建模为 Z3 布尔约束
crypto/prng · verified
一句话结论
LFSR 本身是线性的,但输出经过非线性滤波器(如 WG 的 ANF 组合函数)后,经典 Berlekamp–Massey/线性方程组失效;只要结构(反馈抽头、滤波抽头、ANF)已知且有足够长的连续密钥流(示例 80 位),就可以把 48 位初始状态当作布尔未知量,把 LFSR 时钟更新与每位滤波输出建模成 Z3 约束,求解初始状态后解密。
原理
- LFSR 时钟:状态
s[0..L-1]每个时钟按反馈抽头异或得到fb,状态左移/右移并插入fb:state = [fb] + state[:-1](具体方向按题目)。这一步是 GF(2) 线性变换,可逐位表示为 XOR 约束。 - 非线性滤波:输出不是单个抽头,而是取 7 个滤波抽头的位组成 7-bit 索引,再查 ANF(代数正规型)真值表
f: {0,1}^7 → {0,1}。ANF 是若干单项式(变量子集的 AND)的 XOR;例如x1x2x3 ⊕ x0x2 ⊕ ...。非线性来自 AND 项,使输出对状态不是线性的。 - 建模:为初始 48 位建
Bool变量;每个时钟: 1. 用If(state[tap], 1<<j, 0)拼出 7-bit 索引(BitVecVal); 2. 预计算 7-bit ANF 真值表为 128-bit 常量TT,用LShR(TT, ZeroExt(121, idx)) & 1取第 idx 位作为输出(z3py 的Extract只接受常量索引); 3.solver.add(outbit == keystream[i]); 4. 按反馈抽头更新状态(XOR)。 - 求解:80 位密钥流提供 80 个约束,未知量 48 个,通常可唯一确定初始状态;Z3 的 SAT 求解器能处理这种布尔/位向量混合约束。
- 为什么 BM 失效:BM 只适用于线性递推序列;滤波输出是非线性序列,线性复杂度可能接近状态长度但无法直接恢复状态;SAT 建模直接利用已知非线性结构。
- 解密:拿到初始状态后,重建 LFSR 密钥流,按题目
decrypt(nonce, ct, init_state)解出 flag。
触发条件
- 目标使用 LFSR + 非线性滤波器的流密码/PRNG,且结构(长度 L、反馈抽头、滤波抽头、ANF/真值表)已知或可从代码逆出。
- 可获得足够长的连续密钥流(至少约 L 位,示例 80 位 > 48 状态);密钥流与状态一一对应、无噪声。
- 状态空间大(2^48)无法暴力;但约束系统可满足。
- 有 Z3/其它 SAT/SMT 求解器与建模脚本。
利用步骤
- 逆出结构:从代码/题目数据获取 L(48)、
feedback_taps、filter_taps、WG ANF 项或 7-bit 真值表。 - 预计算真值表:遍历 0..127,按 ANF 计算
f(bits),拼成 128-bit 常量TT。 - 建 Z3 模型:初始状态 48 个 Bool;对每位密钥流,拼索引、移位取位、加约束、更新 LFSR。
- 求解:
solver.check()==sat,从 model 取 48 位初始状态。 - 重建密钥流/解密:用初始状态生成密钥流,调用题目解密函数或自行实现流密码解密。
- 验证:用求解状态重算前 80 位密钥流,应与给定序列一致;再解 flag。
- 优化:若求解慢,可增加约束/固定已知前缀、用
BitVec整体建模、或分块求解。
PoC
from z3 import *
L = 48
feedback_taps = [...] # 反馈抽头
filter_taps = [...] # 7 个滤波抽头
keystream = [...] # 0/1 序列
WG_ANF_TERMS = [(1,2,3,4,5,6), (0,1,2,3,5), ...] # 题目给定
def eval_anf(bits):
res = 0
for mon in WG_ANF_TERMS:
prod = 1
for i in mon:
prod &= bits[i]
res ^= prod
return res
TT = 0
for x in range(128):
bits = [(x >> i) & 1 for i in range(7)]
if eval_anf(bits):
TT |= (1 << x)
TT = BitVecVal(TT, 128)
solver = Solver()
state0 = [Bool(f"s{i}") for i in range(L)]
state = state0[:]
for ks in keystream:
idx = BitVecVal(0, 7)
for j, tap in enumerate(filter_taps):
idx = idx | If(state[tap], BitVecVal(1 << j, 7), BitVecVal(0, 7))
outbit = LShR(TT, ZeroExt(121, idx)) & 1
solver.add(outbit == BitVecVal(ks, 1))
fb = False
for t in feedback_taps:
fb = Xor(fb, state[t])
state = [fb] + state[:-1]
assert solver.check() == sat
model = solver.model()
init_state = [1 if model.eval(b) else 0 for b in state0]
print(init_state)
原文用该模型恢复 48 位状态并调用题目 decrypt 解出 flag;WG_ANF_TERMS/抽头需按目标实现补全。本卡不执行 PoC。
变体与关联
- 其它滤波器:WG、Geffe、求和生成器、门限函数等;只要能把输出写成状态位的布尔函数,都可 SAT 建模。
- 状态更大:2^64/2^128 无法暴力,但约束系统仍可能可解;可加入已知明文/密钥流前缀、分块、或用 CryptoMiniSat/专用代数攻击。
- 相关攻击:代数攻击(解多元非线性方程组)、快速相关攻击、线性掩码;SAT 是通用但可能较慢的路线。
- 关联:[[crypto-prng-conditional-lfsr-sat-onehot-counter]](条件更新 LFSR SAT)、[[ctf-crypto-lfsr-known-plaintext-state-recovery]](线性 LFSR 已知明文)、[[crypto-prng-mt19937-untemper-state-recovery-predict]](MT19937 状态恢复)。
- 边界:需要已知完整结构与非线性函数;若滤波器/抽头保密、密钥流有噪声或长度不足,SAT 可能无解/多解;真实密码应使用 CSPRNG 而非滤波 LFSR。
检测与防御
- 不要用滤波 LFSR 作为密码:使用 AES/ChaCha 等经过审查的 CSPRNG/流密码;LFSR 只适合测试/扩频等非安全场景。
- 增加非线性/状态:若必须用,增加状态长度、非线性度、输出抽头保密,并限制密钥流暴露长度;但这只是提高门槛。
- 检测:大量连续密钥流被采集、异常 SAT 求解资源消耗无法从外部直接检测;协议层应限制输出速率/长度。
- 响应:一旦怀疑状态恢复,立即轮换密钥/种子,停止使用该生成器。