Using Coding Techniques to Analyze Weak Feedback Polynomials
(2010) IEEE International Symposium on Information Theory (ISIT), 2010 In Proceedings p.25232527 Abstract
 We consider a class of weak feedback polynomials for LFSRs in the nonlinear combiner. When feedback taps are located in small groups, a distinguishing attack can sometimes be improved considerably, compared to the common attack that uses low weight multiples. This class of weak polynomials was introduced in 2004 and the main property of the attack is that the noise variables are represented as vectors. We analyze the complexity of the attack using coding theory. We show that the groups of polynomials can be seen as generator polynomials of a convolutional code. Then, the problem of finding the attack complexity is equivalent to finding the minimum row distance of the corresponding generator matrix. A modified version of BEAST is used to... (More)
 We consider a class of weak feedback polynomials for LFSRs in the nonlinear combiner. When feedback taps are located in small groups, a distinguishing attack can sometimes be improved considerably, compared to the common attack that uses low weight multiples. This class of weak polynomials was introduced in 2004 and the main property of the attack is that the noise variables are represented as vectors. We analyze the complexity of the attack using coding theory. We show that the groups of polynomials can be seen as generator polynomials of a convolutional code. Then, the problem of finding the attack complexity is equivalent to finding the minimum row distance of the corresponding generator matrix. A modified version of BEAST is used to search all encoders of memory up to 13. Moreover, we give a tight upper bound on the required size of the vectors in the attack. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1614409
 author
 Hell, Martin ^{LU}
 organization
 publishing date
 2010
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Proceedings
 pages
 2523  2527
 conference name
 IEEE International Symposium on Information Theory (ISIT), 2010
 external identifiers

 WOS:000287512700507
 Scopus:77955697530
 language
 English
 LU publication?
 yes
 id
 a3187f5e3ab9480b9b455e06d613d07d (old id 1614409)
 date added to LUP
 20100611 07:50:02
 date last changed
 20161013 04:57:04
@misc{a3187f5e3ab9480b9b455e06d613d07d, abstract = {We consider a class of weak feedback polynomials for LFSRs in the nonlinear combiner. When feedback taps are located in small groups, a distinguishing attack can sometimes be improved considerably, compared to the common attack that uses low weight multiples. This class of weak polynomials was introduced in 2004 and the main property of the attack is that the noise variables are represented as vectors. We analyze the complexity of the attack using coding theory. We show that the groups of polynomials can be seen as generator polynomials of a convolutional code. Then, the problem of finding the attack complexity is equivalent to finding the minimum row distance of the corresponding generator matrix. A modified version of BEAST is used to search all encoders of memory up to 13. Moreover, we give a tight upper bound on the required size of the vectors in the attack.}, author = {Hell, Martin}, language = {eng}, pages = {25232527}, series = {Proceedings}, title = {Using Coding Techniques to Analyze Weak Feedback Polynomials}, year = {2010}, }