Improved Cryptanalysis of the Self-Shrinking Generator

Erik Zenner, Matthias Krause, Stefan Lucks

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

Abstract

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
Pages21-35
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

Conference

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

Cite this