Fast Key Recovery Attack on the Bit-Search Generator

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.