BabyStream - 从LFSR到LPN的完整攻击复现
💡
原文中文，约14900字，阅读约需36分钟。
📝
内容提要
本文介绍了利用RANSAC算法从基于LFSR的流密码中恢复128位初始状态。通过分析非线性项的噪声影响，构建LPN模型，成功恢复密钥并验证，准确率达到93.854%，实现100%复现。
🎯
关键要点
- 利用RANSAC算法从基于LFSR的流密码中恢复128位初始状态。
- 通过分析非线性项的噪声影响，构建LPN模型。
- 成功恢复密钥并验证，准确率达到93.854%。
- 实现100%复现，逐字节匹配原始输出。
- LFSR算法的核心是线性反馈移位寄存器和Feedforward函数。
- 非线性项被视为噪声，形成带噪声的奇偶学习问题。
- RANSAC算法通过随机选择方程组来提高鲁棒性。
- GF(2)上的高斯消元被改进以适应带噪声的系统。
- 通过位运算优化提高了计算效率。
- LPN问题被认为是量子安全的，适用于多种密码学应用。
- 本题的弱点在于噪声率较低，影响安全性。
- 通过增加噪声或维度可以增强系统的安全性。
- 总结了密码分析中的统计方法和数学建模的重要性。
❓
延伸问答
如何利用RANSAC算法恢复LFSR流密码的初始状态？
通过随机选择128个方程，使用RANSAC算法求解，最终恢复128位初始状态，准确率达到93.854%。
LPN问题是什么，它在密码学中有什么重要性？
LPN问题是带噪声的奇偶学习问题，被认为是量子安全的，广泛应用于认证协议和加密方案。
为什么非线性项可以视为噪声？
非线性项的激活概率极低，约6.25%的输出位受非线性项影响，因此可以将其视为噪声。
如何提高LPN问题的安全性？
可以通过增加噪声或提高维度来增强系统的安全性，例如使用256位或512位的LFSR。
RANSAC算法的核心思想是什么？
RANSAC算法通过随机选择最小子集来估计参数，利用大部分正确的方程来接近真实解。
如何验证恢复的初始状态的正确性？
通过将恢复的初始状态代入原始生成器，逐字节复现输出，确保完全一致来验证正确性。
➡️
