文章总结： 本文详解基于LFSR的CTF题目，利用Z3求解器攻击稀疏反馈流密码。文章分析LFSR线性弱点，通过符号变量与约束方程模拟状态更新，成功从密钥流恢复初始状态并获取Flag。内容涵盖LFSR安全缺陷、Z3应用技巧及现代密码设计原则建议。 综合评分： 96 文章分类： CTF,漏洞分析,二进制安全
zer0lfsr CTF密码学题目技术解析
原创
破镜安全
破镜安全
2026年1月7日 08:01 四川
zer0lfsr CTF密码学题目技术解析
一、题目概述
本题是一道基于线性反馈移位寄存器(LFSR)的流密码破解挑战。题目提供了加密算法源代码chall.py和生成的密钥流文件keystream。我们的目标是通过分析算法和密钥流,恢复出三个LFSR的初始状态,并计算出flag。
题目文件包括:
- chall.py: 包含LFSR实现、组合函数和密钥流生成逻辑
- keystream: 使用未知初始状态生成的8192字节密钥流
二、算法分析
2.1 LFSR基本原理
线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)是一种常用的伪随机数生成器,广泛应用于流密码系统中。其基本工作原理如下:
- 维护一个固定长度的二进制状态
- 每次迭代时,状态左移一位
- 根据反馈多项式(由mask定义)选择特定位进行异或运算,得到反馈位
- 将反馈位填入状态的最低位
- 输出反馈位作为密钥流的一位
让我们详细分析题目中的LFSR实现:
class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1 # 注意:是length+1,即49位掩码
def next(self):
nextdata = (self.init << 1) & self.lengthmask # 左移并保持在49位以内
i = self.init & self.mask & self.lengthmask # 提取mask选中的位
output = 0
# 计算mask选中位的异或
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output # 将输出异或到最低位
self.init = nextdata
return output
关键观察点:
- 状态扩展: 初始状态是48位,但lengthmask = 2^49 – 1,这意味着状态在迭代过程中会扩展到49位
- 反馈机制: mask决定了哪些位参与反馈计算,通过异或运算得到输出位
- 稀疏mask: 每个LFSR的mask只有2位被设置为1,这是一个重要的弱点
2.2 三个LFSR的配置
题目使用了三个独立的LFSR,配置如下:
l1 = lfsr(int.from_bytes(init1,"big"), 0b100000000000000000000000010000000000000000000000, 48)
l2 = lfsr(int.from_bytes(init2,"big"), 0b100000000000000000000000000000000010000000000000, 48)
l3 = lfsr(int.from_bytes(init3,"big"), 0b100000100000000000000000000000000000000000000000, 48)
通过分析mask的二进制表示(从右往左,从第0位开始计数):
- LFSR1: 第47位和第22位参与反馈
- LFSR2: 第47位和第13位参与反馈
- LFSR3: 第47位和第41位参与反馈
每个LFSR的初始状态为6字节(48位),mask中只有2个位置为1,这意味着每个输出位只依赖于当前状态中的2个位。
2.3 组合函数
三个LFSR的输出通过combine函数组合成最终的密钥流:
def combine(x1, x2, x3):
return (x1*x2)^(x2*x3)^(x1*x3)
由于x1、x2、x3都是单比特值(0或1),乘法运算等价于按位与(AND)操作。因此该函数可以改写为:
def combine(x1, x2, x3):
return (x1 & x2) ^ (x2 & x3) ^ (x1 & x3)
这是一个多数表决函数(majority function):
- 当三个输入中至少有两个为1时,输出为1
- 否则输出为0
真值表如下:
| x1 | x2 | x3 | 输出 | | — | — | — | — | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |
2.4 密钥流生成过程
密钥流的生成代码如下:
with open("keystream","wb") as f:
for i in range(8192):
b = 0
for j in range(8):
b = (b<<1)+combine(l1.next(),l2.next(),l3.next())
f.write(chr(b).encode())
生成过程:
- 外层循环8192次,每次生成一个字节
- 内层循环8次,每次从三个LFSR各取一位,通过combine函数组合得到一位输出
- 将8位组合成一个字节b
- 使用chr(b).encode()将字节转换为字符并编码为UTF-8写入文件
重要发现: 这里使用了chr(b).encode(),这意味着文件是UTF-8编码的文本文件,而不是二进制文件。这在后续读取密钥流时需要特别注意。
三、攻击原理分析
3.1 LFSR的安全弱点
本题中LFSR实现存在以下几个关键弱点:
- 状态空间较小: 每个LFSR的状态只有48位,总共144位的密钥空间。虽然看起来很大(约2^144),但对于现代密码分析来说是可以攻破的。
- 稀疏反馈多项式: 每个LFSR的mask只有2位被设置,意味着每个输出位只依赖于状态中的2个位。这大大降低了系统的复杂度。
- 线性特性: LFSR的状态更新完全是线性的,可以用线性方程组或布尔约束来表示。
- 已知密钥流: 我们拥有大量的输出密钥流,可以建立足够多的约束方程。
3.2 单个LFSR的比特传播分析
让我们深入分析单个LFSR的行为。以LFSR1为例,其mask的第47位和第22位为1。
假设初始状态为S0(48位),我们用S0[i]表示第i位(从0开始计数)。
第1次迭代:
- 输出: o0 = S0[47] XOR S0[22]
- 状态左移: S0 << 1
- 新状态最低位: o0
- 新状态S1 = (S0 << 1) XOR o0
第2次迭代:
- 当前状态S1中,第47位是原来S0的第46位,第22位是原来S0的第21位
- 输出: o1 = S1[47] XOR S1[22] = S0[46] XOR S0[21]
- 新状态S2 = (S1 << 1) XOR o1
第3次迭代:
- 输出: o2 = S2[47] XOR S2[22] = S0[45] XOR S0[20]
可以看到一个规律: 每个输出位都可以表示为初始状态中两个特定位的异或。这种线性关系是LFSR的本质特征。
3.3 使用约束求解器的攻击思路
由于LFSR的状态更新和组合函数都可以表示为布尔约束,我们可以使用SMT(Satisfiability Modulo Theories)求解器来恢复初始状态。Z3是微软研究院开发的一个强大的SMT求解器,非常适合解决这类问题。
基本攻击思路:
- 创建符号变量: 为三个LFSR的初始状态创建符号变量(未知数)
- 模拟算法执行: 用符号变量模拟LFSR的状态更新过程
- 添加约束条件: 对于每个已知的输出比特,添加一个约束方程
- 求解: 让Z3求解器找到满足所有约束的初始状态值
关键优势:
- 不需要手工推导复杂的数学关系
- 可以直接表达算法的逻辑约束
- 自动处理非线性的组合函数
3.4 所需密钥流长度分析
理论上,要唯一确定144位的初始状态(3个LFSR各48位),我们至少需要144个独立的约束方程。但由于:
- 组合函数引入了非线性关系
- 可能存在冗余约束
- 需要一定的冗余度来保证求解成功
实践中,使用48个字符(384个比特)的密钥流就足够恢复初始状态。这远超理论最小值,确保了求解的可靠性。
四、解题实现
4.1 密钥流文件的正确读取
首先需要注意密钥流文件的编码问题。题目使用chr(b).encode()写入文件,这会将字节值转换为Unicode字符再编码为UTF-8。因此读取时必须使用UTF-8解码:
with open("keystream", 'r', encoding='utf-8') as f:
data = f.read()
如果使用二进制模式读取(‘rb’),会得到UTF-8编码的字节序列,而不是原始的字节值。读取后,使用ord()函数可以恢复原始的字节值。
4.2 将密钥流转换为比特流
每个字符代表一个字节(8位),需要将其转换为比特流:
result_bits = []
for ch in keystream_chars:
byte_val = ord(ch)
# 从高位到低位提取8个比特
bits = [(byte_val >> (7-i)) & 1 for i in range(8)]
result_bits.extend(bits)
这样就得到了一个由0和1组成的比特序列,对应于combine函数的输出序列。
4.3 创建Z3符号变量和约束
使用Z3求解器的核心步骤如下:
步骤1: 创建求解器和符号变量
import z3
# 创建求解器
s = z3.Solver()
# 创建3个49位的符号变量(状态会扩展到49位)
state_bits = 49
x = z3.BitVec('x', state_bits)
y = z3.BitVec('y', state_bits)
z_var = z3.BitVec('z', state_bits)
inits = [x, y, z_var]
步骤2: 约束初始状态为48位
虽然运行时状态会扩展到49位,但初始状态只有48位,需要添加约束:
init_mask = (1 << 48) - 1 # 48位全1的掩码
s.add(z3.ULT(x, init_mask + 1)) # x < 2^48
s.add(z3.ULT(y, init_mask + 1)) # y < 2^48
s.add(z3.ULT(z_var, init_mask + 1)) # z < 2^48
步骤3: 为每个输出比特添加约束
这是最核心的部分,需要模拟LFSR的运行过程并添加约束:
# mask位索引
mask_indices = [(47, 22), (47, 13), (47, 41)]
len_mask_int = (2 ** 49) - 1
# 遍历每个输出比特
for idx, result in enumerate(result_bits):
combs = []
new_inits = []
# 对于3个LFSR
for lfsr_idx in range(3):
bit_idx1 = mask_indices[lfsr_idx][0]
bit_idx2 = mask_indices[lfsr_idx][1]
# 使用Extract提取特定位
bit1 = z3.Extract(bit_idx1, bit_idx1, inits[lfsr_idx])
bit2 = z3.Extract(bit_idx2, bit_idx2, inits[lfsr_idx])
# 计算单个LFSR的输出
output = bit1 ^ bit2
combs.append(output)
# 模拟LFSR状态更新
shifted = inits[lfsr_idx] << 1
output_extended = z3.ZeroExt(48, output) # 将1位扩展到49位
new_init = (shifted ^ output_extended) & len_mask_int
new_inits.append(new_init)
# 添加combine函数的约束
combined = (combs[0] & combs[1]) ^ (combs[1] & combs[2]) ^ (combs[0] & combs[2])
s.add(combined == result)
# 更新状态
inits = new_inits
4.4 关键技术要点解析
在实现过程中,有几个关键的技术细节需要特别注意:
1. BitVec的位数选择
必须使用49位而不是48位,因为LFSR的lengthmask是2^49-1,状态在运行过程中会扩展到49位。如果使用48位,会导致状态溢出,求解失败。
2. Extract操作的使用
使用z3.Extract()提取特定位,而不是使用Python的位运算符。这是因为Z3的BitVec类型和Python整数类型不能混合使用:
# 正确做法
bit1 = z3.Extract(47, 47, inits[0]) # 提取第47位
# 错误做法
bit1 = (inits[0] >> 47) & 1 # 会导致类型错误
3. ZeroExt操作的必要性
LFSR的输出是1位,但需要与49位的状态进行异或运算。必须使用z3.ZeroExt()将1位扩展到49位:
output_extended = z3.ZeroExt(48, output) # 将1位扩展到49位(48+1=49)
4. 约束数量的权衡
使用48个字符(384个比特)的密钥流就足够。更多的约束会增加求解时间,更少的约束可能导致无解或多解。
4.5 求解并提取结果
添加完所有约束后,调用Z3求解器并提取结果:
# 求解
check_result = s.check()
if check_result == z3.sat:
print("[+] 找到解!")
model = s.model()
# 提取解(只取低48位作为初始状态)
x_res = model[x].as_long() & init_mask
y_res = model[y].as_long() & init_mask
z_res = model[z_var].as_long() & init_mask
return x_res, y_res, z_res
else:
print("[-] 无解")
return None, None, None
4.6 计算FLAG
恢复初始状态后,按照题目要求计算flag:
from Crypto.Util.number import long_to_bytes
import hashlib
# 将初始状态转换为字节(每个48位=6字节)
init1 = long_to_bytes(x_res, 6)
init2 = long_to_bytes(y_res, 6)
init3 = long_to_bytes(z_res, 6)
# 计算SHA256哈希
flag_hash = hashlib.sha256(init1 + init2 + init3).hexdigest()
flag = f"flag{{{flag_hash}}}"
print(f"FLAG: {flag}")
4.7 运行结果
运行完整的求解脚本后,得到以下结果:
[*] 使用 384 个比特的密钥流
[*] 开始添加约束条件...
[*] 已添加 100 个约束条件
[*] 已添加 200 个约束条件
[*] 已添加 300 个约束条件
[*] 开始求解约束条件...
[*] 求解结果: sat
[+] 找到解!
[+] 恢复的LFSR初始状态:
LFSR1: 0x40907168b76f
LFSR2: 0xa4a712d8249f
LFSR3: 0xae32a61e80e9
FLAG: flag{b527e2621131134ec22250cfbca75e8c9f5ae4f40370871fd55910927f66a1b4}
验证结果显示,使用恢复的初始状态生成的密钥流与原始密钥流完全匹配,证明我们成功破解了这个流密码系统。
五、技术总结与安全启示
5.1 LFSR流密码的安全性问题
通过本题的分析,我们可以总结出基于LFSR的流密码存在以下几个关键安全问题:
1. 线性特性是致命弱点
LFSR的状态更新完全是线性的,每个输出位都可以表示为初始状态位的线性组合(异或运算)。这种线性特性使得系统容易受到代数攻击,可以通过建立线性方程组或使用约束求解器来破解。
2. 稀疏反馈多项式降低安全性
本题中每个LFSR的mask只有2位,意味着每个输出位只依赖于2个状态位。这大大降低了系统的复杂度。即使使用了三个LFSR组合,由于反馈多项式过于稀疏,仍然容易被攻破。
3. 状态空间不足
48位的状态空间(约2^48 ≈ 2.8×10^14)在现代计算能力下是不够的。对于密码学应用,通常需要至少128位的安全强度。
4. 简单的组合函数无法提供足够保护
虽然使用了多数表决函数来组合三个LFSR的输出,但这个函数仍然是一个简单的布尔函数,可以被约束求解器有效处理。
5.2 约束求解器在密码分析中的应用
本题展示了SMT求解器(如Z3)在密码分析中的强大能力:
优势:
- 可以直接表达密码算法的逻辑约束,无需手工推导数学关系
- 自动处理复杂的布尔约束和位运算
- 适用于状态空间较小的密码系统
- 开发效率高,代码简洁易懂
局限性:
- 对于大规模问题(如256位状态),求解时间可能过长
- 需要足够的已知输出来建立约束
- 对于高度非线性的系统,求解效率会显著下降
5.3 现代密码系统的设计原则
从本题的弱点中,我们可以总结出现代密码系统应该遵循的设计原则:
1. 足够的密钥长度
- 对称密码至少128位密钥
- 公钥密码至少2048位(RSA)或256位(ECC)
- 避免使用短密钥以抵抗暴力破解
2. 非线性组件
- 使用S盒(Substitution Box)引入非线性
- 采用复杂的混淆和扩散机制
- 避免纯线性的状态更新
3. 充分的轮数
- 确保每个输入位影响所有输出位
- 提供足够的安全边际
- 抵抗差分和线性密码分析
4. 经过充分分析的算法
- 优先使用标准算法(AES、ChaCha20等)
- 避免自己设计密码算法
- 新算法需要经过长期的密码学分析
5.4 解题过程中的关键技巧
在解决这类密码学CTF题目时,以下技巧非常重要:
1. 仔细分析算法实现
- 注意边界条件和特殊处理(如本题的lengthmask是49位而非48位)
- 理解每个参数的含义和作用
- 识别算法的弱点和可利用点
2. 注意编码问题
- 本题中chr(b).encode()导致文件是UTF-8编码而非二进制
- 这类细节容易被忽略,但会导致解题失败
- 始终验证数据的读取和解析是否正确
3. 先用已知数据测试
- 在攻击真实数据前,先用已知初始状态生成测试数据
- 验证求解器能否正确恢复已知的初始状态
- 这种方法可以快速发现实现中的错误
4. 注意类型一致性
- 在使用Z3时,避免Python类型和Z3类型混合
- 使用Extract、ZeroExt等Z3专用操作
- 类型错误是使用约束求解器时最常见的问题
六、扩展思考
6.1 如果增加mask位数会怎样?
假设每个LFSR的mask有8位而不是2位:
影响分析:
- 每个输出位依赖的初始状态位从2个增加到8个
- 约束方程的复杂度显著增加
- 但仍然是线性关系,Z3仍然可以求解
- 求解时间会增加,但对于48位状态仍然可行
结论: 增加mask位数可以提高安全性,但无法从根本上解决线性特性的问题。
6.2 如果状态长度更长会怎样?
假设状态长度从48位增加到128位或256位:
影响分析:
- 搜索空间呈指数级增长(2^128或2^256)
- 需要更多的密钥流数据来唯一确定初始状态
- Z3求解时间会显著增加,可能变得不可行
- 需要考虑其他攻击方法,如时间-内存权衡攻击
结论: 增加状态长度可以有效提高安全性,但仍需要配合其他安全措施。
6.3 如何改进这个密码系统?
如果要改进本题的密码系统,可以考虑以下方向:
1. 使用非线性反馈移位寄存器(NLFSR)
- 在反馈函数中引入非线性项(如AND、OR等)
- 破坏线性特性,使代数攻击更加困难
- 例如: Grain流密码使用了NLFSR
2. 增加LFSR数量和状态长度
- 使用5个或更多的LFSR
- 每个LFSR的状态长度至少128位
- 增加系统的复杂度和搜索空间
3. 使用更复杂的组合函数
- 采用非线性的S盒进行组合
- 使用多层的混淆和扩散
- 参考现代流密码的设计(如Trivium、ChaCha20)
4. 定期重新初始化
- 不使用同一初始状态生成大量密钥流
- 定期更换密钥或重新初始化状态
- 限制单个密钥的使用量
5. 添加初始化向量(IV)
- 使用公开的IV与密钥组合初始化状态
- 确保相同密钥在不同消息下产生不同密钥流
- 防止密钥流重用攻击
但需要强调的是,即使进行这些改进,基于LFSR的流密码在现代密码学中已经较少使用。实际应用中更推荐使用经过充分分析和标准化的算法,如:
- ChaCha20: 现代流密码,安全性高,性能优秀
- AES-CTR: 将分组密码AES用于流密码模式
- AES-GCM: 提供加密和认证的组合模式
七、结语
本题是一道典型的LFSR流密码破解挑战,通过分析我们学习到:
- LFSR的工作原理: 理解了线性反馈移位寄存器的状态更新机制和输出生成过程
- 线性密码的弱点: 认识到纯线性系统容易受到代数攻击,可以通过约束求解器破解
- Z3求解器的应用: 掌握了使用SMT求解器进行密码分析的方法,包括符号变量创建、约束添加和结果提取
- 实现细节的重要性: 学会了注意编码问题、类型一致性等实现细节,这些往往是解题成败的关键
- 现代密码学原则: 了解了安全密码系统应该具备的特性,包括足够的密钥长度、非线性组件、充分的轮数等
这道题目不仅是一次密码破解的实践,更是对密码学基本原理和现代密码分析技术的深入学习。通过这类CTF挑战,我们可以更好地理解密码系统的设计原则和安全性要求,为实际的安全工作打下坚实基础。
参考资料:
- Z3 Solver官方文档: https://github.com/Z3Prover/z3
- 《应用密码学》(Applied Cryptography) – Bruce Schneier
- 《现代密码学》(Introduction to Modern Cryptography) – Jonathan Katz, Yehuda Lindell
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《zer0lfsr CTF密码学题目技术解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论