单字节种子递推流密码:已知明文前缀爆破 256 个种子
ctf/crypto · verified
一句话结论
自定义流密码只用 1 字节随机种子初始化密钥流,后续字节由确定性递推 key[i]=gen(key[i-1]) 生成,再与明文异或;由于种子空间只有 256,攻击者用已知明文前缀 DawgCTF{ 遍历所有种子、生成密钥流并异或,即可筛出正确明文。
原理
- 加密逻辑:
start = os.urandom(1),key[0]=start,key[i]=gen(key[i-1]),ct = key xor flag。gen是一个模 255 的非线性递推,但完全确定。 - 密钥流的全部不确定性来自
key[0],只有 256 种可能;给定密文长度,攻击者可以枚举 256 个种子,各自生成同样长度的密钥流并异或,得到 256 个候选明文。 - 题目/协议通常已知明文前缀(如
DawgCTF{)或格式约束,用前缀过滤即可唯一确定种子;若没有前缀,可用可打印率、语言模型或文件头特征筛选。 - 该攻击与递推函数的具体形式无关,只要种子空间小且密钥流确定;即使
gen很复杂,256 次枚举仍然可行。 - 变体:种子为 2 字节(65536 次)、种子来自时间戳/进程 ID(可预测)、递推可逆(可由密钥流反推种子)。
触发条件
- 加密使用单字节/小空间种子初始化流密码,且种子未与密钥或随机数组合。
- 攻击者已知密文,且知道或能猜测明文前缀/格式。
- 密钥流生成函数完全确定、无外部随机性。
- 加密实现没有使用标准 CSPRNG 或认证加密。
利用步骤
- 从题目代码/二进制中还原
gen函数与密钥流生成顺序。 - 读取密文
ct,确定长度。 - 对
start从 0 到 255:生成key[0..len(ct)-1],计算pt = ct xor key。 - 用已知前缀(如
DawgCTF{)过滤候选;若多个候选,增加已知明文或检查可打印率。 - 输出匹配的明文,提取 flag。
PoC
from binascii import unhexlify
ct = bytes.fromhex(
"9f2eadbd998e9ca1aab6bfbba9bf85afa9bf85a9bfb9a8bfaea985b3b485a3b5"
"afa885a9aea8bfbbb785b9b3aab2bfa8a985ece3b8bcbfebe3eebbbceee9bcea"
"b9bea7"
)
def gen(start):
return (((6 * 7) * (start - 6) * 7) + ((start * 6) - 7) * (start ^ 6)) % 255
known = b"DawgCTF{"
for s in range(256):
key = bytearray([s])
for i in range(1, len(ct)):
key.append(gen(key[i - 1]))
pt = bytes(c ^ k for c, k in zip(ct, key))
if pt.startswith(known):
print(pt.decode())
break
变体与关联
- 变体:种子为 2 字节或多字节但可枚举;种子来自
time()、PID、rand()等可预测源。 - 变体:递推可逆时,可由已知密钥流片段反推种子,而不必枚举。
- 变体:密钥流与明文/位置相关(如
key[i] = gen(key[i-1], i)),仍可按种子枚举。 - 关联:[[ctf-crypto-xor-keystream-reuse-known-plaintext]](密钥流重用)、[[ctf-crypto-lfsr-known-plaintext-state-recovery]](LFSR 状态恢复)、[[crypto-prng-time-seeded-rand-rc4-auth-forge]](时间种子)。
检测与防御
- 防御:不要用 1 字节种子或可预测值初始化流密码;使用 CSPRNG(
secrets、os.urandom)生成足够长的密钥。 - 防御:使用标准 AEAD(AES-GCM/ChaCha20-Poly1305),并对密文做完整性校验;不要自定义递推流密码。
- 检测:代码中出现
os.urandom(1)、单字节种子、key[i]=gen(key[i-1])、ct=key xor flag等模式。 - 响应:确认密钥空间过小后,视为加密失效,轮换密钥并重新加密历史数据。