A self-shrinking generator is a

pseudorandom generator In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class ...

that is based on the

shrinking generator In cryptography, the shrinking generator is a form of pseudorandom number generator intended to be used in a stream cipher. It was published in Crypto 1993 by Don Coppersmith, Hugo Krawczyk, and Yishay Mansour. The shrinking generator uses two lin ...

concept. Variants of the self-shrinking generator based on a

linear-feedback shift register In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a sh ...

(LFSR) are studied for use in

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

Algorithm

In difference to the

, 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 the LFSR twice to obtain a pair of bits as LFSR output. # 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⁸ + x⁴ + x³ + x² + 1'', and an initial register fill of ''1 0 1 1 0 1 1 0''. Below table lists, for each iteration of the

LFSR In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a sh ...

, 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. 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, 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, 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. Another attack {{cite journal, last1=Zenner, first1=Erik, last2=Krause, first2=Matthias, last3=Lucks, first3=Stefan, title=Improved Cryptanalysis of the Self-Shrinking Generator, journal=Information Security and Privacy 13th Australasian Conference ACISP 2008, page=30, url=https://www.researchgate.net/publication/242499559, accessdate=12 April 2016

Algorithm

Example

Cryptanalysis

References

Further reading