Abstract
A comparison of two different approaches to fast correlation attacks on stream ciphers is conducted. One is based on standard or modified iterative probabilistic decoding algorithms, and the other is a recent, so-called free energy minimisation approach. Two different comparisons are presented: one based on the Hamming distance and the other on error-free information sets. The results indicate that a modified iterative probabilistic decoding attack outperforms the free energy minimisation attack in high noise probability regions.
This research was supported in part by the Science Fund of Serbia, Grant #0403, through the Institute of Mathematics, Serbian Academy of Arts and Sciences.
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 stream ciphers,” Advances in Cryptology — EUROCRYPT '91, Lecture Notes in Computer Science, vol. 547, D. W. Davies ed., Springer-Verlag, pp. 176–185, 1991.
G. C. Clark, Jr. and J. B. Cain, Error-Correcting Coding for Digital Communications. New York: Plenum Press, 1982.
R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21–28, Jan. 1962.
J. Dj. Golić, M. Salmasizadeh, A. Clark, A. Khodkar, and E. Dawson, “Discrete optimisation and fast correlation attacks,” Cryptographic Policy and Algorithms — Brisbane '95, Lecture Notes in Computer Science, E. Dawson and J. Golić eds., Springer-Verlag, pp. 188–202, to appear in 1996.
J. Dj. Golić, “On the security of shift register based keystream generators,” Fast Software Encryption — Cambridge '93, Lecture Notes in Computer Science, vol. 809, R. J. Anderson ed., pp. 91–101, 1994.
D. J. C. MacKay, “A free energy minimization framework for inference problems in modulo 2 arithmetic,” Fast Software Encryption — Leuven '94, Lecture Notes in Computer Science, vol. 1008, B. Preneel ed., Springer-Verlag, pp. 179–195, 1995.
J. L. Massey, Threshold Decoding. Cambridge, MA, MIT Press, 1963.
W. Meier and O. Staffelbach, “Fast correlation attacks on certain stream ciphers,” Journal of Cryptology, vol. 1, pp. 159–176, 1989.
M. J. Mihaljević and J. Dj. Golić, “A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence,” Advances in Cryptology — AUSCRYPT '90, Lecture Notes in Computer Science, vol. 453, J. Seberry and J. Pieprzyk eds., Springer-Verlag, pp. 165–175, 1990.
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, D. W. Davies ed., Springer-Verlag, pp. 527–531, 1991.
M. J. Mihaljević and J. Dj. Golić, “Convergence of a Bayesian iterative error-correction procedure on a noisy shift register sequence,” Advances in Cryptology — EUROCRYPT '92, Lecture Notes in Computer Science, vol. 658, R. A. Rueppel ed., Springer-Verlag, pp. 124–137, 1993.
T. Siegenthaler, “Decrypting a class of stream ciphers using ciphertext only,” IEEE Trans. Comput, vol. 34, pp. 81–85, Jan. 1985.
K. Zeng and M. Huang, “On the linear syndrome method in cryptanalysis,” Advances in Cryptology — CRYPTO '88, Lecture Notes in Computer Science, vol. 403, S. Goldwasser ed., Springer-Verlag, pp. 469–478, 1990.
M. V. Živković, “On two probabilistic decoding algorithms for binary linear codes,” IEEE Trans. Inform. Theory, vol. IT-37, pp. 1707–1716, Nov. 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Clark, A., Golić, J.D., Dawson, E. (1996). A comparison of fast correlation attacks. In: Gollmann, D. (eds) Fast Software Encryption. FSE 1996. Lecture Notes in Computer Science, vol 1039. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60865-6_50
Download citation
DOI: https://doi.org/10.1007/3-540-60865-6_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60865-3
Online ISBN: 978-3-540-49652-6
eBook Packages: Springer Book Archive