Affordable Access

Publisher Website

Strategic attack on the shrinking generator

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
409
Issue
3
Identifiers
DOI: 10.1016/j.tcs.2008.09.030
Keywords
  • Stream Cipher
  • Shrinking Generator
  • Interleaved Sequence
  • Cryptanalysis

Abstract

Abstract The shrinking generator is a simple keystream generator with applications in stream ciphers, which is still considered as a secure generator. This work shows that, in order to cryptanalyze it, fewer intercepted bits than indicated by the linear complexity are necessary. Indeed, whereas the linear complexity of shrunken sequences is between A ⋅ 2 ( S − 2 ) and A ⋅ 2 ( S − 1 ) , we claim that the initial states of both component registers are easily computed with fewer than A ⋅ S shrunken bits located at particular positions. Such a result is proven thanks to the definition of shrunken sequences as interleaved sequences. Consequently, it is conjectured that this statement can be extended to all interleaved sequences. Furthermore, this paper confirms that certain bits of the interleaved sequences have a greater strategic importance than others, which must be considered as a proof of weakness of interleaved generators.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Shrinking generators and statistical leakage

on Computers & Mathematics with A... Jan 01, 1996

Modified self-shrinking generator

on Computers & Electrical Enginee... Jan 01, 2010
More articles like this..