Abstract
A statistical approach to cryptanalysis of a memoryless function of clock-controlled shift registers is introduced. In the case of zero-order correlation immunity, an algorithm for a shift register initial state reconstruction based on the sequence comparison concept is proposed. A constrained Levenshtein distance relevant for the cryptanalysis is defined and a novel recursive procedure for its efficient computation is derived. Preliminary experimental results are given and open theoretic problems are discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. Chvatal, D. Sankoff, Longest common subsequences of two random sequences, J. Appl. Probab., pp. 306–315, 1975.
J. Dj. Golic, On the linear complexity of functions of periodic GF(q) sequences, IEEE Trans. Inform. Theory, vol. 35, pp. 69–75, Jan.1989.
D. Gollman, W. G. Chambers, Clock-controlled shift registers: a review, IEEE J. Select. Areas Comm., vol. 7, pp. 525–533, May 1989.
A. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Phys. Dokl., vol. 10, pp. 707–710, 1966.
W. Meier, O. Staffelbach, Fast correlation attacks on certain stream ciphers, J. Cryptology, vol. 1, pp. 159–176, 1989.
M.J. Mihaljevic, J. Dj. Golic, 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, pp. 165–175, Springer-Verlag, Berlin, 1990.
B. J. Oommen, Constrained string editing, Inform. Sci., vol. 40, pp. 267–284, 1986.
B. J. Oommen, Recognition of noisy subsequences using constrained edit distance, IEEE Trans. Pattern Anal. Mach. Intell., vol. 9, pp. 676–685, Sept. 1987.
B. J. Oommen, Correction to “Recognition of noisy subsequences using constrained edit distance,” IEEE Trans. Pattern Anal. Mach. Intell, vol. 10, pp. 983–984, Nov.1988.
D. Sankoff, J. B. Kruskal, Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983.
T. Siegenthaler, Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Trans. Inform. Theory, vol. 30, pp. 776–780, Sept.1984.
T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE Trans. Comput. vol. 34, pp. 81–85, Jan.1985.
Author information
Authors and Affiliations
Additional information
Following [11], a Boolean function f(x 1,..., x n) is said to be mth-order correlation immune if m is the maximum integer such that the random variable f(X 1,..., X n) is statistically independent of every set of m random variables chosen from the balanced and independent binary random variables X 1,..., X n.
Rights and permissions
About this article
Cite this article
Golić, J.D., Mihaljević, M.J. A generalized correlation attack on a class of stream ciphers based on the Levenshtein distance. J. Cryptology 3, 201–212 (1991). https://doi.org/10.1007/BF00196912
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00196912