对比特搜索生成器的猜测确定攻击

贾艳艳; 胡予濮; 高军涛

doi:10.3724/SP.J.1146.2010.00030

对比特搜索生成器的猜测确定攻击

doi: 10.3724/SP.J.1146.2010.00030

基金项目:

国家自然科学基金(60833008)，国家973计划项目(2007CB311201)和广西信息与通讯技术重点实验室基金(20902)资助课题

计量
- 文章访问数: 3725
- HTML全文浏览量: 168
- PDF下载量: 632
- 被引次数: 0
出版历程
- 收稿日期: 2010-01-12
- 修回日期: 2010-07-09
- 刊出日期: 2010-12-19

Guess-and-determine Attack on the Bit-search Generator

摘要

摘要: 针对具有低重量反馈多项式的比特搜索生成器(BSG)，利用猜测确定攻击的思想提出了一种快速密钥恢复攻击。该算法基于BSG序列的差分构造特点，首先由截获的密钥流恢复出候选差分序列，然后用反馈多项式对候选差分序列进行校验，以此减少需要求解的L维线性方程系统的数量，从而大大减少了算法所需的复杂度。理论分析和仿真结果表明，对于反馈多项式的重量小于10的BSG，该算法明显优于现有的攻击方法。特别地当反馈多项式的重量为3时，该算法能够将最好的攻击结果O(L320.5L)降低到O(L20.5L)。
- 流密码 /
- 密码分析学 /
- 比特搜索生成器 /
- 猜测确定攻击 /
- 复杂度分析
Abstract: For the Bit-Search-Generators (BSG) with a low weight feedback polynomial, a fast key recovery algorithm is presented using the ideas of the guess-and-determine attack. A candidate differential sequence is recovered firstly from the intercepted keystream sequence based on the differential construction of the BSG sequence. Then the feedback polynomial is used to check the candidate differential sequence, which will reduce the number of the linear equation systems of L dimensions thus to reduce significantly the complexity of the algorithm. Theoretical analysis and simulation experiment results show that, when the weight of the feedback polynomial is less than 10, the complexity of the attack is noticeably better than that of the existing methods. Specially, the attack complexity can be significantly reduced from the best known attack complexity O(L320.5L) to O(L20.5L) when the weight is 3.
- Stream cipher /
- Cryptanalysis /
- Bit-Search Generator (BSG) /
- Guess-and-determine attacks /
- Complexity analysis

HTML全文

参考文献(1)

[1] Coppersmith D.[J].Krawczyk D, and Mansour Y. The shrinking generator[C]. CRYPTO93. Santa Barbara, USA, Springer- Verlag.1993,:- [2] Meier W and Staffelbach O. The self-shrinking generator[C]. EUROCRYPT94. Santa Barbara, USA, Springer-Verlag, 1994: 205-214. [3] Gouget A and Sibert H. The bit-search generator[C]. In The State of the Art of Stream Ciphers: Workshop Record, Brugge, Belgium, 2004: 60-68. [4] Debraize B and Goubin L. Guess-and-determine algebraic attack on the self-shrinking generator[C]. FSE 2008. Lausanne, Switzerland, Spinger-Verlag, 2008: 235-252. [5] Kanso A A. Modified clock-controlled alternating step generators[J].Computer Communications.2009, 32(5):787-799 [6] Hell M and Johansson T. Some attacks on the bit-search generator[C]. FSE 2005. Berlin, Germany, Springer-Verlag, 2005: 215-227. [7] Hell M and Johansson T. Two new attacks on the self-shrinking generator[J].IEEE Transactions on Information Theory.2006, 52(8):3837-3843 [8] Gouget A, Sibert H, Berbain C, and Coutois N, et al.. Analysis of the bit-search generator and sequence compression techniques[C]. FSE 2005. Berlin, Germany, Spinger-Verlag, 2005: 196-214. [9] 臧玉亮，韩文报. 线性反馈移位寄存器的差分能量攻击[J].电子与信息学报.2009, 31(10):2406-2410浏览 Zang Yu-liang and Han Wen-bao. Differential power attack on linear feedback shift register[J].Journal of Electronics Information Technology.2009, 31(10):2406-2410 [10] Altug Y, Ayerden N P, Mihcak M K, and Anarim E. A note on the periodicity and the output rate of bit search type generators [J].IEEE Transactions on Information Theory.2008, 54(2):666-679 [11] Coppersmith D and Winograd S. Matrix multiplication via arithmetic progression[J].Journal Symbolic Computation.1990, 9(3):251-280 [12] Strassen V. Gaussian elimination is not optimal[J]. Numerische Mathematic, 1969, 14(3): 354-356.

施引文献

资源附件(0)

访问统计