Advanced

Two new attacks on the self-shrinking generator

Hell, Martin LU and Johansson, Thomas LU (2006) In IEEE Transactions on Information Theory 52(8). p.3837-3843
Abstract
The self-shrinking generator was introduced in 1994. It is based on the idea behind the shrinking generator and despite its simplicity it has remained remarkably resistant to efficient attacks. Several known plaintext attacks have been proposed on the generator, some operating on a short keystream and others requiting a longer sequence to succeed. In this paper, two new attacks on the self-shrinking generator are proposed. The first attack, using a short known keystream, has the same complexity as the BDD-based attack, which is the best previously known attack. However, while the BDD-based attack requires a huge amount of memory, the proposed algorithm uses almost no memory, leaving it as the preferred alternative. The second attack... (More)
The self-shrinking generator was introduced in 1994. It is based on the idea behind the shrinking generator and despite its simplicity it has remained remarkably resistant to efficient attacks. Several known plaintext attacks have been proposed on the generator, some operating on a short keystream and others requiting a longer sequence to succeed. In this paper, two new attacks on the self-shrinking generator are proposed. The first attack, using a short known keystream, has the same complexity as the BDD-based attack, which is the best previously known attack. However, while the BDD-based attack requires a huge amount of memory, the proposed algorithm uses almost no memory, leaving it as the preferred alternative. The second attack operates on a longer known keystream, exponential in the length of the LFSR. The attack considers one or several segments of keystream bits and guesses that these bits stem from LFSR segments of some size. It is shown that this attack achieves better complexity than any previously known attack. (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
stream ciphers, self-shrinking generator, (LFSRs), linear feedback shift registers, cryptanalysis, key recovery attack
in
IEEE Transactions on Information Theory
volume
52
issue
8
pages
3837 - 3843
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000239408700041
  • scopus:33746654569
ISSN
0018-9448
DOI
10.1109/TIT.2006.878233
language
English
LU publication?
yes
id
11da22db-9f38-476a-bf88-3f1b270da65c (old id 399140)
date added to LUP
2007-10-03 20:08:47
date last changed
2019-03-27 03:04:57
@article{11da22db-9f38-476a-bf88-3f1b270da65c,
  abstract     = {The self-shrinking generator was introduced in 1994. It is based on the idea behind the shrinking generator and despite its simplicity it has remained remarkably resistant to efficient attacks. Several known plaintext attacks have been proposed on the generator, some operating on a short keystream and others requiting a longer sequence to succeed. In this paper, two new attacks on the self-shrinking generator are proposed. The first attack, using a short known keystream, has the same complexity as the BDD-based attack, which is the best previously known attack. However, while the BDD-based attack requires a huge amount of memory, the proposed algorithm uses almost no memory, leaving it as the preferred alternative. The second attack operates on a longer known keystream, exponential in the length of the LFSR. The attack considers one or several segments of keystream bits and guesses that these bits stem from LFSR segments of some size. It is shown that this attack achieves better complexity than any previously known attack.},
  author       = {Hell, Martin and Johansson, Thomas},
  issn         = {0018-9448},
  keyword      = {stream ciphers,self-shrinking generator,(LFSRs),linear feedback shift registers,cryptanalysis,key recovery attack},
  language     = {eng},
  number       = {8},
  pages        = {3837--3843},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Information Theory},
  title        = {Two new attacks on the self-shrinking generator},
  url          = {http://dx.doi.org/10.1109/TIT.2006.878233},
  volume       = {52},
  year         = {2006},
}