Abstract
The Shrinking Generator and the Alternating Step Generator are two of the most well known clock-controlled stream ciphers. We consider correlation attacks on these two generators, based on an identified relation to the decoding problem for the deletion channel and the insertion channel, respectively. Several ways of reducing the decoding complexity are proposed and investigated, resulting in “divide-and-conquer” attacks on the two generators having considerably lower complexity than previously known attacks.
Supported by the Foundation for Strategic Research - PCC under Grant 97-130.
Chapter PDF
Similar content being viewed by others
References
D. Coppersmith, H. Krawczyk, and Y. Mansour, “The shrinking generator, Lecture Notes in Computer Science 773 (CRYPTO’93), pp. 22–39, 1994.
T. Cover, A. Thomas, Elements of Information Theory, Wiley and Sons, 1991.
A.S. Dolgapolov, “Capacity bounds for a channel with synchronization errors”, Problemy Peredachi Informatsii, 26, pp. 27–37, 1990.
J. Golic’, and L. O’Connor, “Embedding and probabilistic correlation attacks on clock-controlled shift registers”, Lecture Notes in Computer Science 950 (EUROCRYPT’94), pp. 230–243, 1995.
J. Golic’, M. Mihaljevic’, “A generalized correlation attack on a class of stream ciphers based on the Levenstein distance“, Journal of Cryptology, 3 (1991), pp. 201–212.
J. Golic’, “Towards fast correlation attacks on irregularly clocked shift registers”, Lecture Notes in Computer Science 921 (EUROCRYPT’95), pp. 248–262, 1995.
J. Golic’, “Intrinsic statistical weakness of keystream generators”, Lecture Notes in Computer Science 917 (ASIACRYPT’94), pp. 91–103, 1995.
C.G. Günther, “Alternating step generators controlled by de Bruijn sequences”, Lecture Notes in Computer Science 304 (EUROCRYPT’87), pp. 5–14, 1988.
P. Hall, G. Dowling, “Approximate string matching”, Computing Surveys, 12, pp. 381–402, 1980.
H. Krawczyk, “The shrinking generator: Some practical considerations, Lecture Notes in Computer Science 809 (FSE), pp. 45–46, 1994.
W. Meier, and O. Staffelbach, “Fast correlation attacks on certain stream ciphers”, Journal of Cryptology, 1, pp. 159–176, 1989.
A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
T. Siegenthaler, “Correlation-immunity of nonlinear combining functions for cryptographic applications”, IEEE Trans. on Info. Theory, 30 (1984), pp. 776–780.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johansson, T. (1998). Reduced Complexity Correlation Attacks on Two Clock-Controlled Generators. In: Ohta, K., Pei, D. (eds) Advances in Cryptology — ASIACRYPT’98. ASIACRYPT 1998. Lecture Notes in Computer Science, vol 1514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49649-1_27
Download citation
DOI: https://doi.org/10.1007/3-540-49649-1_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65109-3
Online ISBN: 978-3-540-49649-6
eBook Packages: Springer Book Archive