Some attacks on the Bitsearch generator
(2005) Fast Software Encryption 12th International Workshop, FSE 2005 In Fast Software Encryption / Lecture Notes in Computer Science 3557. p.215227 Abstract
 The bitsearch generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and selfshrinking generators. It has the advantage that it works at rate 1/3 using only one LFSR and some selection logic. We present various attacks on the BSG based on the fact that the output sequence can be uniquely defined by the differential of the input sequence. By knowing only a small part of the output sequence we can reconstruct the key with complexity O(L(3)2(0.5L)). This complexity can be significantly reduced in a data/time tradeoff manner to achieve a complexity of O(L(3)2(0.27)L) if we have O(2(0.27L)) of keystream. We also propose a distinguishing attack that can be very efficient if the feedback polynomial is not carefully... (More)
 The bitsearch generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and selfshrinking generators. It has the advantage that it works at rate 1/3 using only one LFSR and some selection logic. We present various attacks on the BSG based on the fact that the output sequence can be uniquely defined by the differential of the input sequence. By knowing only a small part of the output sequence we can reconstruct the key with complexity O(L(3)2(0.5L)). This complexity can be significantly reduced in a data/time tradeoff manner to achieve a complexity of O(L(3)2(0.27)L) if we have O(2(0.27L)) of keystream. We also propose a distinguishing attack that can be very efficient if the feedback polynomial is not carefully chosen. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/226843
 author
 Hell, Martin ^{LU} and Johansson, Thomas ^{LU}
 organization
 publishing date
 2005
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Fast Software Encryption / Lecture Notes in Computer Science
 volume
 3557
 pages
 215  227
 publisher
 Springer
 conference name
 Fast Software Encryption 12th International Workshop, FSE 2005
 external identifiers

 wos:000230869900014
 scopus:26444452700
 ISSN
 16113349
 03029743
 ISBN
 9783540265412
 DOI
 10.1007/11502760_14
 language
 English
 LU publication?
 yes
 id
 86081059bab646818d57e3ee1a5a681b (old id 226843)
 date added to LUP
 20080201 10:39:54
 date last changed
 20170305 03:27:01
@inproceedings{86081059bab646818d57e3ee1a5a681b, abstract = {The bitsearch generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and selfshrinking generators. It has the advantage that it works at rate 1/3 using only one LFSR and some selection logic. We present various attacks on the BSG based on the fact that the output sequence can be uniquely defined by the differential of the input sequence. By knowing only a small part of the output sequence we can reconstruct the key with complexity O(L(3)2(0.5L)). This complexity can be significantly reduced in a data/time tradeoff manner to achieve a complexity of O(L(3)2(0.27)L) if we have O(2(0.27L)) of keystream. We also propose a distinguishing attack that can be very efficient if the feedback polynomial is not carefully chosen.}, author = {Hell, Martin and Johansson, Thomas}, booktitle = {Fast Software Encryption / Lecture Notes in Computer Science}, isbn = {9783540265412}, issn = {16113349}, language = {eng}, pages = {215227}, publisher = {Springer}, title = {Some attacks on the Bitsearch generator}, url = {http://dx.doi.org/10.1007/11502760_14}, volume = {3557}, year = {2005}, }