article

A generalized correlation attack on a class of stream ciphers based on the Levenshtein distance

Authors:

Jovan Dj. Golić,

Miodrag J. MihaljevićAuthors Info & Claims

Journal of Cryptology, Volume 3, Issue 3

Pages 201 - 212

https://doi.org/10.1007/BF00196912

Published: 01 January 1991 Publication History

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.

References

[1]

V. Chvatal, D. Sankoff, Longest common subsequences of two random sequences, J. Appl. Probab., pp. 306-315, 1975.

Crossref

Google Scholar

[2]

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.

Crossref

Google Scholar

[3]

D. Gollman, W. G. Chambers, Clock-controlled shift registers: a review, IEEE J. Select. Areas Comm., vol. 7, pp. 525-533, May 1989.

Digital Library

Google Scholar

[4]

A. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Phys. Dokl., vol. 10, pp. 707-710, 1966.

Google Scholar

[5]

W. Meier, O. Staffelbach, Fast correlation attacks on certain stream ciphers, J. Cryptology, vol. 1, pp. 159-176, 1989.

Digital Library

Google Scholar

[6]

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.

Crossref

Google Scholar

[7]

B. J. Oommen, Constrained string editing, Inform. Sci., vol. 40, pp. 267-284, 1986.

Digital Library

Google Scholar

[8]

B. J. Oommen, Recognition of noisy subsequences using constrained edit distance, IEEE Trans. Pattern Anal. Mach. Intell., vol. 9, pp. 676-685, Sept. 1987.

Digital Library

Google Scholar

[9]

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.

Digital Library

Google Scholar

[10]

D. Sankoff, J. B. Kruskal, Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983.

Google Scholar

[11]

T. Siegenthaler, Correlation-immunity of nonlinear combining functions for cryptograpbic applications, IEEE Trans. Inform. Theory, vol. 30, pp. 776-780, Sept. 1984.

Digital Library

Google Scholar

[12]

T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE Trans. Comput. vol. 34, pp. 81-85, Jan. 1985.

Digital Library

Google Scholar

Cited By

View all

Varadharajalu ALiu WWong W(2011)Author name disambiguation for ranking and clustering pubmed data using netclusProceedings of the 24th international conference on Advances in Artificial Intelligence10.1007/978-3-642-25832-9_16(152-161)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25832-9_16
John DDeepthi PSathidevi P(2007)Linear feedback shift register based stream ciphersProceedings of the Fourth IASTED International Conference on Communication, Network and Information Security10.5555/1659141.1659147(22-27)Online publication date: 17-Sep-2007
https://dl.acm.org/doi/10.5555/1659141.1659147
Gong GJiang S(2005)The editing generator and its cryptanalysisInternational Journal of Wireless and Mobile Computing10.1504/IJWMC.2005.0080541:1(46-52)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1504/IJWMC.2005.008054
Show More Cited By

Recommendations

A Normalized Levenshtein Distance Metric

Although a number of normalized edit distances presented so far may offer good performance in some applications, none of them can be regarded as a genuine metric between strings because they do not satisfy the triangle inequality. Given two strings X ...
Cryptanalysis of WG-8 and WG-16 stream ciphers

In 2008, the WG family of stream ciphers was designed by Navaz and Gong to secure lightweight applications for RFIDs and smart cards. In 2012, a distinguishing attack was discovered against the WG-7 stream cipher by Orumiehchiha, Pieprzyk and Steinfeld. ...
Rebound attack on JH42
ASIACRYPT'11: Proceedings of the 17th international conference on The Theory and Application of Cryptology and Information Security

The hash function JH [20] is one of the five finalists of the NIST SHA-3 hash competition. It has been recently tweaked for the final by increasing its number of rounds from 35.5 to 42. The previously best known results on JH were semi-free-start near-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Cryptology Volume 3, Issue 3

January 1991

62 pages

ISSN:0933-2790

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 1991

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Varadharajalu ALiu WWong W(2011)Author name disambiguation for ranking and clustering pubmed data using netclusProceedings of the 24th international conference on Advances in Artificial Intelligence10.1007/978-3-642-25832-9_16(152-161)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25832-9_16
John DDeepthi PSathidevi P(2007)Linear feedback shift register based stream ciphersProceedings of the Fourth IASTED International Conference on Communication, Network and Information Security10.5555/1659141.1659147(22-27)Online publication date: 17-Sep-2007
https://dl.acm.org/doi/10.5555/1659141.1659147
Gong GJiang S(2005)The editing generator and its cryptanalysisInternational Journal of Wireless and Mobile Computing10.1504/IJWMC.2005.0080541:1(46-52)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1504/IJWMC.2005.008054
Caballero-Gil PFúster-Sabater A(2005)Improvement of the edit distance attack to clock-controlled LFSR-Based stream ciphersProceedings of the 10th international conference on Computer Aided Systems Theory10.1007/11556985_46(355-364)Online publication date: 7-Feb-2005
https://dl.acm.org/doi/10.1007/11556985_46
Kanso A(2003)Clock-controlled shrinking generator of feedback shift registersProceedings of the 8th Australasian conference on Information security and privacy10.5555/1760479.1760528(443-451)Online publication date: 9-Jul-2003
https://dl.acm.org/doi/10.5555/1760479.1760528
Clark ADawson EFuller JGolic JLee HMillan WMoon SSimpson L(2002)The LILI-II Keystream GeneratorProceedings of the 7th Australian Conference on Information Security and Privacy10.5555/646039.678334(25-39)Online publication date: 3-Jul-2002
https://dl.acm.org/doi/10.5555/646039.678334
Golić JMenicocci R(2002)Computation of Edit Probabilities and Edit Distances for the A5-Type Keystream GeneratorJournal of Complexity10.1006/jcom.2001.062418:1(356-374)Online publication date: 1-Mar-2002
https://dl.acm.org/doi/10.1006/jcom.2001.0624
Golic J(1997)Cryptanalysis of alleged A5 stream cipherProceedings of the 16th annual international conference on Theory and application of cryptographic techniques10.5555/1754542.1754566(239-255)Online publication date: 11-May-1997
https://dl.acm.org/doi/10.5555/1754542.1754566
Golic JPetrovic S(1996)Correlation Attacks on Clock-Controlled Shift Registers in Keystream GeneratorsIEEE Transactions on Computers10.1109/12.49410645:4(482-486)Online publication date: 1-Apr-1996
https://dl.acm.org/doi/10.1109/12.494106
Golic J(1996)Linear Models for Keystream GeneratorsIEEE Transactions on Computers10.1109/12.48148545:1(41-49)Online publication date: 1-Jan-1996
https://dl.acm.org/doi/10.1109/12.481485
Show More Cited By

Abstract

References

Cited By

Recommendations

A Normalized Levenshtein Distance Metric

Cryptanalysis of WG-8 and WG-16 stream ciphers

Rebound attack on JH42

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations