A new statistical distinguisher for the shrinking generator

Jovan Dj.  Golic; Renato Menicocci

Paper 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 and LFSR, where LFSR is clock-controlled according to regularly clocked LFSR. The keystream sequence is thus a decimated LFSR 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 sequence that satisfy the LFSR recurrence or any linear recurrence derived from low-weight multiples of the LFSR characteristic polynomial. The keystream sequence length and the computation time required for a reliable statistical distinction are analyzed both theoretically and experimentally.

Metadata

Available format(s): PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: cryptanalysis stream ciphers
Contact author(s): golic @ inwind it
History: 2003-03-03: received
Short URL: https://ia.cr/2003/041
License: CC BY

BibTeX

@misc{cryptoeprint:2003/041,
      author = {Jovan Dj.  Golic and Renato Menicocci},
      title = {A new statistical distinguisher for the shrinking generator},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/041},
      year = {2003},
      url = {https://eprint.iacr.org/2003/041}
}