Cryptology ePrint Archive: Report 2003/041
A new statistical distinguisher for the shrinking generator
Jovan Dj. Golic and Renato Menicocci
Abstract: The shrinking generator is a well-known keystream generator composed
of two linear feedback shift registers, LFSR$_1$ and LFSR$_2$, where
LFSR$_1$ is clock-controlled according to regularly clocked LFSR$_2$.
The keystream sequence is thus a decimated LFSR$_1$ sequence.
Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the
keystream sequence from a purely random sequence.
Previously proposed statistical distinguishers for the shrinking generator
are based on detecting binary linear relations in the keystream sequence that hold
with a probability sufficiently different from one half.
In this paper a novel approach which significantly reduces the required computation time is introduced.
It is based on a probabilistic reconstruction of the bits in the regularly
clocked LFSR$_1$ sequence that satisfy the LFSR$_1$ recurrence
or any linear recurrence derived from
low-weight multiples of the LFSR$_1$ characteristic polynomial.
The keystream sequence length and the computation time required for a reliable statistical distinction
are analyzed both theoretically and experimentally.
Category / Keywords: secret-key cryptography / cryptanalysis, stream ciphers
Date: received 3 Mar 2003
Contact author: golic at inwind it
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Version: 20030303:215141 (All versions of this report)
Short URL: ia.cr/2003/041
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]