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

Institutionen för elektro- och informationsteknik

Institute for Information Transmission Problems Russian Academy of Sciences

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

Sammanfattning

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.

Originalspråk	engelska
Titel på värdpublikation	Advances in Cryptology—EUROCRYPT 1991
Undertitel på värdpublikation	Workshop on the Theory and Application of Cryptographic Techniques, Proceedings
Redaktörer	Donald W. Davies
Förlag	Springer
Sidor	176-185
Antal sidor	10
ISBN (elektroniskt)	9783540464167
ISBN (tryckt)	9783540546207
DOI	https://doi.org/10.1007/3-540-46416-6_16
Status	Published - 1991
Evenemang	Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991 - Brighton, Storbritannien Varaktighet: 1991 apr. 8 → 1991 apr. 11

Publikationsserier

Namn	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volym	547 LNCS
ISSN (tryckt)	0302-9743
ISSN (elektroniskt)	1611-3349

Konferens

Konferens	Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991
Land/Territorium	Storbritannien
Ort	Brighton
Period	1991/04/08 → 1991/04/11

Bibliografisk information

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.

Ämnesklassifikation (UKÄ)

Datavetenskap (datalogi)
Reglerteknik

Tillgång till dokument

10.1007/3-540-46416-6_16

Citera det här

Chepyzhov, V., & Smeets, B. (1991). On a fast correlation attack on certain streaxn ciphers. I D. W. Davies (Red.), Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings (s. 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. redaktör / Donald W. Davies. Springer, 1991. s. 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. i DW Davies (red.), 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, s. 176-185, Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991, Brighton, Storbritannien, 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. red. / Donald W. Davies. Springer, 1991. s. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 547 LNCS).

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i 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. I Davies DW, redaktör, Advances in Cryptology—EUROCRYPT 1991: Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. Springer. 1991. s. 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

Sammanfattning

Publikationsserier

Konferens

Bibliografisk information

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Citera det här