Correlation attacks using a new class of weak feedback polynomials
(2004) 11th International Workshop, FSE 2004 3017. p.127-142- Abstract
- In 1985 Siegenthaler introduced the concept of correlation attacks on LFSR based stream ciphers. A few years later Meier and Staffelbach demonstrated a special technique, usually referred to as fast correlation attacks, that is very effective if the feedback polynomial has a special form, namely, if its weight is very low. Due to this seminal result, it is a well known fact that one avoids low weight feedback polynomials in the design of LFSR based stream ciphers. This paper identifies a new class of such weak feedback polynomials, polynomials of the form f(x) = g(1) (x) + g(2) (x)x(M1) + (...) + g(t)(x)x(Mt-1), where g(1), g(2), (...), g(t) are all polynomials of low degree. For such feedback polynomials, we identify an efficient... (More)
- In 1985 Siegenthaler introduced the concept of correlation attacks on LFSR based stream ciphers. A few years later Meier and Staffelbach demonstrated a special technique, usually referred to as fast correlation attacks, that is very effective if the feedback polynomial has a special form, namely, if its weight is very low. Due to this seminal result, it is a well known fact that one avoids low weight feedback polynomials in the design of LFSR based stream ciphers. This paper identifies a new class of such weak feedback polynomials, polynomials of the form f(x) = g(1) (x) + g(2) (x)x(M1) + (...) + g(t)(x)x(Mt-1), where g(1), g(2), (...), g(t) are all polynomials of low degree. For such feedback polynomials, we identify an efficient correlation attack in the form of a distinguishing attack. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/272861
- author
- Englund, Håkan LU ; Hell, Martin LU and Johansson, Thomas LU
- organization
- publishing date
- 2004
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Fast Software Encryption. Revised Papers / Lecture Notes in Computer Science
- volume
- 3017
- pages
- 127 - 142
- publisher
- Springer
- conference name
- 11th International Workshop, FSE 2004
- conference location
- Delhi, India
- conference dates
- 2004-02-05 - 2004-02-07
- external identifiers
-
- wos:000222561800009
- scopus:35048880661
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 978-3-540-22171-5
- DOI
- 10.1007/978-3-540-25937-4_9
- language
- English
- LU publication?
- yes
- id
- b3cd3ac4-c764-43b8-bcc8-dab5f24d2165 (old id 272861)
- date added to LUP
- 2016-04-01 12:17:36
- date last changed
- 2024-01-08 15:23:46
@inproceedings{b3cd3ac4-c764-43b8-bcc8-dab5f24d2165, abstract = {{In 1985 Siegenthaler introduced the concept of correlation attacks on LFSR based stream ciphers. A few years later Meier and Staffelbach demonstrated a special technique, usually referred to as fast correlation attacks, that is very effective if the feedback polynomial has a special form, namely, if its weight is very low. Due to this seminal result, it is a well known fact that one avoids low weight feedback polynomials in the design of LFSR based stream ciphers. This paper identifies a new class of such weak feedback polynomials, polynomials of the form f(x) = g(1) (x) + g(2) (x)x(M1) + (...) + g(t)(x)x(Mt-1), where g(1), g(2), (...), g(t) are all polynomials of low degree. For such feedback polynomials, we identify an efficient correlation attack in the form of a distinguishing attack.}}, author = {{Englund, Håkan and Hell, Martin and Johansson, Thomas}}, booktitle = {{Fast Software Encryption. Revised Papers / Lecture Notes in Computer Science}}, isbn = {{978-3-540-22171-5}}, issn = {{0302-9743}}, language = {{eng}}, pages = {{127--142}}, publisher = {{Springer}}, title = {{Correlation attacks using a new class of weak feedback polynomials}}, url = {{http://dx.doi.org/10.1007/978-3-540-25937-4_9}}, doi = {{10.1007/978-3-540-25937-4_9}}, volume = {{3017}}, year = {{2004}}, }