Self-shrinking generator

A self-shrinking generator is a pseudorandom number generator and a variant of the shrinking generator concept. It is a generator used in cryptography and has reasonable security properties when used in conjunction with a Linear feedback shift register (LFSR).

Algorithm

Instead of using two distinct LFSR with one register driving the second register outputs, the self-shrinking generator operates with a single register. 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: x^8 + x^4 + x^3 + x^2 + 0

The key will be: 1 0 1 1 0 1 1 0.

Below is the output of the LFSR before it is self-shrunk. The tap positions are marked with the blue headings. The key is loaded in to the zeroth iteration, so it has no output bit. The subsequent iteration numbers each outputa single bit.

See the LFSR article for details on how these rows are generated.

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

The first pair of bits, 01, is discarded since it doesn't match either 10 or 11. The second pair of bits, 10, matches the second step of the algorithm so we output a zero.

To generate more bits, we simply continue to clock the LFSR and shrinking it as we have done above.

Cryptanalysis

Meier and Staffelbach [1] showed 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.

They went on to show that if the period is at least 2^L/2 and also that the linear complexity of the construction is 2^L/2-1.They presented an attack on the construction that requires 2^0.7L steps.

A more advanced attack [2] , discovered by Mihaljević, is able to break a register a hundred bits in length in around 2⁵⁷ steps, using an output sequence of only 4.9 x 10⁸ 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.

Further reading

* [http://www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography]