Shrinking generator

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 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 we clock the registers 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.

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

An interesting variant is the self-shrinking generator.

An implementation of a shrinking generator in Python[edit]

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/python
 
    import sys
 
    # ----------------------------------------------------------------------------
    # Crypto4o functions start here
    # ----------------------------------------------------------------------------
 
    class glfsr:
        def __init__(self, polynom, initial_value):
            self.polynom = polynom | 1
            self.data = initial_value
            tmp = polynom
 
            self.mask = 1
 
            while tmp != 0:
                if tmp & self.mask != 0:
                    tmp = tmp ^ self.mask;
 
                if tmp == 0:
                    break
 
                self.mask = self.mask << 1
 
        def next_state(self):
            self.data = self.data << 1
 
            retval = 0
 
            if self.data & self.mask != 0:
                retval = 1
                self.data = self.data ^ self.polynom
 
            return retval
 
    class sprng:
        def __init__(self, polynom_d, init_value_d, polynom_c, init_value_c):
            self.glfsr_d = glfsr(polynom_d, init_value_d)
            self.glfsr_c = glfsr(polynom_c, init_value_c)
 
        def next_byte(self):
            byte = 0
            bitpos = 7
 
            while 1 == 1:
                bit_d = self.glfsr_d.next_state()
                bit_c = self.glfsr_c.next_state()
 
                if bit_c != 0:
                    bit_r = bit_d
                    byte = byte | (bit_r << bitpos)
 
                    bitpos = bitpos - 1
 
                    if bitpos < 0:
                        break
 
            return byte
 
    # ----------------------------------------------------------------------------
    # Crypto4o functions end here
    # ----------------------------------------------------------------------------
 
    def main():
        prng = sprng(int(sys.argv[3], 16), int(sys.argv[4], 16),
            int(sys.argv[5], 16), int(sys.argv[6], 16))
 
        print "GLFSR D0: using polynom 0x%X, initial value: 0x%X." % (int(sys.argv[3], 16), int(sys.argv[4], 16))
        print "GLFSR C0: using polynom 0x%X, initial value: 0x%X." % (int(sys.argv[5], 16), int(sys.argv[6], 16))
 
        f = open(sys.argv[1], "rb")
        g = open(sys.argv[2], "wb")
 
        while 1 == 1:
            input_ch = f.read(1)
 
            if input_ch == "":
                break
 
            random_ch = prng.next_byte() & 0xff
            g.write(chr(ord(input_ch) ^ random_ch))
 
        f.close()
        g.close()
 
    main()

The C code is also available, see External links.

See also[edit]

References[edit]

  1. ^ Caballero-Gil, P. et al. New Attack Strategy for the Shrinking Generator Journal of Research and Practice in Information Technology, Vol. 41, No. 2, May 2009.