比特搜索生成器的快速密钥恢复攻击

基金项目:

国家自然科学基金(60833008;60803149);国家973计划(2007CB311201)

详细信息

Fast Key Recovery Attack on the Bit-Search Generator

Key Laboratory of Computer Networks and Information Security of Ministry of Education,Xidian University Xi'an 710071

摘要: 针对比特搜索生成器，利用Martin Hell关于自缩生成器的攻击思想，提出了一种基于多段密钥流的概率快速密钥恢复攻击。与目前已知的最好攻击结果相比，该攻击能够将计算复杂度从O(20.5LL3)降低到O(20.43LL3)，特别地，当L为96时，计算复杂度可以达到O(20.39LL3)，所需的数据复杂度为O(NL)。实验结果表明，随着密钥段数的增多，算法的计算复杂度明显减少；密钥长度越长，该算法的攻击效果越好。
- 比特搜索生成器 /
- 密钥流生成器 /
- 密钥恢复攻击 /
- 缩减生成器 /
- 流密码
Abstract: For the bit-search generator, a fast probabilistic key recovery attack based on multi segments of keystream bites is presented using the idea of Martin Hell's attack on the self-shrinking generator. Compared with the best known attack, the attack complexity can be significantly reduced from O(20.5LL3) to O(20.43LL3) if we have O(NL) of keystream bits. Here L is the length of the linear feedback shift register (LFSR); N is the number of the segments of keystream bits. The experimental results show that: the complexity of this algorithm can be significantly degraded as the number of attacks increases; The longer the length of the key is, the more efficient our attack is.
- bit-search generator /
- keystream generator /
- key recovery attack /
- shrinking generator /
- stream ciphers