The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Two new attacks on the self-shrinking generator

Author

Summary, in English

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.

Publishing year

2006

Language

English

Pages

3837-3843

Publication/Series

IEEE Transactions on Information Theory

Volume

52

Issue

8

Document type

Journal article

Publisher

IEEE - Institute of Electrical and Electronics Engineers Inc.

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • stream ciphers
  • self-shrinking generator
  • (LFSRs)
  • linear feedback shift registers
  • cryptanalysis
  • key recovery attack

Status

Published

ISBN/ISSN/Other

  • ISSN: 0018-9448