Stream Ciphers

From a purely mathematical point of view, cryptography is a completely solved problem. In 1882, Frank Miller proposed a cipher system that has become known as a “one-time pad,” which is a method of encrypting text one character at a time, where each character is shifted in the alphabet by a random amount. In other words, as Claude Shannon proved in the 1940s, if two parties can agree on an arbitrarily long string of completely random numbers that only the two of them know and they use these strings correctly then they can send a message that there is absolutely no way that any eavesdropper could decrypt. Of course, as with many results in theoretical mathematics, this system is completely impractical in real life — for example, how am I supposed to agree on a string of any length with Amazon.com given that I live thousands of miles away from their computer servers? And even if we could agree on a short string (as more modern “public key” cryptosystems allow us to do), it is still computationally extremely inefficient to generate and agree on the very long, purely random strings that would be required for a one time pad.

One approach to getting around this issue is what have become known as “stream ciphers.” To use a stream cipher, the two parties only agree on a relatively short key ahead of time (which public key methods allow them to do relatively easily), and they then use this short key to generate an arbitrarily long string that they can use in a way similar to a one time pad. Of course, strictly speaking the string they are using is not a one time pad, as it is not purely random. Rather, it is what we often call pseudorandom, and much theory has gone into developing these pseudorandom number generators that can be used in stream ciphers. This is the topic of Andreas Klein’s book Stream Ciphers, which has recently been published by Springer.

Klein’s book opens with a chapter giving some historical background, explaining how stream ciphers evolved over time and how to view certain historical ciphers such as the Vigenere Cipher and the Enigma machine through this lens. The theoretical meat of the book is contained in the next six chapters, which introduce the concept of linear feedback shift registers (LFSRs), and discuss their relative strengths and weaknesses from a cryptographic point of view. LFSRs might be more familiar to mathematicians if they are phrased as linear recurrence relations over the integers mod 2, and Klein discusses the theory as well as some computational algorithms behind these. He writes of several weaknesses that exploit the linear nature of LFSRs, leading to several descriptions of non-linear ways of combining LFSRs to circumvent these attacks. The next few chapters describe the cryptanalysis of stream ciphers and ways of circumventing them. These include various algebraic attacks, which means the author has to give the reader a crash course in Gröbner Bases and methods of solving polynomial equations over finite fields. He also introduces the idea of irregular clock control, which makes aspects of the cryptography more secure but also increases the susceptibility to side-channel attacks such as analyzing the power that a machine uses.

While these chapters have a number of examples, some of which are based on “real world” ciphers, the next part of the book goes into great detail on a handful of such ciphers. In particular, there is a full chapter dedicated to the GSM protocol used by mobile phones and another chapter dedicated to the RC4 cipher which is part of the WEP wireless protocol that is commonly used. These discussions go into depth not just about the mathematics of the ciphers themselves but also issues such as key scheduling and efficiency of the implementations. There are also sections dedicated to ciphers with names such as Trivium, Rabbit, and Mosquito, and a whole chapter devoted to the Blum-Blum-Shub pseudorandom number generator.

As one might guess from what I have written, the discussing the range of topics in this book involves pulling in a large number of ideas from throughout mathematics and computer science, and most readers probably will need a refresher on some of these topics if not a whole introduction from scratch. While Klein does not do a lot of this in the early chapters of the book, the last few chapters are devoted to these ideas, and give a reader an introduction to the main ideas that he uses from computational complexity, numerical linear algebra, number theory, the theory of finite fields, combinatorics, and statistics. These are obviously not as detailed as a textbook in the areas would be, but he does a good job of quickly hitting the important points. He also gives an introduction to some of the computer programs he discusses in the text which are available on his website as well as a tool he has developed for literate programming. The book also contains a chapter of exercises and solutions that I found useful to try my hand at.

It is probably inevitable that a book covering these types of topics is fairly inconsistent in its level of difficulty, and I know that I found parts of the book far more readable (not to mention more interesting) than other parts. There are parts of it that would be accessible to beginning undergraduate students, and other parts of it that I think will be over the head of anyone who is not an active researcher in the field. But on the whole Klein does a good job of introducing some very interesting ideas in mathematics in a very applied way, and if you are interested in learning about some modern ideas in cryptography it is a good place to look.

Darren Glass is an Associate Professor of Mathematics at Gettysburg College whose research interests include Algebraic Geometry, Number Theory, and Cryptography. He can be reached at dglass@gettysburg.edu.