Stream cipher

A stream cipher is a cipher which encrypts data by combining the plaintext with the output of a keyed pseudorandom number generator to generate the ciphertext. To decrypt, run the generator with the same key to generate the same pseudorandom data, then reverse the combining operation to convert ciphertext back to plaintext.

Many stream ciphers use bitwise XOR as the combining operation. This is convenient since XOR is its own inverse, so encryption and decryption use exactly the same operations. However, any operation that has an inverse may be used. Some stream ciphers use bytewise (mod 256) addition to encrypt, subtraction to decrypt. Bruce Schneier's Solitaire (http://www.schneier.com/solitaire.html) is intended to be used manually rather than on a computer; it uses addition and subtraction mod 26 to encrypt at letter level.

The hard part of stream cipher design is the pseudorandom generator. An enemy who knows or guesses some plaintext and has intercepted the matching ciphertext can easily get some of the pseudorandom data. If that allows him to infer the internal state of the generator, then he can break the cipher.

A one-time pad is in effect the ultimate stream cipher. It requires a truly random key as long as long as the data to be encrypted, which makes it impractical for many applications. Given such a key, however, there is no need to generate pseudorandom material and therefore no need to worry about the quality of the generator.

A design problem for stream cipher implementations is how to maintain synchronisation; if the encrypting and decrypting devices get out of sync, generating different pseudorandom output, then communication is lost. In many applications, this is an easy problem but in some cases it can be quite difficult. Consider battlefield communications with noise everywhere and an enemy who attempts to disrupt your communications.

There are some usage restrictions. In particular, never encrypt two different messages with the same pseudorandom data (or even the same truly random data; see VENONA). Using P for plaintext, C for ciphertext, R for (pseudo)random, and ^ for XOR this makes the encryptions:

C1 = P1^R
C2 = P2^R

The enemy can intercept both ciphertexts, so he does:

X = C1^C2 = P1^R^P2^R

and the Rs conveniently cancel out, so he has

X = P1^P2

This is very weak indeed. Given moderately strong knowledge of plaintext properties — for example, that it is English text — it can be broken using techniques such as frequency counting that have been well-known for centuries and can be done with pencil and paper. See History of cryptography for details. Even with weaker knowledge of the input format, it is still breakable.