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).
Article PDF
Similar content being viewed by others
References
W. Blaser and P. Heinzmann, New cryptographic device with high security using public key distribution,IEEE Student Papers, 1982, pp. 145–153.
R. G. Gallager,Low-Density Parity-Check Codes, MIT Press, Cambridge, MA, 1963.
R. A. Rueppel,Analysis and Design of Stream Ciphers, Springer-Verlag, New York, 1986.
T. Siegenthaler, Correlation-immunity of nonlinear combining functions for cryptographic applications,IEEE Trans. Inform. Theory,30, 776–780, 1984.
T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only,IEEE Trans. Comput.,34, 81–85, 1985.
J. H. van Lint,Introduction to Coding Theory, Graduate Texts in Mathematics, Vol. 86, Springer-Verlag, Berlin, 1982
G. Z. Xiao and J. L. Massey, A spectral characterization of correlation-immune combining functions,IEEE Trans. Inform. Theory,34, 569–571, 1988.
Author information
Authors and Affiliations
Additional information
This work was supported in part by GRETAG Ltd., Regensdorf, Switzerland.
Rights and permissions
About this article
Cite this article
Meier, W., Staffelbach, O. Fast correlation attacks on certain stream ciphers. J. Cryptology 1, 159–176 (1989). https://doi.org/10.1007/BF02252874
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02252874