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:
https://lup.lub.lu.se/record/399140
- author
- Hell, Martin
LU
and Johansson, Thomas
LU
- organization
- publishing date
- 2006
- 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
- 2016-04-01 17:01:40
- date last changed
- 2023-09-05 05:49:21
@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}},
keywords = {{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}},
doi = {{10.1109/TIT.2006.878233}},
volume = {{52}},
year = {{2006}},
}