A **self-shrinking generator** is a pseudorandom generator, which is based on the shrinking generator concept. Various variants of the self-shrinking generator based on a linear feedback shift register (LFSR) are studied for use in cryptography.

## AlgorithmEdit

In difference to the shrinking generator, which uses as second feedback shift register to control the output of the first, the self-shrinking generator uses alternating output bits of a single register to control its final output. The procedure for clocking this kind of generator is as follows:

- Clock two bits from the LFSR.
- If the pair is 10 output a zero.
- If the pair is 11 output a one.
- Otherwise, output nothing.
- Return to step one.

## ExampleEdit

This example will use the connection polynomial *x ^{8} + x^{4} + x^{3} + x^{2} + 1*,
and an initial register fill of

*1 0 1 1 0 1 1 0*.

Below table lists, for each iteration of the LFSR, its intermediate output before self-shrinking, as well as the final generator output. The tap positions defined by the connection polynomial are marked with blue headings. The state of the zeroth iteration represents the initial input.

Iteration # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Intermediate output | Generator output |
---|---|---|---|---|---|---|---|---|---|---|

0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N/A | N/A |

1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N/A |

2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |

3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |

4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |

At the end of four iterations, the following sequence of intermediate bits is produced: *0110*.

The first pair of bits, *01*, is discarded since it does not match either *10* or *11*.
The second pair of bits, *10*, matches the second step of the algorithm so a zero is output.

More bits are created by continuing to clock the LFSR and shrinking its output as described above.

## CryptanalysisEdit

In their paper [1], 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 2^{L/2}, and a linear complexity of at least 2^{L/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 2^{0.7L} steps, assuming a known connection polynomial.

A more advanced attack [2], discovered by Mihaljević, is able to break a register a hundred bits in length in around 2^{57} steps, using an output sequence of only 4.9 x 10^{8} bits.

## ReferencesEdit

- [1] "The self-shrinking generator", Advances in Cryptology-Eurocrypt 1994 (LNCS 950), 205-214, 1995.
- [2] "An security examination of the self-shrinking generator", Circencester, UK, December 1995.