 Stream ciphers

Stream ciphers form an important class of symmetric-key encryption schemes. They are, in one sense, veiy simple block ciphers having block length equal to one. What makes them useful is the fact that the encryption transformation can change for each symbol of plaintext being encrypted. In situations where transmission errors are highly probable, stream ciphers are advantageous because they have no error propagation. They can also be used when the data must be processed one symbol at a time (e.g., if the equipment has no memory or buffering of data is limited).

• 1.37 Definition Let K. be the key space for a set of encryption transformations. A sequence of symbols ei «2^3 • ■ ■ e< € /С, is called a key stream.
• 1.38 Definition Let A be an alphabet of q symbols and let Ee be a simple substitution cipher with block length 1 where e e K.. Let тхт^пгз ■ ■ ■ be a plaintext string and let е^ез • • • be a keystream from K. A stream cipher takes the plaintext string and produces a ciphertext string С1С2С3 • • • where c, = E(,t (m,). If dt denotes the diverse of e*, then D,t, (с*) = m, decrypts the ciphertext string.

A stream cipher applies simple encryption transformations according to the keystream being used. The keystream could be generated at random, or by an algorithm which generates the keystream from an initial small keystream (called a seed), or from a seed and previous ciphertext symbols. Such an algorithm is called a keystream generator.

The Vernam cipher

A motivating factor for the Vernam cipher was its simplicity and ease of implementation.

1.39 Definition The Vernam Cipher is a stream cipher defined on the alphabet A = {0,1}. A binary message mi m2 • • • mt is operated on by a binary key string kki of the same length to produce a ciphertext string cC2 - ■ - ct where If the key string is randomly chosen and never used again, the Vernam cipher is called a one-time system or a one-time pad.

To see how the Vernam cipher corresponds to Definition 1.38, observe that there are precisely two substitution ciphers on the set A. One is simply the identity map E0 which sends 0 to 0 and 1 to 1; the other E sends 0 to 1 and 1 to 0. When the keystream contains a 0, apply E0 to the corresponding plaintext symbol; otherwise, apply E.

If the key string is reused there are ways to attack the system. For example, if C1C2 • • • ct and c'xc2 • • • cj are two ciphertext strings produced by the same keystream кк2 ■ ■ ■ kt then and Ci 0 c- = m* 0 m'. The redundancy in the latter may permit cryptanalysis.

The one-time pad can be shown to be theoretically unbreakable. That is, if a cryptanalyst has a ciphertext string C1C2 • • • ct encrypted using a random key string which has been used only once, the cryptanalyst can do no better than guess at the plaintext being any binary string of length t (i.e., f-bit binary strings are equally likely as plaintext). It has been proven that to realize an unbreakable system requires a random key of the same length as the message. This reduces the practicality of the system in all but a few specialized situations. Reportedly until very recently the communication line between Moscow and Washington was secured by a one-tune pad. Transport of the key was done by trusted courier.

The key space

The size of the key space is the number of encryption/decryptionkey pans that are available in the cipher system. A key is typically a compact way to specify the encryption transformation (from the set of all encryption transformations) to be used. For example, a transposition cipher of block length t has /! encryption functions from which to select. Each can be simply described by a permutation which is called the key.

It is a great temptation to relate the security of the encryption scheme to the size of the key space. The following statement is important to remember.

1.40 Fact A necessary, but usually not sufficient, condition for an encryption scheme to be secure is that the key space be large enough to preclude exhaustive search.

For instance, the simple substitution cipher in Example 1.25 has a key space of size 26! « 4 x 102G. The polyalphabetic substitution cipher of Example 1.31 has a key space of size (26!)3 « 7 x 1079. Exhaustive search of either key space is completely infeasible, yet both ciphers are relatively weak and provide little security.