Abstract
The alternating step generator is a well-known keystream generator consisting of two stop/go clocked LFSRs, LFSR1 and LFSR2, whose clocks are controlled by another LFSR, LFSR3, which is clocked regularly. A probabilistic analysis of this generator is conducted which shows that the posterior probabilites of individual bits of the first derivatives of the regularly clocked LFSR1 and LFSR2 sequences, when conditioned on a given segment of the first derivative of the keystream sequence, can be computed efficiently in a number of probabilistic models of interest. The expected values of these probabilities, for a random keystream sequence, are derived by an approximate theoretical analysis and are also verified by systematic computer experiments. It is pointed out that these posterior probabilities can be enhanced in a resynchronization scenario and thus used for a low-complexity fast correlation attack on the two LFSRs. More generally, it is argued that even without resynchronization these probabilities may be significantly different from one half for fast correlation attacks based on iterative decoding algorithms to be successful, although with incresead complexity. A related method for computing the posterior probabilities of individual bits of the LFSR3 sequence, when conditioned on both the keystream sequence and the LFSR1 and LFSR2 sequences, is also developed. As these posterior probabilities are much more different from one half, they can be used for a low-complexity fast correlation attack on LFSR3, provided that the initial states of LFSR1 and LFSR2 are previously reconstructed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Coppersmith, H. Krawczyk and Y. Mansour, The shrinking generator, Advances in Cryptology-CRYPTO'93, Lecture Notes in Computer Science, Vol. 773 (1993) pp. 22-39.
J. Daemen, R. Govaerts and J. Vandewalle, Resynchronization weakness in synchronous stream ciphers, Advances in Cryptology-EUROCRYPT '93, Lecture Notes in Computer Science, Vol. 765 (1994) pp. 159-167.
J. Dj. Golić and R. Menicocci, Edit distance correlation attack on the alternating step generator, Advances in Cryptology-CRYPTO '97, Lecture Notes in Computer Science, Vol. 1294 (1997) pp. 499-512.
J. Dj. Golić, Recent advances in stream cipher cryptanalysis, Publications de l'Institut Mathematique, Vol. (64/78) (1998) pp. 183-204.
J. Dj. Golić and R. Menicocci, Edit probability correlation attack on the alternating step generator, Sequences and their Applications-SETA '98, Discrete Mathematics and Theoretical Computer Science, C. Ding, T. Helleseth and H. Niederreiter (eds.), Springer-Verlag, (1999) pp. 213-227.
J. Dj. Golić, M. Salmasizadeh and E. Dawson, Fast correlation attacks on the summation generator, Journal of Cryptology, Vol. 13 (2000) pp. 245-262.
J. Dj. Golić, Correlation analysis of the shrinking generator, Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science, Vol. 2139 (2001) pp. 440-457.
D. Gollmann and W.G. Chambers, Clock-controlled shift registers: A review, IEEE Journal on Selected Areas in Communications, Vol. 7 (May 1989) pp. 525-533.
C. G. Güunther, Alternating step generators controlled by de Bruijn sequences, Advances in Cryptology-EUROCRYPT '87, Lecture Notes in Computer Science, Vol. 304 (1988) pp. 5-14.
T. Johansson, Reduced complexity correlation attacks on two clock-controled generators, Advances in Cryptology-ASIACRYPT '98, Lecture Notes in Computer Science, Vol. 1514 (1998) pp. 342-357.
T. Johansson and F. Jonnson, Improved fast correlation attacks on stream ciphers via convolutional codes, Advances in Cryptology-EUROCRYPT '99, Lecture Notes in Computer Science, Vol. 1592 (1999) pp. 347-362.
W. Meier and O. Staffelbach, Fast correlation attacks on certain stream ciphers, Journal of Cryptology, Vol. 1 (1989) pp. 159-176.
A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, FL (1997).
M. J. Mihaljević and J. Dj. Golić, A comparison of cryptanalytic principles based on iterative error-correction, Advances in Cryptology-EUROCRYPT '91, Lecture Notes in Computer Science, Vol. 547 (1991) pp. 527-531.
M. J. Mihaljević, M.P.C. Fossorier and H. Imai, A low-complexity and high-performance algorithm for the fast correlation attack, Fast Software Encryption-FSE 2000, Lecture Notes in Computer Science, Vol. 1978 (2001) pp. 196-212.
B. Schneier, Applied Cryptography, Wiley, New York (1996).
L. Simpson, J. Dj. Golić, M. Salmasizadeh and E. Dawson, A fast correlation attack on multiplexer generators, Information Processing Letters, Vol. 70 (1999) pp. 89-93.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Golić, J.D., Menicocci, R. Correlation Analysis of the Alternating Step Generator. Designs, Codes and Cryptography 31, 51–74 (2004). https://doi.org/10.1023/A:1027386519887
Issue Date:
DOI: https://doi.org/10.1023/A:1027386519887