On a fast correlation attack on certain streaxn ciphers

Vladimir Chepyzhov; Ben Smeets

doi:10.1007/3-540-46416-6_16

On a fast correlation attack on certain streaxn ciphers

Vladimir Chepyzhov, Ben Smeets

Department of Electrical and Information Technology

Institute for Information Transmission Problems Russian Academy of Sciences

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

Abstract

In this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. Our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. Our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. Our procedure works for shift register with arbitrary feedback polynomial.

Original language	English
Title of host publication	Advances in Cryptology—EUROCRYPT 1991
Subtitle of host publication	Workshop on the Theory and Application of Cryptographic Techniques, Proceedings
Editors	Donald W. Davies
Publisher	Springer
Pages	176-185
Number of pages	10
ISBN (Electronic)	9783540464167
ISBN (Print)	9783540546207
DOIs	https://doi.org/10.1007/3-540-46416-6_16
Publication status	Published - 1991
Event	Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991 - Brighton, United Kingdom Duration: 1991 Apr 8 → 1991 Apr 11

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	547 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991
Country/Territory	United Kingdom
City	Brighton
Period	1991/04/08 → 1991/04/11

Bibliographical note

Funding Information:
The first author would like to thank the USSR Academy of Sciences, the Royal Swedish Academy of Sciences, and the Department of Information Theory in Lund for their support and making this work possible.

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.

Subject classification (UKÄ)

Computer Science
Control Engineering

Access to Document

10.1007/3-540-46416-6_16

Cite this

Chepyzhov, V., & Smeets, B. (1991). On a fast correlation attack on certain streaxn ciphers. In D. W. Davies (Ed.), Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings (pp. 176-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 547 LNCS). Springer. https://doi.org/10.1007/3-540-46416-6_16

Chepyzhov, Vladimir ; Smeets, Ben. / On a fast correlation attack on certain streaxn ciphers. Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. editor / Donald W. Davies. Springer, 1991. pp. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7a59a362b50d4728b19fbfe046f9b9ac,

title = "On a fast correlation attack on certain streaxn ciphers",

abstract = "In this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. Our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. Our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. Our procedure works for shift register with arbitrary feedback polynomial.",

author = "Vladimir Chepyzhov and Ben Smeets",

note = "Funding Information: The first author would like to thank the USSR Academy of Sciences, the Royal Swedish Academy of Sciences, and the Department of Information Theory in Lund for their support and making this work possible. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991 ; Conference date: 08-04-1991 Through 11-04-1991",

year = "1991",

doi = "10.1007/3-540-46416-6_16",

language = "English",

isbn = "9783540546207",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "176--185",

editor = "Davies, {Donald W.}",

booktitle = "Advances in Cryptology—EUROCRYPT 1991",

address = "Germany",

}

Chepyzhov, V & Smeets, B 1991, On a fast correlation attack on certain streaxn ciphers. in DW Davies (ed.), Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 547 LNCS, Springer, pp. 176-185, Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991, Brighton, United Kingdom, 1991/04/08. https://doi.org/10.1007/3-540-46416-6_16

On a fast correlation attack on certain streaxn ciphers. / Chepyzhov, Vladimir; Smeets, Ben.

Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. ed. / Donald W. Davies. Springer, 1991. p. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 547 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

T1 - On a fast correlation attack on certain streaxn ciphers

AU - Chepyzhov, Vladimir

AU - Smeets, Ben

N1 - Funding Information: The first author would like to thank the USSR Academy of Sciences, the Royal Swedish Academy of Sciences, and the Department of Information Theory in Lund for their support and making this work possible. Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - In this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. Our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. Our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. Our procedure works for shift register with arbitrary feedback polynomial.

AB - In this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. Our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. Our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. Our procedure works for shift register with arbitrary feedback polynomial.

U2 - 10.1007/3-540-46416-6_16

DO - 10.1007/3-540-46416-6_16

M3 - Paper in conference proceeding

AN - SCOPUS:85030473541

SN - 9783540546207

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 176

EP - 185

BT - Advances in Cryptology—EUROCRYPT 1991

A2 - Davies, Donald W.

PB - Springer

T2 - Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991

Y2 - 8 April 1991 through 11 April 1991

ER -

Chepyzhov V, Smeets B. On a fast correlation attack on certain streaxn ciphers. In Davies DW, editor, Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. Springer. 1991. p. 176-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46416-6_16

On a fast correlation attack on certain streaxn ciphers

Abstract

Publication series

Conference

Bibliographical note

Subject classification (UKÄ)

Access to Document

Fingerprint

Cite this