Shrinking generator

Last updated

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. [1]

Contents

The shrinking generator uses two linear-feedback shift registers. One, called the A sequence, generates output bits, while the other, called the S sequence, controls their output. Both A and S are clocked; if the S bit is 1, then the A bit is output; if the S bit is 0, the A bit is discarded, nothing is output, and the registers are clocked again. This has the disadvantage that the generator's output rate varies irregularly, and in a way that hints at the state of S; this problem can be overcome by buffering the output. The random sequence generated by LFSR can not guarantee the unpredictability in secure system and various methods have been proposed to improve its randomness [2]

Despite this simplicity, there are currently no known attacks better than exhaustive search when the feedback polynomials are secret. If the feedback polynomials are known, however, the best known attack requires less than A • S bits of output. [3]

A variant is the self-shrinking generator.

An implementation in Python

This example uses two Galois LFRSs to produce the output pseudorandom bitstream. The Python code can be used to encrypt and decrypt a file or any bytestream.

#!/usr/bin/env python3importsys# ----------------------------------------------------------------------------# Crypto4o functions start here# ----------------------------------------------------------------------------classGLFSR:"""Galois linear-feedback shift register."""def__init__(self,polynom,initial_value):print"Using polynom 0x%X, initial value: 0x%X."%(polynom,initial_value)self.polynom=polynom|1self.data=initial_valuetmp=polynomself.mask=1whiletmp!=0:iftmp&self.mask!=0:tmp^=self.maskiftmp==0:breakself.mask<<=1defnext_state(self):self.data<<=1retval=0ifself.data&self.mask!=0:retval=1self.data^=self.polynomreturnretvalclassSPRNG:def__init__(self,polynom_d,init_value_d,polynom_c,init_value_c):print"GLFSR D0: ",self.glfsr_d=GLFSR(polynom_d,init_value_d)print"GLFSR C0: ",self.glfsr_c=GLFSR(polynom_c,init_value_c)defnext_byte(self):byte=0bitpos=7whileTrue:bit_d=self.glfsr_d.next_state()bit_c=self.glfsr_c.next_state()ifbit_c!=0:bit_r=bit_dbyte|=bit_r<<bitposbitpos-=1ifbitpos<0:breakreturnbyte# ----------------------------------------------------------------------------# Crypto4o functions end here# ----------------------------------------------------------------------------defmain():prng=SPRNG(int(sys.argv[3],16),int(sys.argv[4],16),int(sys.argv[5],16),int(sys.argv[6],16),)withopen(sys.argv[1],"rb")asf,open(sys.argv[2],"wb")asg:whileTrue:input_ch=f.read(1)ifinput_ch=="":breakrandom_ch=prng.next_byte()&0xFFg.write(chr(ord(input_ch)^random_ch))if__name__=="__main__":main()

See also

Related Research Articles

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

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.

<span class="mw-page-title-main">Linear congruential generator</span> Algorithm for generating pseudo-randomized numbers

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 fact that its period length is chosen to be a Mersenne prime.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

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.

The Yarrow algorithm is a family of cryptographic pseudorandom number generators (CPRNG) devised by John Kelsey, Bruce Schneier, and Niels Ferguson and published in 1999. The Yarrow algorithm is explicitly unpatented, royalty-free, and open source; no license is required to use it. An improved design from Ferguson and Schneier, Fortuna, is described in their book, Practical Cryptography

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

<span class="mw-page-title-main">Hardware random number generator</span> Cryptographic device

In computing, a hardware random number generator (HRNG) or true random number generator (TRNG) is a device that generates random numbers from a physical process, rather than by means of an algorithm. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, involving a beam splitter, and other quantum phenomena. These stochastic processes are, in theory, completely unpredictable for as long as an equation governing such phenomena is unknown or uncomputable. This is in contrast to the paradigm of pseudo-random number generation commonly implemented in computer programs.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).

<span class="mw-page-title-main">/dev/random</span> Pseudorandom number generator file in Unix-like operating systems

In Unix-like operating systems, /dev/random and /dev/urandom are special files that serve as cryptographically secure pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. /dev/random typically blocked if there was less entropy available than requested; more recently it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for /dev/random and /dev/urandom.

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

Fortuna is a cryptographically secure pseudorandom number generator (PRNG) devised by Bruce Schneier and Niels Ferguson and published in 2003. It is named after Fortuna, the Roman goddess of chance. FreeBSD uses Fortuna for /dev/random and /dev/urandom is symbolically linked to it since FreeBSD 11. Apple OSes have switched to Fortuna since 2020 Q1.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but unpredictable to foresight. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from Hebrew University suggested security problems in the Windows 2000 implementation of CryptGenRandom. Microsoft later acknowledged that the same problems exist in Windows XP, but not in Vista. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.

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">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.

A counter-based random number generation is a kind of pseudorandom number generator that uses only an integer counter as its internal state. They are generally used for generating pseudorandom numbers for large parallel computations.

xoroshiro128+ is a pseudorandom number generator intended as a successor to xorshift+. Instead of perpetuating Marsaglia's tradition of xorshift as a basic operation, xoroshiro128+ uses a shift/rotate-based linear transformation designed by Sebastiano Vigna in collaboration with David Blackman. The result is a significant improvement in speed and statistical quality.

A permuted congruential generator (PCG) is a pseudorandom number generation algorithm developed in 2014 by Dr. M.E. O'Neill which applies an output permutation function to improve the statistical properties of a modulo-2n linear congruential generator. It achieves excellent statistical performance with small and fast code, and small state size.

References

  1. ↑ D. Coppersmith, H. Krawczyk, and Y. Mansour, “The shrinking generator,” in CRYPTO ’93: Proceedings of the 13th annual international cryptology conference on Advances in cryptology, (New York, NY, USA), pp. 22–39, Springer-Verlag New York, Inc., 1994
  2. ↑ Poorghanad, A. et al. Generating High Quality Pseudo Random Number Using Evolutionary methods IEEE, DOI: 10.1109/CIS.2008.220.
  3. ↑ Caballero-Gil, P. et al. New Attack Strategy for the Shrinking Generator Journal of Research and Practice in Information Technology, Vol. 1, pages 331–335, Dec 2008.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.