Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
New Guess-and-Determine Attack on the Self-Shrinking Generator
verfasst von : Bin Zhang, Dengguo Feng
Erschienen in: Advances in Cryptology – ASIACRYPT 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a new type of guess-and-determine attack on the self-shrinking generator (SSG). The inherent flexibility of the new attack enables us to deal with different attack conditions and requirements smoothly. For the SSG with a length
L
LFSR of arbitrary form, our attack can reliably restore the initial state with time complexity
O
(2
0.556 L
), memory complexity
O
(
L
2
) from
O
(2
0.161L
)-bit keystream for
L
≥100 and time complexity
O
(2
0.571 L
), memory complexity
O
(
L
2
) from
O
(2
0.194 L
)-bit keystream for
L
< 100. Therefore, our attack is better than all the previously known attacks on the SSG and especially, it compares favorably with the time/memory/data tradeoff attack which typically has time complexity
O
(2
0.5 L
), memory complexity
O
(2
0.5 L
) and data complexity
O
(2
0.25 L
)-bit keystream after a pre-computation phase of complexity
O
(2
0.75 L
). It is well-known that one of the open research problems in stream ciphers specified by the European STORK (Strategic Roadmap for Crypto) project is to find an attack on the self-shrinking generator with complexity lower than that of a generic time/memory/data tradeoff attack. Our result is the best answer to this problem known so far.