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.
2010, Vol. 32 
