Self-shrinking Generator - Cryptanalysis

Cryptanalysis

In their paper, Meier and Steffelbach prove that a LFSR based self-shrinking generator with a connection polynomial of length L results in an output sequence period of at least 2L/2, and a linear complexity of at least 2L/2-1.

Furthermore, they show that any self-shrinking generator can be represented as a shrinking-generator. The inverse is also true: Any shrinking generator can be implemented as a self-shrinking generator, although the resultant generator may not be of maximal length.

An attack presented by the authors requires about 20.7L steps, assuming a known connection polynomial.

A more advanced attack, discovered by Mihaljević, is able to break a register a hundred bits in length in around 257 steps, using an output sequence of only 4.9 x 108 bits.

Read more about this topic:  Self-shrinking Generator