Cryptography with Shrinking Generators

There is one form of encryption known to be perfectly secure: a one-time pad. The idea is that two people, conventionally called Alice and Bob, have identical sheets of random 0s and 1s. When Alice wishes to send an encrypted message to Bob, she converts her message to a binary stream, adds each bit of the message to the corresponding bit on the random pad mod 2 (i.e. she takes the XOR of the bits), and sends the result to Bob. Bob then takes Alice’s encrypted message and XORs it with his copy of the pad to recover her original message.

 

The problem with one-time pads is that securely sharing the pads ahead of time is almost as difficult as securely sharing messages. And, as the name implies, the pads can only be used once. If a pad is ever reused, the method is no longer secure.

 

But what if instead of using pre-printed pads of random bits, you generate random bits? Then you don't have to exchange a stack of pads, you only have to exchange the key that was used to seed the random bit generator. Good idea! This is called a stream cipher. The problem here, however, is that most random number generators are not good enough to use in a stream cipher. Many people have independently, and naively, had the idea to use something like the Mersenne Twister random number generator for a stream cipher. Unfortunately, this would not be secure. While the Mersenne Twister has excellent statistical properties, its output can eventually be predicted by an observer.

 

The quest for random number generators suitable for stream ciphers has a long history. One of the chapters in that history is the use of shrinking generators. The idea is to take two efficient but insecure bit generators and combine them to create a secure bit generator. Specifically, both bit generators are linear feedback shift register (LFSR) streams. They are combined by using the bits from one generator to sample the other generator: take the nth bit of the second stream if and only if the nth bit of the first stream is a 1. The two input streams are linear, and subject to easy attack, but the sampling combines the two streams in a nonlinear way, making the result less susceptible to attack.

 

Sara Díaz Cardell and Amparo Fúster-Sabater have written a short book on shrinking generators with a long name: Cryptography with Shrinking Generators: Fundamentals and Applications of Keystream Sequence Generators Based on Irregular Decimation. I will refer to it here as CSG for short.

 

CSG packs a lot of information into about 100 pages, summarizing research into shrinking generators. It begins with a brief introduction to LFSRs and stream ciphers, then discusses shrinking generators. Next, it shows how shrinking generators can be modeled using cellular automata. Finally, it discusses cryptanalysis attacks against shrinking generators.

 

One puzzling aspect of the book is that it discusses the eSTREAM stream cipher competition, but does not mention how the methods in that competition relate to shrinking generators. CSG implies that shrinking generators are secure.  Despite its simplicity, there are currently no known attacks better than exhaustive search of the initial states of the registers, when the characteristic polynomials [determining the LFSRs] are secret.  However, it isn’t clear than any of the eSTREAM finalists listed in CSG actually use shrinking generators. CSG refers to a book written about the eSTREAM methods, and the only method in that book that mentions shrinking generators is DECIM v2, a method that made it to the second round of the competition but was not one of the seven finalists. (A note on the eSTREAM site says that there are no known attacks against DECIM v2, but that the method was not a finalist because other methods were faster.)

 

CSG has a lot of low-level detail for a math book, but it would be considered high-level from an electrical engineering or programming perspective. It contains several idealized circuit diagrams and tables of 0s and 1s. However, it does not go into realistic hardware diagrams, not does it go into software source code or pseudocode. The level of detail would be appropriate for mathematicians wanting to understand algorithmic details, or for hardware or software developers wanting a mathematical overview. 

---

John D. Cook is an applied math consultant with an interest in cryptography.