Self-shrinking generator

Last updated July 28, 2024

A self-shrinking generator is a pseudorandom generator that 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.^{[ who? ]}

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 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, 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	N/A
3	1	1	1	1	0	1	1	0	1	0
4	1	1	1	1	1	0	1	1	0	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

As with the shrinking generator, the self-shrinking generator is vulnerable to timing attacks since the output rate varies depending on the state.

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⁵⁷ steps, using an output sequence of only 4.9 x 10⁸ bits.

Another attack ^[3] requires 2^0.694L steps.

Related Research Articles

In telecommunications, a scrambler is a device that transposes or inverts signals or otherwise encodes a message at the sender's side to make the message unintelligible at a receiver not equipped with an appropriately set descrambling device. Whereas encryption usually refers to operations carried out in the digital domain, scrambling usually refers to operations carried out in the analog domain. Scrambling is accomplished by the addition of components to the original signal or the changing of some important component of the original signal in order to make extraction of the original signal difficult. Examples of the latter might include removing or changing vertical or horizontal sync pulses in television signals; televisions will not be able to display a picture from such a signal. Some modern scramblers are actually encryption devices, the name remaining due to the similarities in use, as opposed to internal operation.

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.

The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto and Takuji Nishimura. Its name derives from the choice of a Mersenne prime as its period length.

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It is one of several implementations of the A5 security protocol. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified.

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 Berlekamp–Massey algorithm is an algorithm that will find the shortest linear-feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse. Reeds and Sloane offer an extension to handle a ring.

A maximum length sequence (MLS) is a type of pseudorandom binary sequence.

A pseudorandom binary sequence (PRBS), pseudorandom binary code or pseudorandom bitstream is a binary sequence that, while generated with a deterministic algorithm, is difficult to predict and exhibits statistical behavior similar to a truly random sequence. PRBS generators are used in telecommunication, such as in analog-to-information conversion, but also in encryption, simulation, correlation technique and time-of-flight spectroscopy. The most common example is the maximum length sequence generated by a (maximal) linear feedback shift register (LFSR). Other examples are Gold sequences, Kasami sequences and JPL sequences, all based on LFSRs.

A nonlinear-feedback shift register (NLFSR) is a shift register whose input bit is a non-linear function of its previous state.

Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommend a maximum length of output per pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.

SNOW is a family of word-based synchronous stream ciphers developed by Thomas Johansson and Patrik Ekdahl at Lund University.

In cryptography, SOBER is a family of stream ciphers initially designed by Greg Rose of QUALCOMM Australia starting in 1997. The name is a contrived acronym for Seventeen Octet Byte Enabled Register. Initially the cipher was intended as a replacement for broken ciphers in cellular telephony. The ciphers evolved, and other developers joined the project.

In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator used in stream ciphers, based on three linear-feedback shift registers. Its output is a combination of two LFSRs which are stepped (clocked) in an alternating fashion, depending on the output of a third LFSR.

<span class="mw-page-title-main">Crypto-1</span> Stream cipher

Crypto1 is a proprietary encryption algorithm and authentication protocol created by NXP Semiconductors for its MIFARE Classic RFID contactless smart cards launched in 1994. Such cards have been used in many notable systems, including Oyster card, CharlieCard and OV-chipkaart.

<span class="mw-page-title-main">Xorshift</span> Class of pseudorandom number generators

Xorshift random number generators, also called shift-register generators, are a class of pseudorandom number generators that were invented by George Marsaglia. They are a subset of linear-feedback shift registers (LFSRs) which allow a particularly efficient implementation in software without the excessive use of sparse polynomials. They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit-shifted version of itself. This makes execution extremely efficient on modern computer architectures, but it does not benefit efficiency in a hardware implementation. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.

Correlation attacks are a class of cryptographic known-plaintext attacks for breaking stream ciphers whose keystreams are generated by combining the output of several linear-feedback shift registers (LFSRs) using a Boolean function. Correlation attacks exploit a statistical weakness that arises from the specific Boolean function chosen for the keystream. While some Boolean functions are vulnerable to correlation attacks, stream ciphers generated using such functions are not inherently insecure.

In sequence design, a Feedback with Carry Shift Register is the arithmetic or with carry analog of a linear-feedback shift register (LFSR). If $is an integer, then an N -ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer . The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in .$

References

↑ "The self-shrinking generator", Advances in Cryptology – Eurocrypt 1994 (LNCS 950), 205-214, 1995.
↑ "An security examination of the self-shrinking generator", Circencester, UK, December 1995.
↑ Zenner, Erik; Krause, Matthias; Lucks, Stefan. "Improved Cryptanalysis of the Self-Shrinking Generator". Information Security and Privacy 13th Australasian Conference ACISP 2008: 30. Retrieved 12 April 2016.