Advanced

Improved Distinguishers on Stream Ciphers with Certain Weak Feedback Polynomials

Hell, Martin LU ; Johansson, Thomas LU ; Brynielsson, Lennart and Englund, Håkan (2012) In IEEE Transactions on Information Theory 58(9). p.6183-6193
Abstract
It is well known that fast correlation attacks can be very efficient if the feedback polynomial is of low weight. These feedback polynomials can be considered weak in the context of stream ciphers. This paper generalizes the class of weak feedback polynomials into polynomials were taps are located in several groups, possibly far apart. Low weight feedback polynomials are thus a special case of this class. For the general class it is shown that attacks can sometimes be very efficient even though the polynomials are of large weight. The main idea is to consider vectors of noise variables. It is shown how the complexity of a distinguishing attack can be efficiently computed and that the complexity is closely related to the minimum row... (More)
It is well known that fast correlation attacks can be very efficient if the feedback polynomial is of low weight. These feedback polynomials can be considered weak in the context of stream ciphers. This paper generalizes the class of weak feedback polynomials into polynomials were taps are located in several groups, possibly far apart. Low weight feedback polynomials are thus a special case of this class. For the general class it is shown that attacks can sometimes be very efficient even though the polynomials are of large weight. The main idea is to consider vectors of noise variables. It is shown how the complexity of a distinguishing attack can be efficiently computed and that the complexity is closely related to the minimum row distance of a generator matrix for a convolutional code. Moreover, theoretical results on the size of the vectors are given. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
correlation attack, LFSR, stream cipher, weak feedback polynomial
in
IEEE Transactions on Information Theory
volume
58
issue
9
pages
6183 - 6193
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • WOS:000307892800039
  • Scopus:84865408281
ISSN
0018-9448
DOI
10.1109/TIT.2012.2202212
language
English
LU publication?
yes
id
17b4de15-4b8d-496e-a4ac-9bf937a0c708 (old id 2743568)
date added to LUP
2012-06-08 14:46:28
date last changed
2016-10-13 04:31:11
@misc{17b4de15-4b8d-496e-a4ac-9bf937a0c708,
  abstract     = {It is well known that fast correlation attacks can be very efficient if the feedback polynomial is of low weight. These feedback polynomials can be considered weak in the context of stream ciphers. This paper generalizes the class of weak feedback polynomials into polynomials were taps are located in several groups, possibly far apart. Low weight feedback polynomials are thus a special case of this class. For the general class it is shown that attacks can sometimes be very efficient even though the polynomials are of large weight. The main idea is to consider vectors of noise variables. It is shown how the complexity of a distinguishing attack can be efficiently computed and that the complexity is closely related to the minimum row distance of a generator matrix for a convolutional code. Moreover, theoretical results on the size of the vectors are given.},
  author       = {Hell, Martin and Johansson, Thomas and Brynielsson, Lennart and Englund, Håkan},
  issn         = {0018-9448},
  keyword      = {correlation attack,LFSR,stream cipher,weak feedback polynomial},
  language     = {eng},
  number       = {9},
  pages        = {6183--6193},
  publisher    = {ARRAY(0x82ec1b0)},
  series       = {IEEE Transactions on Information Theory},
  title        = {Improved Distinguishers on Stream Ciphers with Certain Weak Feedback Polynomials},
  url          = {http://dx.doi.org/10.1109/TIT.2012.2202212},
  volume       = {58},
  year         = {2012},
}