RSA Laboratories

3.6.10 What are some other stream ciphers?

There are a number of alternative stream ciphers that have been proposed in cryptographic literature as well as a large number that appear in implementations and products world-wide. Many are based on the use of LFSRs (Linear Feedback Shift Registers; see Question 2.1.5), since such ciphers tend to be more amenable to analysis and it is easier to assess the security they offer.

Rueppel suggests there are essentially four distinct approaches to stream cipher design [Rue92]. The first is termed the information-theoretic approach as exemplified by Shannon's analysis of the one-time pad. The second approach is that of system-theoretic design. In essence, the cryptographer designs the cipher along established guidelines that ensure the cipher is resistant to all known attacks. While there is, of course, no substantial guarantee that future cryptanalysis will be unsuccessful, it is this design approach that is perhaps the most common in cipher design. The third approach is to attempt to relate the difficulty of breaking the stream cipher (where "breaking" means being able to predict the unseen keystream with a success rate better than can be achieved by guessing) to solving some difficult problem (see [BM84] [BBS86]). This complexity-theoretic approach is very appealing, but in practice the ciphers developed tend to be rather slow and impractical. The final approach highlighted by Rueppel is that of designing a randomized cipher. Here the aim is to ensure the cipher is resistant to any practical amount of cryptanalytic work, rather than being secure against an unlimited amount of work, as was the aim with Shannon's information-theoretic approach.

A recent example of a stream cipher designed by a system-theoretic approach is the Software-optimized Encryption Algorithm (SEAL), which was designed by Rogaway and Coppersmith in 1993 [RC93] as a fast stream cipher for 32-bit machines. SEAL has a rather involved initialization phase during which a large set of tables is initialized using the Secure Hash Algorithm (see Question 3.6.5). However, the use of look-up tables during keystream generation helps to achieve a very fast performance with just five instructions required per byte of output generated.

A design that has system-theoretic as well as complexity-theoretic aspects is given by Aiello, Rajagopalan, and Venkatesan [ARV95]. The design, commonly referred to as "VRA," derives a fast stream cipher from an arbitrary secure block cipher. VRA is described as a pseudo-random generator (see Question 2.5.2), not a stream cipher, but the two concepts are closely connected, since a pseudo-random generator can produce a (pseudo) one-time pad for encryption.

For examples of ciphers in each of these categories, see Rueppel's article [Rue92] or any book on contemporary cryptography. More details are also provided in an RSA Laboratories technical report [Rob95a].

Top of the page