This paper proposes a new, surprisingly powerful method for attacking stream ciphers. It allows us to break not only a few ciphers that were up until now believed quite secure, but also holds even deeper consequences. For about a decade, designers of ciphers have embraced a path which, in order to avoid some known attacks, tried to provably preclude these attacks by using the so-called "highly non-linear components" (built out of so-called highly non-linear Boolean functions). This work adds to a few related papers which I and my coauthors published during the years 2002-2004 and which form a growing body of counter-examples, whose aim is to prove that this paradigm is incorrect, or rather, incomplete. To build an algorithm that securely encrypts data, it is not sufficient (at different stages of the design) to avoid having "too simple" Boolean functions. One should also avoid having "too simple" algebraic relations, and this is generally much harder to achieve.

First of all, the discovery of algebraic attacks on various ciphers opens up whole new avenues of research, and brings the entire area of design and the cryptanalysis of ciphers to the next level. But there is even more to consider. The fast-growing area of algebraic cryptanalysis that stems from this work is deeply connected to the general issue of what is more or less automated problem solving (similar to the issue of artificial intelligence). Many hard problems in various areas of science—mathematics, physics, chemistry, computer science, etc.—can be formalized as mathematically well-defined problems, in which one has to find a configuration satisfying a finite set of simple rules. Such problems will be expressed as solving a system of algebraic equations. Thus the new algebraic cryptanalytic techniques can tentatively be applied in almost every area of science whose processes stumble over some computationally difficult problem. How successful these methods will really be, only time will prove, yet I'm quite optimistic. In the field of cryptology we usually focus our attention on computational problems that are expected to be "very hard." It is possible that many problems that arise more naturally in science turn out to be "less hard," once we begin to examine them and find some hints.

The idea of looking at the cipher as a system of algebraic equations, and trying to solve this system to get the unknown key is not new. It had already been proposed by Claude Elwood Shannon, the father of cryptologic science, in his 1949 paper, "Communication theory of secrecy systems," (Bell System Technical Journal, 28, 1949). However, for more than 50 years it seemed simply hopeless: nobody was ever able to solve the resulting equations. Here comes the discovery of our paper: it turns out that for several known constructions of stream ciphers, devastating algebraic attacks are not hard to obtain. The weakness of these ciphers is to use a linear component that generates a long sequence of bits, and only then it is "concealed" behind a highly non-linear component (that is said to be "filtering" the sequence). We asked the question whether it exists as some algebraic equation of relatively low degree that relates only the bits of the internal linear component and the output bits, without involving any other internal intermediate bits. If only one such equation exists—and we discovered that for great many ciphers it does!—then the cipher is broken in polynomial time. This is because the linearity preserves the degree of the equations, and another equation of the same (low) degree can be written at each time during the encryption process. We get a growing system of equations of low degree, and at some point the solution (the secret key) becomes quite easy to find.

I worked on very similar algebraic attacks for several years, until one day I suddenly realized that it applies also to the cryptanalysis of block and stream ciphers. Then, with the help of my co-authors, more and more powerful attacks were obtained. The research is still an ongoing effort and, in my opinion, the full power of algebraic attacks is still greatly underestimated.