Fast correlation attacks on certain stream ciphers

Two new correlation attacks are presented to determine the initial digits of a, provided that the numbert of feedback taps is small, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000).

Abstract

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 ifp≤0.75). The computational complexity of Algorithm A is of orderO(2ck), 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 probabilitiesp≤0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk≥100 andt≥10).