|Previous||Table of Contents||Next|
The original UNIX encryption algorithm, crypt(1), is a stream cipher based on the same ideas as the Enigma. This is a 256-element, single-rotor substitution cipher with a reflector. Both the rotor and the reflector are generated from the key. This algorithm is far simpler than the World War II German Enigma and, for a skilled cryptanalyst, very easy to break [1576,1299]. A public-domain UNIX program, called Crypt Breakers Workbench (CBW), can be used to break files encrypted with crypt(1).
Another generator is based on the knapsack problem (see Section 19.2) . CRYPTO-LEGGO is insecure . Joan Daemen has developed SubStream, Jam, and StepRightUp ; they are all too new to comment on. Many other algorithms are described in the literature, and even more are kept secret and incorporated into equipment.
In practice, stream-cipher design is a lot like block-cipher design. It involves more mathematical theory, but in the end a cryptographer proposes a design and then tries to analyze it.
According to Rainer Rueppel, there are four different approaches to the construction of stream ciphers [1360,1362]:
The approaches differ in their assumptions about the capabilities and opportunities of the cryptanalyst, the definition of cryptographic success, and the notion of security. Most of the research in this field is theoretical, but there are some good stream ciphers among the impractical ones.
The system-theoretic approach was used in all the stream ciphers previously listed; it produces most of the stream ciphers that are practical enough to be used in the real world. A cryptographer designs keystream generators that have testable security propertiesperiod, distribution of bit patterns, linear complexity, and so onand not ciphers based on mathematical theory. The cryptographer also studies various cryptanalytic techniques against these generators and makes sure the generators are immune to these attacks.
Over the years, the approach has resulted in a set of design criteria for stream ciphers [1432,99,1357,1249]. These were discussed by Rueppel in , in which he details the theory behind them.
This list of design criteria is not unique for stream ciphers designed by the system-theoretic approach; it is true for all stream ciphers. It is even true for all block ciphers. The unique point about the system-theoretic approach is that stream ciphers are designed to satisfy these goals directly.
The major problem with these cryptosystems is that nothing can be proven about their security; the design criteria have never been proved to be either necessary or sufficient for security. A keystream generator may satisfy all the design principles, but could still turn out to be insecure. Another could turn out to be secure. There is still some magic to the process.
On the other hand, breaking each of these keystream generators is a different problem for a cryptanalyst. If enough different generators are out there, it may not be worth the cryptanalysts time to try to break each one. He may better achieve fame and glory by figuring out better ways to factor large numbers or calculating discrete logarithms.
Rueppel also delineated a complexity-theoretic approach to stream-cipher design. Here, a cryptographer attempts to use complexity theory to prove that his generators are secure. Consequently, the generators tend to be more complicated, based on the same sorts of hard problems as public-key cryptography. And like public-key algorithms, they tend to be slow and cumbersome.
Shamirs Pseudo-Random-Number Generator
Adi Shamir used the RSA algorithm as a pseudo-random-number generator . While Shamir showed that predicting the output of the pseudo-random-number generator is equivalent to breaking RSA, potential biases in the output were demonstrated in [1401,200].
This generator gets its security from the difficulty of computing discrete logarithms . Let g be a prime and p be an odd prime. A key x0, starts off the process:
The output of the generator is 1 if xi < (p - 1)/2, and 0 otherwise.
If p is large enough so that computing discrete logarithms mod p is infeasible, then this generator is secure. Additional theoretical results can be found in [1627,986,985,1237,896,799].
This RSA generator [35,36] is a modification of . The initial parameters are a modulus N which is the product of two large primes p and q, an integer e which is relatively prime to (p - 1) (q - 1), and a random seed x0, where x0 is less than N.
The output of the generator is the least significant bit of xi. The security of this generator is based on the difficulty of breaking RSA. If N is large enough, then the generator is secure. Additional theory can be found in [1569,1570,1571,30,354].
Blum, Blum, and Shub
The simplest and most efficient complexity-theoretic generator is called the Blum, Blum, and Shub generator, after its inventors. Mercifully, we shall abbreviate it to BBS, although it is sometimes called the quadratic residue generator .
|Previous||Table of Contents||Next|