Fast correlation attacks on certain stream ciphers

Suppose that the output of a running key generator employed in a stream cipher is correlated to a linear feedback shift register sequence (LFSR sequence) a with correlation probabilityp>0.5. Then two new correlation attacks (Algorithms A and B) are presented to determine the initial digits of a, provided that the numbert of feedback taps is small (t<10 ifp0.75). The computational complexity of Algorithm A is of orderO(2^ck), wherek denotes the length of the LFSR andc<1 depends on the input parameters of the attack, and Algorithm B is polynomial (in fact, even linear) in the lengthk of the LFSR. These algorithms are much faster than an exhaustive search over all phases of the LFSR, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000). On the other hand, for correlation probabilitiesp0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk100 andt10).This work was supported in part by GRETAG Ltd., Regensdorf, Switzerland.