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

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

针对具有低重量反馈多项式的比特搜索生成器(BSG),利用猜测确定攻击的思想提出了一种快速密钥恢复攻击。该算法基于BSG序列的差分构造特点,首先由截获的密钥流恢复出候选差分序列,然后用反馈多项式对候选差分序列进行校验,以此减少需要求解的L维线性方程系统的数量,从而大大减少了算法所需的复杂度。理论分析和仿真结果表明,对于反馈多项式的重量小于10的BSG,该算法明显优于现有的攻击方法。特别地当反馈多项式的重量为3时,该算法能够将最好的攻击结果O(L320.5L)降低到O(L20.5L)。

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.