Why isn't the alternating step generator used more often?

Question

According to the Wikipedia entry for the Alternating Step pseudorandom number generator, there is no public cryptanalysis for this device since it was invented back in 1987 by C.G. Gunther. I have several questions about this:

1. If it hasn't been cracked since 1987, why is it not considered to be a candidate for a "one way function" like the RSA crypto system, the discrete logarithm system, etc.?
2. If it is unbreakable, why isn't everybody using it?
3. Why doesn't Mr. Gunther have a U.S. patent for such a great invention?

Answer 1

A stream cipher, RSA, or whatever you designate by the expression "discrete logarithm system", are not "one-way functions". In particular, asymmetric encryption algorithms and digital signature algorithms provide functionality which is not doable (or not with the same usability) with only the "scrambling" techniques of symmetric cryptography. Let's not confuse things.

ASG is a stream cipher: it produces a key-dependent sequence of pseudo-random bits, which can be combined with some data (bitwise XOR) to encrypt or decrypt it. This is symmetric encryption. As a symmetric encryption engine, it is rather lousy:

• Linear Feedback Shift Registers are inefficient in software. They used to be popular in the 70s and 80s because a LFSR is inexpensive, in terms of silicon area, when implemented in a custom ASIC. However, the World has evolved since, and has gone more and more software-based. As of 2011, extreme silicon efficiency is relevant only to very small platforms (RFID tags). For all others, ASG is just slow.

• ASG is wasteful of its state. For n-bit security, it requires three LFSR of size at least n bits. Compare it with A5/1: A5/1, with m bits of state, has a security equivalent to 2^2m/3. The original A5/1 state size is only 64 bits, so its security is in the realm of the highly breakable and open to many kinds of optimizations with precomputations; but the structure of A5/1 could be extended to longer registers, and yield adequate security. For instance, with three LFSR with a total size of 192 bits, you could get with an A5/1-like cipher about 128 bits of security, which is, in simple terms, "totally unbreakable for the foreseeable future". To get the same security level with ASG, you need 384 bits of state, i.e. twice as much.

• There is more to a stream cipher than simply spouting out bits. A complete specification should define how the key is transformed into the initial state, preferably along with an Initialization Vector, so that one could encrypt several messages with the same key (exactly what RC4 lacks, and it proved to be an endless source of vulnerable implementations). Weaknesses often hide in those steps. Without such a specification, ASG is like a car engine: regardless of its power, it will not get you far unless you add wheels.

As @Marsh points out, ASG has been patented. This alone is enough to explain that it is not widely used. There is no shortage of good stream ciphers, that we do not know how to break; why would anybody use yet another one, of questionable efficiency and subject to usage conditions and assorted royalties ? In cryptography, a patent is often a way to make sure that a given algorithm will not get used.

Answer 2

Some points on the Wikipedia entry: in the overview:

However, they cannot be used as-is because their output can be predicted easily.

and in the security section:

In Reduced Complexity Attacks on the Alternating Step Generator, Shahram Khazaei, Simon Fischer, and Willi Meier give a cryptanalysis of the ASG allowing various tradeofs between time complexity and the amount of output needed to mount the attack, e.g. with asymptotic complexity $O(L^{2} 2^{2L/3})$ and $O(2^{2L / 3})$ bits, where $L$ is the size of the shortest of the three LFSRs.

If a security equivalent to $2^{128}$ was required, we need at least $3*170$ bits of 3 LFSR( $log_{2}(170^{2}) + 2 * 170 / 3) = 128.15$ bits). In stream cipher design Thomas Pornin as one of SOSEMANUK submitter can provide a good answer.

Answer 3

But he did get a US patent for it: Generator for generating binary ciphering sequences

In fact, it looks very similar to A5/1 and A5/2 which were used in the GSM spec. The designers of A5/1 were doubtless aware of the ASG paper as it was presented in Europe the very same year. It would be really interesting to find out if they licensed it or simply worked around it, that could be the only reason for the variation.

And yes, GSM using A5/1..2 is varying degrees of "cracked".

Although Wikipedia describes controversy over the adoption of A5/1 in Europe, no one was particularly frightened of the construct itself. There was a ton of research on LFSRs back then, including ways of using the interaction of multiple LFSRs to increase the complexity. Combining LFSRs is obvious, the value comes from doing the analysis giving the justification for believing in its security.

Perhaps another way to look at the value of Gunther's contribution is that it helped the Europeans weaken GSM with much greater precision. :-)

Answer 4

If it hasn't been cracked since 1987, why is it not considered to be a candidate for a "one way function" like the RSA crypto system, the discrete logarithm system, etc.?

This generator looks like suitable for a stream cipher, i.e. it is a one-way function (of type N -> *, i.e. fixed length input, variable-length output.) Other common one-way-functions are hash functions (type * -> N: variable length input and fixed length output).

For public-key crpytography (and signature algorithms), we don't need a simple one-way function (here of type M×N -> N - input and output fixed length, M the size of the public key, N message size), but we need a trap-door one-way function - i.e. a function which normally is one-way, but which is easily inverted with some additional information. This additional information is then the private key. (In RSA, this is the factorization of the modulus n, for example.)

There is no obvious way to build a trapdoor into a stream cipher.