A New Correlation Attack on LFSR Sequences with High Error Tolerance
Peizhong Lu, Lianzhen Huang · Birkhäuser Basel eBooks · 2004
Let u = (u 1, u 2,…,u n ) be N bits of a linear feedback shift register (LFSR) sequence with L the degree of the feedback polynomial. Let z = (z 1, z 2,…,z N ) be N bits of observed sequence such that P(z i = u i )=1/2 + δ where $$0 < \delta \leqslant \tfrac{1}{2}$$ . This paper presents a new efficient correlation attack on stream ciphers, which is equivalent to solve the problem of recovering the LFSR’s initial state (u = (u 1, u 2,…,u L )from the observed output sequence z. We consider the problem as a decoding problem for a linear [N, L] code. Our new approach has at least three advantages. Firstly, the new algorithm constructs much more independent parity check equations which results in significant decrease both of the decoding errors and of the required length N of the observed sequence. Secondly, by the combination of statistical test and repeatedly using of One-Step decoding algorithm, our novel scheme provides better performance and lower complexity than other reported methods. Thirdly, we find a new formula to describe the relationship between the tendency of attack performance, the weight w of parity check equations, the noise level (δ, and N.