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