In cryptography, a stream cipher is a symmetric cipher in which the input digits are encrypted one at a time, and in which the transformation of successive digits varies during the encryption. An alternative name is a state cipher, as the encryption of each digit is dependent on the current state. In practice, the digits are typically single bits or bytes.

Stream ciphers represent a different approach to symmetric encryption from block ciphers. Block ciphers operate on large blocks of digits with a fixed, unvarying transformation. This distinction is not always clear-cut: some modes of operation use a block cipher primitive in such a way that it then acts effectively as a stream cipher. Stream ciphers typically execute at a higher speed than block ciphers and have lower hardware complexity. However, stream ciphers can be susceptible to serious security problems if used incorrectly: see stream cipher attacks — in particular, the same starting state must never be used twice.

NSA documents sometimes use the term combiner-type algorithms, referring to algorithms that use some function to combine a pseudorandom number generator (PRNG) with a plaintext stream.

Loose inspiration from the one-time pad

Stream ciphers can be viewed as approximating the action of the only theoretically unbreakable cipher, the one-time pad (OTP), sometimes known as the Vernam cipher. A one-time pad uses a key stream of completely random digits. The key stream is combined with the plaintext digits one at a time to form the ciphertext. This system was proved to be theoretically secure by Shannon in 1949. However, the key stream must be (at least) the same length as the plaintext, and generated completely at random. This makes the system very cumbersome to implement in practice, and as a result the one-time pad has not been widely used.

A stream cipher makes use of a much smaller and convenient key — 128 bits, for example. Based on this key, it generates a pseudorandom key stream which can be combined with the plaintext digits in a similar fashion to the one-time pad. However, this comes at a cost: because the keystream is now pseudorandom, and not truly random, the proof of security associated with the one-time pad no longer holds: it is quite possible for a stream cipher to be completely insecure.

Types of stream cipher

A stream cipher generates successive elements of the keystream based on an internal state. This state is updated in essentially two ways: if the state changes independently of the plaintext or ciphertext messages, the cipher is classified as a synchronous stream cipher. By contrast, self-synchronising stream ciphers update their state based on previous ciphertext digits.

Synchronous stream ciphers

In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher.

In a synchronous stream cipher, the sender and receiver must be exactly in step for decryption to be successful. If digits are added or removed from the message during transmission, synchronisation is lost. To restore synchronisation, various offsets can be tried systematically to obtained the correct decryption. Another approach is to tag the ciphertext with markers at regular points in the output.

If, however, a digit is corrupted in transmission, rather than added or lost, only a single digit in the plaintext is affected and the error does not propagate to other parts of the message. This property is useful when the transmission error rate is high; however, it makes it less likely the error would be detected without further mechanisms. Moreover, because of this property synchronous stream ciphers are very susceptible to active attacks — if an attacker can change a digit in the ciphertext, he might be able to make predictable changes to the corresponding plaintext bit; for example, flipping a bit in the ciphertext causes the same bit to be flipped in the plaintext.

Self-synchronising stream ciphers

Another approach uses several of the previous N ciphertext digits to compute the keystream. Such schemes are known as self-synchronizing stream ciphers, asynchronous stream ciphers or ciphertext autokey (CTAK). The idea of self-synchronization was patented in 1946 (), and has the advantage that the receiver will automatically synchronise with the keystream generator after receiving N ciphertext digits, making it easier to recover if digits are dropped or added to the message stream. Single-digit errors are limited in their effect, affecting only up to N plaintext digits. It is somewhat more difficult to perform active attacks on self-synchronising stream ciphers by comparison with their synchronous counterparts.

An example of a self-synchronising stream cipher is a block cipher in cipher-feedback mode (CFB).

LFSR-based stream ciphers

Linear feedback shift registers (LFSRs) are popular components in stream ciphers as they can be implemented cheaply in hardware, and their properties are well-understood.

Binary stream ciphers are often constructed using linear feedback shift registers (LFSR)s because they can be easily implemented in hardware and can be readily analysed mathematically. The use of LFSRs on their own, however, is insufficient to provide good security. Various schemes have been proposed to increase the security of LFSRs.

Non-linear combining functions

Because LFSRs are inherently linear, one technique for removing the linearity is to feed the outputs of several parallel LFSRs into a non-linear [[Boolean function] to form a combination generator. Various properties of such a combining function are criticial for ensuring the security of the resultant scheme, for example, in order to avoid correlation attacks .

Clock-controlled generators

Normally LFSRs are stepped regularly. One approach to introducting non-linearity is to have the LFSR clocked irregularly, controlled by the output of a second LFSR. Such generators include the stop-and-go generator , the alternating step generator and the shrinking generator.

The stop-and-go generator (Beth and Piper, 1984) consists of two LFSRs. One LFSR is clocked if the output of a second is a "1", otherwise it repeats its previous output. This output is then (in some versions) combined with the output of a third LFSR clocked at a regular rate.

The shrinking generator takes a different approach. Two LFSRs are used, both clocked regularly. If the output of the first LFSR is "1", the output of the second LFSR becomes the output of the generator. If the first LFSR outputs "0", however, the output of the second is discarded, and no bit is output by the generator. This mechanism suffers from timing attacks on the second generator, since the speed of the output is variable in a manner that depends on the second generator's state. This can be alleviated by buffering the output.

This section is a stub. You can help Wikipedia by (PDF).