Improved Cryptanalysis of the Self-Shrinking Generator

Erik Zenner, Matthias Krause, Stefan Lucks

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


We propose a new attack on the self-shrinking generator [8]. The attack is based on a backtracking algorithm and will reconstruct the key from a short sequence of known keystream bits. We give both mathematical and empirical evidence for the effectiveness of this attack. The algorithm takes at most O(2^0.694L) steps, where L is the key length. Thus, our attack is more efficient than previously known key reconstruction algorithms against the self-shrinking generator that operate on short keystream sequences.
Original languageEnglish
Title of host publicationProceedings ACISP 2001
EditorsVijay Varadharajan, Yi Mu
Place of PublicationLondon, UK
PublisherSpringer Verlag
Publication date2001
ISBN (Print)3-540-42300-1
Publication statusPublished - 2001
Externally publishedYes
EventAustralasian Conference on Information Security and Privacy - Sydney, AU
Duration: 1 Jan 2001 → …
Conference number: 6


ConferenceAustralasian Conference on Information Security and Privacy
CitySydney, AU
Period01/01/2001 → …
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Improved Cryptanalysis of the Self-Shrinking Generator'. Together they form a unique fingerprint.

Cite this