Advanced

Some attacks on the Bit-search generator

Hell, Martin LU and Johansson, Thomas LU (2005) Fast Software Encryption 12th International Workshop, FSE 2005 In Fast Software Encryption / Lecture Notes in Computer Science 3557. p.215-227
Abstract
The bit-search generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and self-shrinking 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 bit-search generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and self-shrinking 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:
author
organization
publishing date
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
1611-3349
0302-9743
ISBN
978-3-540-26541-2
DOI
10.1007/11502760_14
language
English
LU publication?
yes
id
86081059-bab6-4681-8d57-e3ee1a5a681b (old id 226843)
date added to LUP
2008-02-01 10:39:54
date last changed
2017-03-05 03:27:01
@inproceedings{86081059-bab6-4681-8d57-e3ee1a5a681b,
  abstract     = {The bit-search generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and self-shrinking 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         = {978-3-540-26541-2},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {215--227},
  publisher    = {Springer},
  title        = {Some attacks on the Bit-search generator},
  url          = {http://dx.doi.org/10.1007/11502760_14},
  volume       = {3557},
  year         = {2005},
}