Advanced

Correlation attacks using a new class of weak feedback polynomials

Englund, Håkan LU ; Hell, Martin LU and Johansson, Thomas LU (2004) 11th International Workshop, FSE 2004 In Fast Software Encryption. Revised Papers / Lecture Notes in Computer Science 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Fast Software Encryption. Revised Papers / Lecture Notes in Computer Science
volume
3017
pages
127 - 142
publisher
Springer
conference name
11th International Workshop, FSE 2004
external identifiers
  • wos:000222561800009
  • scopus:35048880661
ISSN
1611-3349
0302-9743
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
2007-10-22 08:59:36
date last changed
2017-07-30 03:47:12
@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         = {1611-3349},
  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},
  volume       = {3017},
  year         = {2004},
}