Improved Cryptanalysis of the Self-Shrinking Generator

Erik  Zenner; Matthias Krause; Stefan Lucks

Improved Cryptanalysis of the Self-Shrinking Generator

Erik Zenner, Matthias Krause, Stefan Lucks

University of Mannheim

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Proceedings ACISP 2001
Editors	Vijay Varadharajan, Yi Mu
Place of Publication	London, UK
Publisher	Springer Verlag
Publication date	2001
Pages	21-35
ISBN (Print)	3-540-42300-1
Publication status	Published - 2001
Externally published	Yes
Event	Australasian Conference on Information Security and Privacy - Sydney, AU Duration: 1 Jan 2001 → … Conference number: 6

Conference

Conference	Australasian Conference on Information Security and Privacy
Number	6
City	Sydney, AU
Period	01/01/2001 → …

Series	Lecture Notes in Computer Science
Number	2119

OpenUrl availability

Full text

Cite this

@inproceedings{06092f449715401b9eadfd409323f926,

title = "Improved Cryptanalysis of the Self-Shrinking Generator",

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.",

author = "Erik Zenner and Matthias Krause and Stefan Lucks",

year = "2001",

language = "English",

isbn = "3-540-42300-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

number = "2119",

pages = "21--35",

editor = "Vijay Varadharajan and Yi Mu",

booktitle = "Proceedings ACISP 2001",

address = "Germany",

note = "Australasian Conference on Information Security and Privacy, ACISP ; Conference date: 01-01-2001",

}

Improved Cryptanalysis of the Self-Shrinking Generator. / Zenner, Erik ; Krause, Matthias; Lucks, Stefan.

Proceedings ACISP 2001. ed. / Vijay Varadharajan; Yi Mu. London, UK : Springer Verlag, 2001. p. 21-35 (Lecture Notes in Computer Science; No. 2119).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Improved Cryptanalysis of the Self-Shrinking Generator

AU - Zenner, Erik

AU - Krause, Matthias

AU - Lucks, Stefan

N1 - Conference code: 6

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

M3 - Article in proceedings

SN - 3-540-42300-1

T3 - Lecture Notes in Computer Science

SP - 21

EP - 35

BT - Proceedings ACISP 2001

A2 - Varadharajan, Vijay

A2 - Mu, Yi

PB - Springer Verlag

CY - London, UK

T2 - Australasian Conference on Information Security and Privacy

Y2 - 1 January 2001

ER -

Improved Cryptanalysis of the Self-Shrinking Generator

Abstract

Conference

OpenUrl availability

Fingerprint

Cite this