Self-shrinking generator
A self-shrinking generator is a pseudorandom generator, which is based on the shrinking generator concept. Variants of the self-shrinking generator based on a linear feedback shift register (LFSR) are studied for use in cryptography.
Algorithm
In difference to the shrinking generator, which uses a 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.
Example
This example will use the connection polynomial x8 + x4 + x3 + x2 + 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.
Cryptanalysis
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 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 [2], 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.
References
- [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.