条件更新 LFSR 的 SAT 求解:前缀和 one-hot 计数器 + 翻转约束
crypto/prng · verified
一句话结论
两个 64 位 LFSR 中,lfsr2 只在 lfsr1 输出为 1 时更新,最终输出 output[t] = z_{sum(c_0..c_t)};c_t 与 z_j 都是 seed 的 GF(2) 线性函数,非线性只剩“前缀和选择哪个 z_j”。用 SAT 表示 64 个 seed 位、XOR 约束的 c_t/z_j、one-hot 前缀计数器和“输出翻转 ⇒ 当轮必须更新”的约束,即可在 60 秒内恢复 seed 并解密。
原理
- 两个 LFSR:
lfsr1每轮正常更新并输出控制位c_t;lfsr2只在c_t=1时更新。最终 64 位输出的第 t 位是z_{S_t},其中S_t = c_0 + c_1 + ... + c_t是到第 t 轮为止lfsr2的更新次数。 - 线性性:LFSR 的状态转移和输出都是 GF(2) 线性的,因此每个
c_t和每个z_j(lfsr2更新 j 次后的输出位)都可写成 64 个 seed 位的 XOR。 - 非线性来源:只有“根据前缀和
S_t选择z_{S_t}”这一步是非线性的;把S_t用 one-hot 计数器编码后,可用 SAT 处理。 - SAT 编码:
- 64 个布尔变量表示 seed;
seed由getRandomNBitInteger(64)生成,最高位恒为 1,加约束。 - 每个
c_t、z_j用add_xor_clause表示成 seed 的线性函数。 cnt[t][j]表示“第 t 轮结束后lfsr2更新了 j 次”;cnt[0][1]=c_0,之后cnt[t][j] = c_t ? cnt[t-1][j-1] : cnt[t-1][j](用 ITE/AND 子句展开)。output[t] = z_j:对每个cnt[t][j]=1,加子句强制z_j == output[t]。- 翻转约束:若
output[t] != output[t-1],说明第 t 轮lfsr2必须更新,即c_t=1。对随机输出,这条约束能固定大量控制位,显著加速求解。 - 多解与枚举:满足约束的 seed 可能不止一个,需用 AES 解密验证
fakeflag{...}格式;用 pycryptosat 增量求解,每次加 blocking clause 求下一个模型,避免重新建模。 - 实例筛选:不同实例的翻转次数不同,翻转越多约束越强;只选择
min_flips >= 26的实例,失败则重连换实例。 - 为什么可行:64 位 seed 的搜索空间是 2^64,但 SAT 利用线性结构和前缀和约束把它压到可解;60 秒内通常能枚举前若干个候选并命中正确 seed。
触发条件
- 目标使用两个 LFSR,其中一个条件更新,另一个正常更新;输出位是条件 LFSR 的当前位。
seed为 64 位且最高位已知(如getRandomNBitInteger(64)最高位为 1)。- 攻击者拿到
mask1、mask2、64 位output与AES_ECB(md5(str(seed)), secret)密文。 - 有 SAT 求解器(pycryptosat/CryptoMiniSat)与 AES 验证逻辑。
- 时间限制内允许枚举多个候选/重连。
利用步骤
- 从服务端读取
mask1、mask2、output、enc;计算output的相邻位翻转次数,低于阈值(如 26)则重连换实例。 - 预计算
lfsr1的 64 个c_t线性行与lfsr2的 65 个z_j线性行(z_0..z_64)。 - 建立 SAT:seed 变量 + 最高位 1;
c_t/z_j的 XOR 约束;cnt[t][j]的 one-hot 转移;output[t]=z_j的蕴含;翻转约束output[t]!=output[t-1] ⇒ c_t=1。 - 求解模型,取 seed;用
simulate(mask1,mask2,seed)复核output。 - 用
md5(str(seed))做 AES-ECB 解密,检查明文是否为fakeflag{32hex};失败则加 blocking clause 求下一个模型。 - 命中后提交/输出明文;若枚举上限内无解,重连换实例。
PoC
from pycryptosat import Solver
# 64 个 seed 位,最高位固定 1
# c_t = XOR(seed & mask1_row_t)
# z_j = XOR(seed & mask2_row_j)
# cnt[t][j]:第 t 轮后 lfsr2 更新 j 次
# cnt[0][1] = c_0;cnt[t][j] = c_t ? cnt[t-1][j-1] : cnt[t-1][j]
# 对每个 cnt[t][j]=1:z_j == output[t]
# 若 output[t] != output[t-1]:c_t = 1
solver = Solver()
# ... 建模 ...
sat, model = solver.solve()
seed = bits_to_int(model, seed_vars)
# 复核
assert simulate(mask1, mask2, seed) == output
# AES 验证;失败则 blocking clause 求下一个
key = hashlib.md5(str(seed).encode()).digest()
pt = unpad(AES.new(key, AES.MODE_ECB).decrypt(enc), 16)
# 案例:flips=26,candidate 1 命中
# seed = 9582451577998823576
# secret = fakeflag{997ab6dca75a1892802d61f43f6a0c9c}
变体与关联
- 条件变体:
lfsr2可在c_t=0时更新、按多比特控制、按计数器阈值更新;SAT 编码相应调整。 - 求解器变体:pycryptosat 增量求解、CryptoMiniSat、Z3;翻转约束和 one-hot 计数器是通用加速手段。
- 关联:[[ctf-crypto-lfsr-known-plaintext-state-recovery]](已知明文线性方程)、[[crypto-prng-mt19937-untemper-state-recovery-predict]](MT19937 状态恢复)、[[crypto-prng-lcg-parameter-recovery-delta-gcd]](LCG 参数恢复)。
检测与防御
- 检测:输出呈现 LFSR 线性结构;同一 seed 驱动两个寄存器;相邻输出翻转与控制位相关;AES 密钥由
md5(str(seed))派生。 - 防御:不要用 LFSR/线性反馈寄存器生成密钥或认证材料;使用 CSPRNG/流密码(ChaCha20、AES-CTR)并配合 MAC;seed 使用高熵随机数,不要只依赖 64 位。
- 加固:对密钥派生使用 HKDF;限制输出样本数量;对异常/多候选请求做速率限制;定期轮换密钥。