Improved Distinguishers on Stream Ciphers with Certain Weak Feedback Polynomials
(2012) In IEEE Transactions on Information Theory 58(9). p.61836193 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:
http://lup.lub.lu.se/record/2743568
 author
 Hell, Martin ^{LU} ; Johansson, Thomas ^{LU} ; Brynielsson, Lennart and Englund, Håkan
 organization
 publishing date
 2012
 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
 IEEEInstitute of Electrical and Electronics Engineers Inc.
 external identifiers

 wos:000307892800039
 scopus:84865408281
 ISSN
 00189448
 DOI
 10.1109/TIT.2012.2202212
 language
 English
 LU publication?
 yes
 id
 17b4de154b8d496ea4ac9bf937a0c708 (old id 2743568)
 date added to LUP
 20120608 14:46:28
 date last changed
 20180107 10:21:11
@article{17b4de154b8d496ea4ac9bf937a0c708, 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 = {00189448}, keyword = {correlation attack,LFSR,stream cipher,weak feedback polynomial}, language = {eng}, number = {9}, pages = {61836193}, publisher = {IEEEInstitute of Electrical and Electronics Engineers Inc.}, 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}, }