Abstract
This paper describes new techniques for fast correlation attacks, based on Gallager iterative decoding algorithm using parity-check equations of weight greater than 3. These attacks can be applied to any key-stream generator based on LFSRs and it does not require that the involved feedback polynomial have a low weight. We give a theoretical analysis of all fast correlation attacks, which shows that our algorithm with parity-check equations of weight 4 or 5 is usually much more efficient than correlation attacks based on convolutional codes or on turbo codes. Simulation results confirm the validity of this comparison. In this context, we also point out the major role played by the nonlinearity of the Boolean function used in a combination generator.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
V. Chepyzhov and B. Smeets. On a fast correlation attack on certain stream ciphers. In Advances in Cryptology-EUROCRYPT’91, number 547 in Lecture Notes in Computer Science, pages 176–185. Springer-Verlag, 1991.
E. Filiol and C. Fontaine. Highly nonlinear balanced Boolean functions with a good correlation-immunity. In Advances in Cryptology-EUROCRYPT’98, number 1403 in Lecture Notes in Computer Science, pages 475–488. Springer-Verlag, 1998.
R.G. Gallager. Low-density parity-check codes. IRE Trans. Inform. Theory, IT-8:21–28, 1962.
R.G. Gallager. Low-density parity-check codes. MIT Press, Cambridge, MA, 1963.
J. Hagenauer, E. Offer, and L. Papke. Iterative decoding of binary block and convolutional codes. IEEE Trans. Inform. Theory, 42(2):429–445, 1996.
T. Johansson and F. Jönsson. Improved fast correlation attack on stream ciphers via convolutional codes. In Advances in Cryptology-EUROCRYPT’99, number 1592 in Lecture Notes in Computer Science, pages 347–362. Springer-Verlag, 1999.
T. Johansson and F. Jönsson. Fast correlation attacks based on turbo code techniques. In Advances in Cryptology-CRYPTO’99, number 1666 in Lecture Notes in Computer Science, pages 181–197. Springer-Verlag, 1999.
F.J. MacWilliams and N.J.A. Sloane. The theory of error-correcting codes. North-Holland, 1977.
W. Meier and O. Staffelbach. Fast correlation attacks on stream ciphers. In Advances in Cryptology-EUROCRYPT’88, number 330 in Lecture Notes in Computer Science, pages 301–314. Springer-Verlag, 1988.
W. Meier and O. Staffelbach. Fast correlation attack on certain stream ciphers. J. Cryptology, pages 159–176, 1989.
W. Meier and O. Staffelbach. Nonlinearity criteria for cryptographic functions. In Advances in Cryptology-EUROCRYPT’89, number 434 in Lecture Notes in Computer Science, pages 549–562. Springer-Verlag, 1990.
M.J. Mihaljević and J.D. Golić. A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence. In Advances in Cryptology-AUSCRYPT’90, number 453 in Lecture Notes in Computer Science, pages 165–175. Springer-Verlag, 1990.
M.J. Mihaljević and J.D. Golić. A comparison of cryptanalytic principles based on iterative error-correction. In Advances in Cryptology-EUROCRYPT’91, number 547 in Lecture Notes in Computer Science, pages 527–531. Springer-Verlag, 1991.
W. T. Penzhorn. Correlation attacks on stream ciphers: computing low-weight parity checks based on error-correcting codes. In Fast Software Encryption 96, number 1039 in Lecture Notes in Computer Science, pages 159–172. Springer-Verlag, 1996.
W.T. Penzhorn and G.J. Kühn. Computation of low-weight parity checks for correlation attacks on stream ciphers. In Cryptography and Coding-5th IMA Conference, number 1025 in Lecture Notes in Computer Science, pages 74–83. Springer-Verlag, 1995.
R.A. Rueppel. Analysis and Design of stream ciphers. Springer-Verlag, 1986.
E.S. Selmer. Linear recurrence relations over finite fields. PhD thesis, University of Bergen, Norway, 1966.
C.E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 27, 1948.
T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inform. Theory, IT-30(5):776–780, 1984.
T. Siegenthaler. Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Computers, C-34(1):81–84, 1985.
K. Zeng, C.H. Yang, and T.R.N. Rao. An improved linear syndrome algorithm in cryptanalysis with applications. In Advances in Cryptology-CRYPTO’90, number 537 in Lecture Notes in Computer Science. Springer-Verlag, 1990.
N. Zierler. Linear recurring sequences. J. Soc. Indus. Appl. Math., 7:31–48, 1959.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Canteaut, A., Trabbia, M. (2000). Improved Fast Correlation Attacks Using Parity-Check Equations of Weight 4 and 5. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_40
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67517-4
Online ISBN: 978-3-540-45539-4
eBook Packages: Springer Book Archive