 Classification

Stream ciphers can be either symmetric-key or public-key. The focus of this chapter is symmetric-key stream ciphers; the Blum-Goldwasser probabilistic public-key encryption scheme (§8.7.2) is an example of a public-key stream cipher.

• 6.1 Note (block vs. stream ciphers) Block ciphers process plaintext in relatively large blocks (e.g., n > 64 bits). The same function is used to encrypt successive blocks; thus (pure) block ciphers are memoryless. In contrast, stream ciphers process plaintext in blocks as small as a single bit, and the encryption function may vary as plaintext is processed; thus stream ciphers are said to have memory. They are sometimes called state ciphers since encryption depends on not only the key and plaintext, but also on the current state. This distinction between block and stream ciphers is not definitive (see Remark 7.25); adding a small amount of memory to a block cipher (as hr the CBC mode) results in a stream cipher with large blocks.

Recall (Definition 1.39) that a Vernam cipher over the binary alphabet is defined by where mi, m2, m3,... are the plaintext digits, ki, ^2, &з, • • • (the key stream) are the key digits, ci, С2,сз,... are the ciphertext digits, and ® is the XOR function (bitwise addition modulo 2). Decryption is defined by m, = If the keystrearn digits are generated

independently and randomly, the Vernam cipher is called a one-time pad, and is unconditionally secure (§1.13.3(i)) against a ciphertext-only attack. More precisely, if M, C, and К are random variables respectively denoting the plaintext, ciphertext, and secret key, and if H() denotes the entropy function (Definition 2.39), then H(MC) = H(M). Equivalently, I(M: C) = 0 (see Definition 2.45): the ciphertext contributes no information about the plaintext.

Shannon proved that a necessary condition for a symmetric-key encryption scheme to be unconditionally secure is that H{K) > H(M). That is, the uncertainty of the secret key must be at least as great as the uncertainty of the plaintext. If the key has bitlength k, and the key bits are chosen randomly and independently, then H{K) = k, and Shannon’s necessary condition for unconditional security becomes к > H(M). The one-time pad is unconditionally sectrre regardless of the statistical distribution of the plaintext, and is optimal in the sense that its key is the smallest possible among all symmetric-key encryption schemes having this property.

An obvious drawback of the one-time pad is that the key should be as long as the plaintext, which increases the difficulty of key distribution and key management. This motivates the design of stream ciphers where the keystrearn is pseudorandomly generated from a smaller secret key, with the intent that the keystrearn appears random to a computationally bounded adversary. Such stream ciphers do not offer unconditional secirrity (since H(K) < ff (M)), but the hope is that they are computationally secure (§1.13.3(iv)).

Stream ciphers are commonly classified as being synchronous or self-synchronizing.

• (ii) Synchronous stream ciphers
• 6.2 Definition A synchronous stream cipher is one in which the keystream is generated independently of the plaintext message and of the ciphertext.

The encryption process of a synchronous stream cipher can be described by the equations where o0 is the initial state and may be determined from the key k, f is the next-state function, д is the function which produces the keystream zt, and h is the output function which combines the keystream and plaintext m, to produce ciphertext c*. The encryption and decryption processes are depicted hi Figure 6.1. The OFB mode of a block cipher (see §7.2.2(iv)) is an example of a synchronous stream cipher. Figure 6.1: General model of a synchronous stream cipher.

• 6.3 Note (properties of synchronous stream ciphers)
• (i) synchronization requirements. In a synchronous stream cipher, both the sender and receiver must be synchronized - using the same key and operating at the same position (state) within that key - to allow for proper decryption. If synchronization is lost due to ciphertext digits being inserted or deleted during transmission, then decryption fails and can only be restored through additional techniques for re-synchronization. Techniques for re-synchronization include re-initialization, placing special markers at regular intervals in the ciphertext, or, if the plaintext contains enough redundancy, trying all possible keystream offsets.
• (ii) no error propagation. A ciphertext digit that is modified (but not deleted) during transmission does not affect the decryption of other ciphertext digits.
• (iii) active attacks. As a consequence of property (i), the insertion, deletion, or replay of ciphertext digits by an active adversary causes immediate loss of synchronization, and hence might possibly be detected by the decryptor. As a consequence of property (ii), an active adversary might possibly be able to make changes to selected ciphertext digits, and know exactly what affect these changes have on the plaintext. This illustrates that additional mechanisms must be employed in order to provide data origin authentication and data integrity guarantees (see §9.5.4).

Most of the stream ciphers that have been proposed to date in the literature are additive stream ciphers, which are defined below.

6.4 Definition A binary> additive stream cipher is a synchronous stream cipher in which the keystream, plaintext, and ciphertext digits are binary digits, and the output function h is the XOR function.

Binary additive stream ciphers are depicted in Figure 6.2. Referring to Figure 6.2, the keystream generator is composed of the next-state function / and the function д (see Figure 6.1), and is also known as the running key generator. Figure 6.2: General model of a binaiy additive stream cipher.

• (iii) Self-synchronizing stream ciphers
• 6.5 Definition A self-synchronizing or asynchronous stream cipher is one in which the key- stream is generated as a function of the key and a fixed number of previous ciphertext digits.

The encryption function of a self-synchronizing stream cipher can be described by the equations where a0 = (c_t,c_t+i,... , c_i) is the (non-secret) initial state, к is the key, д is the function which produces the keystream zt, and h is the output function which combines the keystream and plaintext mt to produce ciphertext c*. The encryption and decryption processes are depicted in Figure 6.3. The most common presently-used self-synchronizing stream ciphers are based on block ciphers in 1-bit cipher feedback mode (see §7.2.2(iii)). Figure 6.3: General model of a self-synchronizing stream cipher.

• 6.6 Note (properties of self-synchronizing stream ciphers)
• (i) self-synchronization. Self-synchronization is possible if ciphertext digits are deleted or inserted, because the decryption mapping depends only on a fixed number of preceding ciphertext characters. Such ciphers are capable of re-establishing proper decryption automatically after loss of synchronization, with only a fixed number of plaintext characters unrecoverable.
• (ii) limited error propagation. Suppose that the state of a self-synchronization stream cipher depends on t previous ciphertext digits. If a single ciphertext digit is modified (or even deleted or inserted) during transmission, then decryption of up to t subsequent ciphertext digits may be incorrect, after which correct decryption resumes.
• (iii) active attacks. Property (ii) implies that any modification of ciphertext digits by an active adversary causes several other ciphertext digits to be decrypted incorrectly, thereby improving (compared to synchronous stream ciphers) the likelihood of being detected by the decryptor. As a consequence of property (i), it is more difficult (than for synchronous stream ciphers) to detect insertion, deletion, or replay of ciphertext digits by an active adversary. This illustrates that additional mechanisms must be employed in order to provide data origin authentication and data integrity guarantees (see §9.5.4).
• (iv) diffusion of plaintext statistics. Since each plaintext digit influences the entire following ciphertext, the statistical properties of the plaintext are dispersed through the ciphertext. Hence, self-synchronizing stream ciphers may be more resistant than synchronous stream ciphers against attacks based on plaintext redundancy.