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: in some modes of operation, a block cipher primitive is used in such a way that it 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.
A stream cipher makes use of a much smaller and more convenient key — 128 bits, for example. Based on this key, it generates a pseudorandom keystream 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.
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.
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 obtain 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.
An example of a self-synchronising stream cipher is a block cipher in cipher-feedback mode (CFB).
Binary stream ciphers are often constructed using linear feedback shift registers (LFSRs) 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.
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 critical for ensuring the security of the resultant scheme, for example, in order to avoid correlation attacks.
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.
Instead of a linear driving device, one may use a nonlinear update function. For example, Klimov and Shamir proposed triangular functions (T-Functions) with a single cycle on n bit words.
To be secure, the period of the keystream, that is, the number of digits output before the stream repeats itself, needs to be sufficiently large. If the sequence repeats, then the overlapping ciphertexts can be aligned against each other "in depth", and there are techniques which could allow the plaintext to be extracted. This can be a practical concern: for example, the DES block cipher was initially allowed to be used in a certain mode (OFB) with a varying parameter. However, for most choices of this parameter, the resulting stream had a period of only 232 — for many applications, this period is far too low. For example, if encryption is being performed at a rate of 1 megabyte per second, a stream of period 232 will repeat after around 8.5 minutes.
Another advantage of stream ciphers in military cryptography is that the cipher stream can be generated in a separate box that is subject to strict security measures and fed to other devices, e.g. a radio set, which will perform the xor operation as part of their function. The latter device can then be designed and used in less stringent environments.
|A5/1||1989||Voice (Wphone)||54||114||64||Active KPA OR|
KPA Time-Memory Tradeoff
|~2 seconds OR|
|A5/2||1989||Voice (Wphone)||54||114||64?||Active||4.6 milliseconds|
|FISH||1993||Quite Fast (Wsoft)||Huge||Known-plaintext attack||211|
|ISAAC||1996||2.375 (W64-bit) -|
|PANAMA||1998||2||256||128?||1216?||Hash Collisions (2001)||282|
|Phelix||Pre-2004||up to 8 (Wx86)||256 + a 128-bit Nonce||128?||Differential (2006)||237|
|Pike||1994||0.9 x FISH (Wsoft)||Huge||N/A (2004)||N/A (2004)|
|64||8320||Cryptanalytic Theory (2006)||275|
|Rabbit||2003-Feb||3.7(WP3)-9.7(WARM7)||128||64||512||N/A (2006)||N/A (2006)|
|8||2064||Shamir Initial-Bytes Key-Derivation OR KPA||213 OR 233|
|Salsa20||Pre-2004||4.24 (WG4) -|
|128 + a 64-bit Nonce||512||512 + 384 (key+IV+index)||Differential (2005)||N/A (2005)|
|Scream||2002||4 - 5 (Wsoft)||128 + a 128-bit Nonce||32?||64-bit round function|
|SEAL||1997||Very Fast (W32-bit)||32?|
|SNOW||Pre-2003||Very Good (W32-bit)||128 OR 256||32|
|SOBER-128||2003||up to 128||Message Forge||2-6|
|SOSEMANUK||Pre-2004||Very Good (W32-bit)||128||128|
|Trivium||Pre-2004||4 (Wx86) - 8 (WLG)||80||80||288||Brute force attack (2006)||2135|
|VEST||2005||42 (WASIC) -|
|256 - 800||N/A (2006)||N/A (2006)|
|WAKE||1993||Fast||8192||CPA & CCA||Vulnerable|