Incryptography, theshrinking generator is a form ofpseudorandom number generator intended to be used in astream cipher. It was published in Crypto 1993 byDon Coppersmith,Hugo Krawczyk andYishay Mansour.[1]
The shrinking generator uses twolinear-feedback shift registers. One, called theA sequence, generates output bits, while the other, called theS sequence, controls their output. BothA andS are clocked; if theSbit is 1, then theA bit is output; if theS bit is 0, theA 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 thathints 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 thanA •S bits of output.[3]
A variant is theself-shrinking generator.
An implementation in Python
editThis 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
edit- FISH, an (insecure)stream cipher based on the shrinking generator principle
- Alternating step generator, a similarstream cipher
References
edit- ^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
- ^Poorghanad, A. et al.Generating High Quality Pseudo Random Number Using Evolutionary methodsIEEE, DOI: 10.1109/CIS.2008.220.
- ^Caballero-Gil, P. et al.New Attack Strategy for the Shrinking GeneratorJournal of Research and Practice in Information Technology, Vol. 1, pages 331–335, Dec 2008.