GF(3) LFSR 已知明文恢复:前 40 输出取初态,模 3 高斯消元解 mask 并解密
ctf/crypto · verified
一句话结论
在 GF(3) 上的 LFSR 中,每次输出 state[0] 后状态右移并在末尾追加 b = Σ state[i]·mask[i] mod 3;题目给出的已知明文 gift 足以反推出前 40 个输出(即 40 个 trit 的初始状态)和接下来的 40 个输出,用模 3 高斯消元解出 40 个 mask 系数,即可推进状态到 flag 密文起点并生成密钥流,逐 trit 还原明文。
原理
- 三进制 LFSR:状态向量长度
n=40,每个分量取值{0,1,2}。每次output = state[0],随后state = state[1:] + [sum(state[i]*mask[i]) mod 3]。这是 GF(3) 上的线性递推:新状态分量是旧状态的线性组合。 - 已知明文得到密钥流:加密为逐 trit
ct = pt ^ stream(题面用 Python 的^实现,脚本按同样运算对齐)。gift是已知明文b'\xff'*k的密文;把已知明文展开成 base-3(LSB-first)后与gift逐位异或,即得一段连续密钥流(本例 81 个 trit)。 - 前 n 个输出就是初始状态:因为每次先输出
state[0]再移位,前 40 个输出恰好对应初始状态的 40 个分量,无需解方程。 - 后 n 个输出建立 mask 方程:第
t个输出是当时状态的state[0],而状态由初始状态和未知 mask 线性决定;把观察到的 40 个输出作为b、对应状态向量作为矩阵行,解A·mask = b (mod 3)即可。40 个方程解 40 个未知数,gift 提供 81 个输出,满足2n的最低要求。 - 推进到 flag 起点:gift 消耗了前
L个密钥流 trit(本例L=81),要先把恢复出的状态推进L步,再为 flag 密文生成长度相同的密钥流;flag 密文也是 base-3 trit 序列,异或后按 LSB-first 还原整数,再按大端转字节。 - 为什么成立:LFSR 的线性性使已知明文攻击从暴力搜索
3^40降为解 40×40 的模 3 线性方程组;mask 与状态都只需多项式时间。
触发条件
- LFSR 工作在 GF(3)(或一般小素数域),状态长度
n已知(本例题目首行给出 40)。 - 加密是逐 trit 组合(异或/模 3 加),且提供一段已知明文的密文
gift。 - 已知明文展开后的 trit 数至少
2n(本例 81 ≥ 80),能同时覆盖初态与 mask 方程。 - 需要恢复 flag 密文
ct起始位置对应的密钥流(需知道 gift 消耗的 trit 数或能推断)。 - 有模 3 高斯消元/线性代数实现,能处理非域元素(3 为素数,1/2 的逆分别为 1/2)。
利用步骤
- 读取题目代码/参数,确认 LFSR 的状态长度
n、输出位(state[0])、移位方向和反馈公式。 - 把
gift的已知明文按 base-3 LSB-first 展开;与gift密文逐位异或得到密钥流stream。 - 取
stream[:n]作为初始状态;对t=0..n-1,用stream[t:t+n]构造矩阵行、stream[n+t]作为b,建立A·mask = b (mod 3)。 - 模 3 高斯消元(主元为 1 或 2,2 的逆为 2)解出
mask;用mask重放前2n个输出,验证与stream一致。 - 从初始状态模拟推进
L步(gift 消耗的 trit 数),再为ct生成等长密钥流。 - 逐 trit 异或得到 flag 明文 trits;按
flag_int += d*3^i还原整数,再to_bytes(...,'big')解码;用QnQSec{/flag{前缀校验。
PoC
def expand(n, base=3):
res = []
while n:
res.append(n % base); n //= base
return res or [0]
def solve_mod3(A, b):
n, m = len(A), len(A[0])
M = [row[:] + [bv] for row, bv in zip(A, b)]
r = 0
for c in range(m):
piv = next((i for i in range(r, n) if M[i][c] % 3), None)
if piv is None: continue
M[r], M[piv] = M[piv], M[r]
if M[r][c] % 3 == 2:
M[r] = [(v * 2) % 3 for v in M[r]]
for i in range(n):
if i != r and M[i][c] % 3:
f = M[i][c] % 3
M[i] = [(M[i][j] - f * M[r][j]) % 3 for j in range(m + 1)]
r += 1
x = [0] * m
for row in M:
lead = next((j for j in range(m) if row[j] % 3), None)
if lead is not None:
x[lead] = row[-1] % 3
return x
gift_ct = bytes.fromhex(GIFT_HEX)
flag_ct = bytes.fromhex(CT_HEX)
gift_pt = expand(int.from_bytes(b"\xff" * 16, "big"), 3)
L = min(len(gift_pt), len(gift_ct))
stream = [gift_pt[i] ^ gift_ct[i] for i in range(L)]
n = 40
init = stream[:n]
A = [[stream[t + i] % 3 for i in range(n)] for t in range(n)]
b = [stream[n + t] % 3 for t in range(n)]
mask = solve_mod3(A, b)
state = init[:]
def step(state):
out = state[0]
fb = sum(s * m for s, m in zip(state, mask)) % 3
return out, state[1:] + [fb]
for _ in range(L):
_, state = step(state)
ks = []
for _ in range(len(flag_ct)):
out, state = step(state)
ks.append(out)
digits = [ks[i] ^ flag_ct[i] for i in range(len(flag_ct))]
val, p = 0, 1
for d in digits:
val += d * p; p *= 3
print(val.to_bytes((val.bit_length() + 7) // 8, "big"))
变体与关联
- 变体:GF(2) 的 LFSR 用比特异或与 GF(2) 高斯消元,见 [[ctf-crypto-lfsr-known-plaintext-state-recovery]];已知 mask 求初态见 [[ctf-crypto-lfsr-mask-recovery-output-state]]。
- 变体:输出位不一定是
state[0];若输出是状态某一位的线性组合,矩阵行需按实际输出方程构造。 - 变体:反馈可能是模 3 加法/乘法混合、状态长度更大;只要保持线性,仍可用同一套模素数高斯消元。
- 边界:若 gift 的 trit 数小于
2n,方程不足;若加密不是逐 trit 线性组合(如先转字节再异或),需要按题目实际运算重建模型。
检测与防御
- 检测(CTF):题目给出 GF(3)/模 3 参数、状态长度与一段已知明文密文;密钥流长度至少为状态长度的 2 倍。
- 修复(真实设计):LFSR 不是密码学安全流密码;应使用 AES-CTR/ChaCha20 等带 nonce 的认证加密,避免线性反馈结构。
- 加固:若必须用 LFSR,至少叠加非线性滤波函数并定期重播种;不要复用密钥流。