文章总结： 本文深入分析了一道CTF密码学题目，讲解LFSR流密码的工作原理、安全漏洞及暴力破解方法。通过逆向分析加密脚本，发现flag格式约束导致密钥空间仅为2^19，利用Python编写脚本枚举所有可能，成功破解出flag{1110101100001101011}。文章详细剖析了LFSR算法实现、密钥生成流程，并讨论了其线性性质带来的安全缺陷，强调在实际应用中必须使用标准加密算法而非自行设计。 综合评分： 85 文章分类： CTF,密码学,漏洞分析,安全开发,逆向分析
深入剖析：LFSR流密码的暴力破解之道
原创
破镜安全 破镜安全
破镜安全
2026年2月8日 08:02 四川
深入剖析：LFSR流密码的暴力破解之道
前言
在现代密码学中，流密码是一类重要的加密方式，它通过生成伪随机密钥流来加密数据。LFSR（Linear Feedback Shift Register，线性反馈移位寄存器）作为流密码的经典实现，在资源受限环境下有着广泛应用。本文将通过分析一道CTF密码学题目，深入理解LFSR的工作原理、安全特性以及攻击方法。
一、题目初探
拿到题目后，我们首先需要了解有哪些文件，以及它们分别的作用。
1.1 文件清单
题目提供了两个文件：
streamgame1.py：Python加密脚本key：加密后的输出文件
让我们先查看这两个文件的基本信息。
使用十六进制查看器查看key文件：
xxd key
输出结果：
00000000: 5538 f742 c10d b2c7 ede0 243a U8.B......$:
可以看到key文件是一个12字节的二进制文件，内容为：5538f742c10db2c7ede0243a
1.2 题目类型判断
通过文件名”streamgame”可以初步判断，这是一道关于流密码的题目。流密码的特点是通过生成密钥流来加密数据，我们需要通过分析加密算法来找到原始的flag。
二、加密脚本深度分析
让我们详细分析streamgame1.py这个加密脚本。
2.1 Flag格式约束
脚本开头有三个断言：
from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25
这三行代码告诉我们：
- flag以”flag{“开头（5个字符）
- flag以”}”结尾（1个字符）
- flag总长度为25个字符
因此，flag中间的内容有 25 – 6 = 19 个字符。
这是一个非常重要的信息，它限制了我们的搜索空间。
2.2 LFSR核心函数
脚本的核心是LFSR函数：
def lfsr(R,mask):
output = (R << 1) & 0xffffff
i=(R&mask)&0xffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
这个函数看起来很简洁，但包含了LFSR的核心逻辑。让我们逐行分析。
2.3 加密主流程
R=int(flag[5:-1],2)
mask = 0b1010011000100011100
f=open("key","ab")
for i in range(12):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
f.write(chr(tmp))
f.close()
关键信息：
flag[5:-1]提取了flag中大括号内的内容（19个字符）int(...,2)表示将字符串按二进制解析，这说明flag内部的19个字符都是’0’或’1′- 外层循环12次，生成12个字节（对应key文件的12字节）
- 内层循环8次，每次生成1个bit，组成1个字节
三、LFSR算法原理详解
LFSR是密码学中的经典算法，让我们深入理解它的工作机制。
3.1 什么是LFSR
LFSR（线性反馈移位寄存器）由三个部分组成：
- 移位寄存器：存储当前状态（本题中是R）
- 反馈函数：计算新的bit（通过异或运算）
- 掩码：决定哪些位参与反馈计算（本题中是mask）
3.2 LFSR函数逐行解析
让我们详细分析每一行代码的作用：
第1步：左移操作
output = (R << 1) & 0xffffff
R << 1：将R的所有位向左移动1位& 0xffffff：只保留低24位（0xffffff是24个1的二进制数）- 作用：为寄存器腾出最低位的位置
举例：如果R = 0b1101（十进制13）
R = 0b1101
R << 1 = 0b11010
第2步：提取掩码位
i=(R&mask)&0xffffff
R&mask：按位与操作，提取mask中为1的位- 作用：选择参与反馈计算的位
举例：
R = 0b1010110
mask = 0b1010100
-----------------
i = 0b1010100 (只保留mask为1的位置的值)
第3步：计算反馈位（核心）
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
这是LFSR的核心：对选中的所有位进行异或运算。
让我们用一个具体的例子来说明。假设i = 0b1101（十进制13）：
初始：lastbit = 0, i = 0b1101
循环1：i&1 = 1, lastbit = 0^1 = 1, i = 0b110
循环2：i&1 = 0, lastbit = 1^0 = 1, i = 0b11
循环3：i&1 = 1, lastbit = 1^1 = 0, i = 0b1
循环4：i&1 = 1, lastbit = 0^1 = 1, i = 0b0
结果：lastbit = 1
这个过程实际上是计算i中所有1的个数的奇偶性：
- 如果1的个数是奇数，lastbit = 1
- 如果1的个数是偶数，lastbit = 0
第4步：更新寄存器
output^=lastbit
return (output,lastbit)
output^=lastbit：将计算出的反馈位填入output的最低位- 返回新的寄存器状态和输出位
3.3 LFSR工作流程图解
让我们用一个完整的例子来演示LFSR的一次迭代：
假设：R = 0b10101, mask = 0b10100
步骤1：左移
output = (0b10101 << 1) & 0xffffff = 0b101010
步骤2：提取掩码位
i = 0b10101 & 0b10100 = 0b10100
步骤3：计算反馈
0b10100中有2个1，偶数个，所以lastbit = 0
步骤4：更新
output = 0b101010 ^ 0 = 0b101010
返回：(0b101010, 0)
3.4 字节生成过程
了解了单次LFSR操作后，我们来看如何生成一个字节：
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
这个循环执行8次，每次：
- 调用lfsr生成1个bit
- 将这个bit拼接到tmp中
- 8次后，tmp就是一个完整的字节（8位）
例如，如果8次LFSR分别输出：1, 0, 1, 1, 0, 0, 1, 1
第1次：tmp = 0b1
第2次：tmp = 0b10
第3次：tmp = 0b101
第4次：tmp = 0b1011
第5次：tmp = 0b10110
第6次：tmp = 0b101100
第7次：tmp = 0b1011001
第8次：tmp = 0b10110011 (十进制179)
最终生成的字节值为179（0xB3）。
四、加密流程完整梳理
现在让我们把整个加密过程串联起来。
4.1 初始化阶段
R=int(flag[5:-1],2)
mask = 0b1010011000100011100
- 提取flag中的19个二进制字符
- 将其转换为整数作为LFSR的初始状态
- mask固定为0b1010011000100011100（十进制340252）
例如，如果flag = “flag{1110101100001101011}”：
flag[5:-1] = "1110101100001101011"
R = int("1110101100001101011", 2) = 481387
4.2 密钥生成阶段
for i in range(12): # 外层循环12次，生成12字节
tmp=0
for j in range(8): # 内层循环8次，生成8位
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
f.write(chr(tmp))
整个过程：
- LFSR运行 12 × 8 = 96 次
- 生成96个bit
- 每8个bit组成1个字节
- 最终得到12字节的密钥流
4.3 输出结果
12字节的密钥流被写入key文件，这就是我们看到的：
5538f742c10db2c7ede0243a
五、安全性分析：为什么可以破解？
理解了算法后，我们需要分析它的安全性。
5.1 密钥空间计算
关键问题：flag中间有多少种可能的组合？
- flag中间有19个字符
- 每个字符只能是’0’或’1′
- 可能的组合数 = 2^19 = 524,288种
这是一个相对较小的搜索空间，在现代计算机上可以在短时间内遍历完成。
5.2 算法的确定性
LFSR是完全确定性的算法：
- 相同的输入（R和mask）→相同的输出
- 没有使用随机数或时间戳
- 加密过程完全可复现
这意味着我们可以：
- 枚举所有可能的19位二进制串
- 对每个候选值运行加密算法
- 比对生成的结果与给定的key文件
- 找到匹配的就是答案
5.3 已知密文攻击
在这个题目中，我们拥有：
- 完整的加密算法（streamgame1.py）
- 加密后的输出（key文件）
- flag的格式约束
这是典型的”已知密文攻击”场景。由于密钥空间足够小，暴力破解是可行的。
5.4 输出长度的作用
12字节（96位）的输出提供了足够的”区分度”：
- 对于不同的输入，生成相同输出的概率极低
- 12字节有2^96种可能的值
- 而我们只有2^19种输入
- 碰撞概率：2^19 / 2^96 ≈ 1.9 × 10^-24（几乎为0）
因此，我们可以确信找到的匹配结果就是正确答案。
六、解题实战
基于以上分析，我们可以编写破解脚本。
6.1 破解思路
核心思路非常直接：
- 读取题目给定的key文件
- 枚举所有可能的19位二进制串（从000…0到111…1）
- 对每个候选值构造flag，运行加密算法
- 将生成的密钥与原始key比对
- 找到匹配的即为答案
6.2 破解脚本实现
#encoding:utf8
def read_key_origin():
fin=open("key","rb")
res = fin.read()
fin.close()
return res
key = read_key_origin()
print("Key content (hex):", key.hex())
print("Key length:", len(key))
def crack(flag):
# 验证flag格式
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25
global key
# LFSR函数（与加密脚本相同）
def lfsr(R,mask):
output = (R << 1) & 0xffffff
i=(R&mask)&0xffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
# 提取flag中间的二进制串并转换为整数
R=int(flag[5:-1],2)
mask = 0b1010011000100011100
# 生成密钥流
s=b""
for i in range(12):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
s+=bytes([tmp])
# 比对结果
if s==key:
print("Found flag:", flag)
exit()
def enum():
count = 0
# 递归枚举所有19位二进制串
def _enum(s,dep):
nonlocal count
if 19==dep:
count += 1
if count % 50000 == 0:
print(f"Progress: {count}/524288")
flag = "flag{"+s+"}"
crack(flag)
return
for bit in "01":
_enum(s+bit,dep+1)
_enum("",0)
def main():
enum()
print("No match found")
if '__main__'==__name__:
main()
6.3 脚本关键点解析
枚举策略
使用递归方式枚举所有可能的二进制串：
def _enum(s,dep):
if 19==dep: # 达到19位，构造完整flag
flag = "flag{"+s+"}"
crack(flag)
return
for bit in "01": # 尝试添加0或1
_enum(s+bit,dep+1)
这种递归方法会生成所有可能的组合：
""
├─ "0"
│ ├─ "00"
│ │ ├─ "000..." (继续递归)
│ │ └─ "001..." (继续递归)
│ └─ "01"
│ ├─ "010..." (继续递归)
│ └─ "011..." (继续递归)
└─ "1"
├─ "10"
└─ "11"
...
进度显示
if count % 50000 == 0:
print(f"Progress: {count}/524288")
每测试50000个候选值，显示一次进度，让我们知道程序在正常运行。
6.4 运行破解脚本
执行脚本：
python3 solve.py
运行输出：
Key content (hex): 5538f742c10db2c7ede0243a
Key length: 12
Progress: 50000/524288
Progress: 100000/524288
Progress: 150000/524288
Progress: 200000/524288
Progress: 250000/524288
Progress: 300000/524288
Progress: 350000/524288
Progress: 400000/524288
Progress: 450000/524288
Found flag: flag{1110101100001101011}
成功找到flag：flag{1110101100001101011}
从进度可以看出，在遍历了约45万个候选值后找到了答案，整个过程在普通计算机上只需要几秒钟到几分钟。
七、结果验证：确保答案正确
找到flag后，我们必须验证它的正确性。最可靠的方法是反向验证：用找到的flag重新运行加密算法，看是否能生成相同的key文件。
7.1 验证脚本
#encoding:utf8
flag = "flag{1110101100001101011}"
# 验证flag格式
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25
print(f"验证flag: {flag}")
print(f"Flag长度: {len(flag)}")
print(f"Flag中间部分: {flag[5:-1]}")
print(f"中间部分长度: {len(flag[5:-1])}")
def lfsr(R,mask):
output = (R << 1) & 0xffffff
i=(R&mask)&0xffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
# 将flag中间的二进制串转换为整数
R=int(flag[5:-1],2)
mask = 0b1010011000100011100
print(f"\n初始状态R: {R} (0b{bin(R)[2:]})")
print(f"掩码mask: {mask} (0b{bin(mask)[2:]})")
# 生成密钥
generated_key = b""
print("\n生成过程：")
for i in range(12):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
generated_key += bytes([tmp])
print(f"字节 {i}: 0x{tmp:02x} (十进制{tmp})")
print(f"\n生成的密钥 (hex): {generated_key.hex()}")
# 读取原始key文件
with open("key","rb") as f:
original_key = f.read()
print(f"原始密钥 (hex): {original_key.hex()}")
# 对比
if generated_key == original_key:
print("\n========================================")
print("验证成功！生成的密钥与原始密钥完全匹配！")
print(f"正确的Flag是: {flag}")
print("========================================")
else:
print("\n验证失败！密钥不匹配！")
7.2 验证结果
运行验证脚本：
python3 verify.py
输出结果：
验证flag: flag{1110101100001101011}
Flag长度: 25
Flag中间部分: 1110101100001101011
中间部分长度: 19
初始状态R: 481387 (0b1110101100001101011)
掩码mask: 340252 (0b1010011000100011100)
生成过程：
字节 0: 0x55 (十进制85)
字节 1: 0x38 (十进制56)
字节 2: 0xf7 (十进制247)
字节 3: 0x42 (十进制66)
字节 4: 0xc1 (十进制193)
字节 5: 0x0d (十进制13)
字节 6: 0xb2 (十进制178)
字节 7: 0xc7 (十进制199)
字节 8: 0xed (十进制237)
字节 9: 0xe0 (十进制224)
字节 10: 0x24 (十进制36)
字节 11: 0x3a (十进制58)
生成的密钥 (hex): 5538f742c10db2c7ede0243a
原始密钥 (hex): 5538f742c10db2c7ede0243a
========================================
验证成功！生成的密钥与原始密钥完全匹配！
正确的Flag是: flag{1110101100001101011}
========================================
7.3 验证分析
验证结果显示：
- 初始状态：R = 481387，这是将”1110101100001101011″转换为十进制的结果
- 生成过程：12个字节逐一生成，每个字节的值都被记录
- 最终对比：生成的密钥与原始密钥完全一致
这证明了我们找到的flag是100%正确的。
通过验证，我们完整地复现了加密流程：
flag{1110101100001101011}
↓ (提取中间部分)
1110101100001101011
↓ (转换为十进制)
R = 481387
↓ (LFSR算法96次迭代)
12字节密钥流
↓ (输出)
5538f742c10db2c7ede0243a
八、技术深度剖析
8.1 LFSR在密码学中的地位
历史背景
LFSR在密码学历史上占有重要地位：
- 早期被广泛用于加密通信（如A5/1算法用于GSM）
- 硬件实现简单高效
- 在资源受限设备上有优势
现实应用
目前LFSR主要用于：
- 伪随机数生成
- CRC校验码生成
- 扰码器设计
- 某些流密码的组件
8.2 LFSR的优势与局限
优势
- 硬件效率高：只需要移位寄存器和异或门
- 速度快：运算简单，执行速度快
- 可预测的周期：特定配置的LFSR有固定的周期长度
- 理论研究成熟：有完整的数学理论支持
局限
- 线性性质：是线性系统，容易被代数攻击
- 已知明文攻击脆弱：只需少量已知明文就能恢复状态
- 密钥流可预测：一旦知道初始状态和反馈函数，输出完全确定
- 不适合单独使用：必须与非线性组件结合使用
8.3 本题的安全缺陷总结
本题存在多个致命的安全问题：
1. 密钥空间过小
- 只有19位（2^19 ≈ 52万种可能）
- 现代标准至少需要128位（2^128 ≈ 3.4×10^38）
- 差距：2^128 / 2^19 ≈ 6.5×10^32倍
2. 密钥格式可预测
- 限定为二进制字符串
- 没有使用复杂的密钥派生函数
- 每个字符只有2种选择而非256种
3. 完整的算法泄露
- 攻击者知道完整的加密过程
- 在实际应用中，这违反了Kerckhoffs原则的安全实践
4. 没有使用盐值或IV
- 相同的flag总是产生相同的key
- 无法抵抗重放攻击和字典攻击
5. 单一LFSR的使用
- 没有使用多个LFSR组合
- 没有添加非线性变换
- 线性性质完全暴露
8.4 如何增强LFSR的安全性
如果必须使用LFSR，以下是一些增强方法：
1. 增加密钥长度
# 不安全：19位
R = 19_bit_value
# 较安全：128位或更多
R = 128_bit_value
2. 使用多个LFSR组合
# 使用3个LFSR的输出进行非线性组合
output = (lfsr1() & lfsr2()) ^ lfsr3()
3. 添加非线性滤波器
# 对LFSR输出进行非线性变换
filtered_output = S_box[lfsr_output]
4. 密钥派生函数
# 从用户密码派生强密钥
import hashlib
key = hashlib.pbkdf2_hmac('sha256', password, salt, 100000)
5. 添加初始化向量（IV）
# 每次加密使用不同的IV
R = hash(original_key || IV)
九、CTF中的LFSR题型总览
在CTF竞赛中，LFSR相关题目有多种变体。
9.1 常见题型分类
类型1：暴力破解类（本题属于此类）
- 特征：密钥空间较小（通常小于2^32）
- 解法：枚举所有可能的初始状态
- 难度：简单到中等
类型2：已知明文攻击
- 特征：给出部分明文和对应的密文
- 解法：利用线性性质求解方程组
- 难度：中等
类型3：Berlekamp-Massey算法
- 特征：给出足够长的输出序列
- 解法：使用BM算法恢复LFSR参数
- 难度：中等到困难
类型4：组合LFSR破解
- 特征：多个LFSR组合使用
- 解法：分析组合方式，分别攻破
- 难度：困难
类型5：非线性滤波LFSR
- 特征：LFSR输出经过非线性变换
- 解法：代数攻击或时间记忆权衡攻击
- 难度：困难到非常困难
9.2 解题技巧总结
- 首先评估密钥空间：如果小于2^32，考虑暴力破解
- 寻找线性关系：LFSR本质是线性的，利用这一点
- 观察输出长度：2倍寄存器长度的输出通常足以恢复状态
- 工具使用：SageMath等工具有现成的LFSR分析函数
- 注意边界情况：全0状态、全1状态等特殊情况
十、实际密码系统的启示
10.1 密码系统设计原则
通过这道题目，我们可以总结出安全密码系统的设计原则：
1. 充足的密钥空间
- 最低128位，推荐256位
- 防止暴力破解攻击
2. 密钥的高熵性
- 使用密码学安全的随机数生成器
- 避免可预测的密钥格式
3. 算法的复杂性
- 不依赖算法的保密性（Kerckhoffs原则）
- 但算法本身应足够复杂，抵抗已知攻击
4. 适当的输出处理
- 使用认证加密（AEAD）
- 防止输出泄露内部状态
5. 定期更新和审查
- 密码学是动态领域
- 及时淘汰不安全的算法
10.2 推荐的现代密码算法
在实际应用中，应使用经过充分验证的现代算法：
对称加密
- AES（Advanced Encryption Standard）
- ChaCha20
流密码
- ChaCha20（推荐）
- Salsa20
认证加密
- AES-GCM
- ChaCha20-Poly1305
这些算法经过多年的安全审查，在当前的威胁模型下是安全的。
十一、总结
通过对这道CTF题目的完整分析，我们深入学习了以下内容：
11.1 技术收获
- LFSR原理：理解了线性反馈移位寄存器的工作机制
- 位运算技巧：掌握了左移、右移、异或等位操作
- 密码分析方法：学会了评估密钥空间和设计攻击策略
- Python编程：实现了完整的破解和验证脚本
- 逆向思维：从加密脚本逆推出破解方法
11.2 安全意识
- 密钥长度至关重要：19位密钥在现代计算能力下毫无安全性
- 算法选择需谨慎：不要自己设计密码算法，使用标准算法
- 完整性验证必不可少：找到答案后必须验证
- 安全是系统工程：单一组件的安全不代表整体安全
11.3 学习方法
本题展示了分析密码学问题的标准流程：
- 收集信息（文件分析）
- 理解算法（逐行分析代码）
- 评估安全性（密钥空间计算）
- 设计攻击（编写破解脚本）
- 验证结果（反向验证）
这种系统化的方法可以应用到其他密码学题目和实际的安全分析工作中。
11.4 最后的话
密码学是信息安全的基石，但也是一个充满陷阱的领域。简单的实现往往隐藏着致命的漏洞。通过CTF这样的实战练习，我们可以在安全的环境中学习密码学知识，理解攻击与防御的对抗关系。
记住：在实际应用中，永远使用经过验证的标准密码库，而不是自己实现密码算法。这道题目是学习的极好材料，但其中的做法在现实世界中是绝对不安全的。
希望本文能帮助你深入理解LFSR流密码的原理和安全性分析方法，在未来的CTF竞赛和安全研究中学以致用。
本文涉及的完整代码和文件可在实验环境中复现，建议读者动手实践，加深理解。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《深入剖析：LFSR流密码的暴力破解之道》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论