 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Astream cipher is asymmetric keycipher where plaintext digits are combined with apseudorandom cipher digit stream (keystream). In a stream cipher, eachplaintextdigit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of theciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known asstate cipher. In practice, a digit is typically abit and the combining operation is anexclusive-or (XOR).
The pseudorandom keystream is typically generated serially from a randomseed value using digitalshift registers. Theseed value serves as thecryptographic key for decrypting the ciphertext stream. Stream ciphers represent a different approach to symmetric encryption fromblock ciphers. Block ciphers operate on large blocks of digits with a fixed, unvarying transformation. This distinction is not always clear-cut: in somemodes 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 security breaches (seestream cipher attacks); for example, when the same starting state (seed) is used twice.
Stream ciphers can be viewed as approximating the action of a proven unbreakable cipher, theone-time pad (OTP). A one-time pad uses akeystream of completelyrandom digits. The keystream is combined with the plaintext digits one at a time to form the ciphertext. This system was proven to be secure byClaude E. Shannon in 1949.[1] However, the keystream must be generated completely at random with at least the same length as the plaintext and cannot be used more than once. This makes the system cumbersome to implement in many practical applications, and as a result the one-time pad has not been widely used, except for the most critical applications. Key generation, distribution and management are critical for those applications.
A stream cipher makes use of a much smaller and more convenient key such as 128 bits. 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. The keystream is now pseudorandom and so is 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.[citation needed]
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 orciphertext messages, the cipher is classified as asynchronous stream cipher. By contrast,self-synchronising stream ciphers update their state based on previous plaintext or ciphertext digits. A system that incorporates the plaintext into the key is also known as anautokey cipher or autoclave cipher.
In asynchronous stream cipher a stream of pseudorandom 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 theexclusive or operation (XOR). This is termed abinary 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 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 toactive attacks: if an attacker can change a digit in the ciphertext, they 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.
Another approach uses several of the previousN ciphertext digits to compute the keystream. Such schemes are known asself-synchronizing stream ciphers,asynchronous stream ciphers orciphertext 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 receivingN 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 toN plaintext digits.
An example of a self-synchronising stream cipher is a block cipher incipher feedback (CFB)mode.
Binary stream ciphers are often constructed usinglinear-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-linearBoolean function to form acombination generator. Various properties of such acombining function are critical for ensuring the security of the resultant scheme, for example, in order to avoidcorrelation attacks.
![[icon]](/mt/?noimg=&dark=on&url=http%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aWiki_letter_w_cropped.svg) | This sectionneeds expansion. You can help byadding to it.(June 2008) |
Normally LFSRs are stepped regularly. One approach to introducing non-linearity is to have the LFSR clocked irregularly, controlled by the output of a second LFSR. Such generators include thestop-and-go generator, thealternating step generator and theshrinking generator.
Analternating step generator comprises three LFSRs, which we will call LFSR0, LFSR1 and LFSR2 for convenience. The output of one of the registers decides which of the other two is to be used; for instance, if LFSR2 outputs a 0, LFSR0 is clocked, and if it outputs a 1, LFSR1 is clocked instead. The output is the exclusive OR of the last bit produced by LFSR0 and LFSR1. The initial state of the three LFSRs is the key.
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.
Theshrinking 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.
Another approach to improving the security of an LFSR is to pass the entire state of a single LFSR into a non-linearfiltering function.
| This sectionneeds expansion. You can help byadding to it.(June 2008) |
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.
| This sectionneeds expansion. You can help byadding to it.(June 2008) |
For a stream cipher to be secure, its keystream must have a largeperiod, and it must be impossible torecover the cipher's key or internal state from the keystream. Cryptographers also demand that the keystream be free of even subtle biases that would let attackersdistinguish a stream from random noise, and free of detectable relationships between keystreams that correspond torelated keys or relatedcryptographic nonces. That should be true for all keys (there should be noweak keys), even if the attacker canknow orchoose someplaintext orciphertext.
As with other attacks in cryptography, stream cipher attacks can becertificational so they are not necessarily practical ways to break the cipher but indicate that the cipher might have other weaknesses.
Securely using a secure synchronous stream cipher requires that one never reuse the same keystream twice. That generally means a differentnonce or key must be supplied to each invocation of the cipher. Application designers must also recognize that most stream ciphers provide notauthenticity butprivacy: encrypted messages may still have been modified in transit.
Short periods for stream ciphers have been a practical concern. For example, 64-bit block ciphers likeDES can be used to generate a keystream inoutput feedback (OFB) mode. However, when not using full feedback, the resulting stream has a period of around 232 blocks on average; for many applications, the period is far too low. For example, if encryption is being performed at a rate of 8megabytes per second, a stream of period 232 blocks will repeat after about an hour.
Some applications using the stream cipherRC4 are attackable because of weaknesses in RC4's key setup routine; new applications should either avoid RC4 or make sure all keys are unique and ideallyunrelated (such as generated by a well-seededCSPRNG or acryptographic hash function) and that the first bytes of the keystream are discarded.
The elements of stream ciphers are often much simpler to understand than block ciphers and are thus less likely to hide any accidental or malicious weaknesses.
Stream ciphers are often used for their speed and simplicity of implementation in hardware, and in applications where plaintext comes in quantities of unknowable length like a securewireless connection. If ablock cipher (not operating in a stream cipher mode) were to be used in this type of application, the designer would need to choose either transmission efficiency or implementation complexity, since block ciphers cannot directly work on blocks shorter than their block size. For example, if a 128-bit block cipher received separate 32-bit bursts of plaintext, three quarters of the data transmitted would bepadding. Block ciphers must be used inciphertext stealing orresidual block termination mode to avoid padding, while stream ciphers eliminate this issue by naturally operating on the smallest unit that can be transmitted (usually bytes).
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 such as 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.
ChaCha is becoming the most widely used stream cipher in software;[2] others include:RC4,A5/1,A5/2,Chameleon,FISH,Helix,ISAAC,MUGI,Panama,Phelix,Pike,Salsa20,SEAL,SOBER,SOBER-128,andWAKE.
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2014) (Learn how and when to remove this message) |
| Stream cipher | Creation date | Speed (cycles per byte) | (bits) | Attack | |||
|---|---|---|---|---|---|---|---|
| Effective key-length | Initialization vector | Internal state | Best known | Computational complexity | |||
| A5/1 | 1989 | ? | 54 or 64 (in2G) | 22 (in 2G) | 64 | ActiveKPA OR KPA time–memory tradeoff | ~ 2 seconds OR 239.91 |
| A5/2 | 1989 | ? | 54 | 114 | 64? | Active | 4.6 milliseconds |
| Achterbahn-128/80 | 2006 | 1 (hardware) | 80/128 | 80/128 | 297/351 | Brute force for frame lengthsL ≤ 244.Correlation attack forL ≥ 248. | 280 resp. 2128 forL ≤ 244. |
| CryptMT | 2005 | ? | Variable | up to 19968 | 19968 | — (2008) | — (2008) |
| Crypto-1 | Pre-1994 | ? | 48 | 16 | 48 | Active KPA (2008) | 40 ms OR 248 (2008)[3] |
| E0 (cipher) | Pre-1999 | ? | Variable (usually 128) | 4 | 132 | KPA (2005) | 238 (2005)[4] |
| FISH | 1993 | ? | Variable | ? | ? | Known-plaintext attack | 211 |
| Grain | Pre-2004 | ? | 80 | 64 | 160 | Key derivation | 243 (2006)[5] |
| HC-256 | Pre-2004 | 4(WP4) | 256 | 256 | 65536 | ? | ? |
| ISAAC | 1996 | 2.375(W64-bit) – 4.6875(W32-bit) | 8–8288 (usually 40–256) | — | 8288 | (2006) First-round weak-internal-state-derivation | 4.67×101240 (2001) |
| MICKEY | Pre-2004 | ? | 80 | Variable (0 to 80) | 200 | Differential Fault Attack (2013) | 232.5 (2013)[6] |
| MUGI | 1998–2002 | ? | 128 | 128 | 1216 | — (2002) | ~ 282 |
| PANAMA | 1998 | 2 | 256 | 128? | 1216? | Hash collisions (2001) | 282 |
| Phelix | Pre-2004 | up to 8(Wx86) | 256 + a 128-bitnonce | 128? | ? | Differential (2006) | 237 |
| Pike | 1994 | ? | Variable | ? | ? | — (2004) | — (2004) |
| Py | Pre-2004 | 2.6 | 8–2048? (usually 40–256?) | 64 | 8320 | Cryptanalytic theory (2006) | 275 |
| Rabbit | 2003-Feb | 3.7(WP3) – 9.7(WARM7) | 128 | 64 | 512 | — (2006) | — (2006) |
| RC4 | 1987 | 7WP5[7] | 8–2048 (usually 40–256) | RC4 does not take an IV. If one desires an IV, it must be mixed into the key somehow. | 2064 | Shamir initial-byteskey-derivation ORKPA | 213 OR 233 |
| Salsa20 | Pre-2004 | 4.24(WG4) – 11.84(WP4) | 256 | a 64-bit nonce + a 64-bit stream position | 512 | Probabilistic neutral bits method | 2251 for 8 rounds (2007) |
| Scream | 2002 | 4–5(Wsoft) | 128 + a 128-bit nonce | 32? | 64-bit round function | ? | ? |
| SEAL | 1997 | ? | ? | 32? | ? | ? | ? |
| SNOW | Pre-2003 | ? | 128 or 256 | 32 | ? | ? | ? |
| SOBER-128 | 2003 | ? | up to 128 | ? | ? | Message forge (MAC portion) | 25 (2004)[8] |
| SOSEMANUK | Pre-2004 | ? | 128 | 128 | ? | ? | ? |
| Trivium | Pre-2004 | 4(Wx86) – 8(WLG) | 80 | 80 | 288 | Brute force attack (2006) | 2135 |
| Turing | 2000–2003 | 5.5(Wx86) | ? | 160 | ? | ? | ? |
| VEST | 2005 | 42(WASIC) – 64(WFPGA) | Variable (usually 80–256) | Variable (usually 80–256) | 256–800 | — (2006) | — (2006) |
| WAKE | 1993 | ? | ? | ? | 8192 | CPA &CCA | Vulnerable |
| Stream cipher | Creation date | Speed (cycles per byte) | (bits) | Attack | |||
| Effective key-length | Initialization vector | Internal state | Best known | Computational complexity | |||
{{cite book}}: CS1 maint: location missing publisher (link)