Stream cipher

Last updated August 20, 2024

Astream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

The pseudorandom keystream is typically generated serially from a random seed value using digital shift registers. The seed value serves as the cryptographic key for decrypting the ciphertext stream. 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 security breaches (see stream cipher attacks); for example, when the same starting state (seed) is used twice.

Loose inspiration from the one-time pad

Stream ciphers can be viewed as approximating the action of a proven unbreakable cipher, the one-time pad (OTP). A one-time pad uses a keystream of completely random digits. The keystream is combined with the plaintext digits one at a time to form the ciphertext. This system was proven to be secure by Claude 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 ]}

Types

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 plaintext or ciphertext digits. A system that incorporates the plaintext into the key is also known as an autokey cipher or autoclave cipher.

Synchronous stream ciphers

In a synchronous 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 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 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, 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.

Self-synchronizing 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.

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

Based on linear-feedback shift registers

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.

Non-linear combining functions

One approach is to use n LFSRs in parallel, their outputs combined using an n-input binary Boolean function (F). Nonlinear-combo-generator.png — One approach is to use n LFSRs in parallel, their outputs combined using an n-input binary Boolean function (F).

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.

Clock-controlled generators

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 the stop-and-go generator, the alternating step generator and the shrinking generator.

An alternating 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.

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.

Filter generator

Another approach to improving the security of an LFSR is to pass the entire state of a single LFSR into a non-linear filtering function.

Other designs

RC4 is one of the most widely used stream cipher designs. RC4.svg — RC4 is one of the most widely used stream cipher designs.

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.

Security

For a stream cipher to be secure, its keystream must have a large period, and it must be impossible to recover 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 attackers distinguish a stream from random noise, and free of detectable relationships between keystreams that correspond to related keys or related cryptographic nonces. That should be true for all keys (there should be no weak keys ), even if the attacker can know or choose some plaintext or ciphertext.

As with other attacks in cryptography, stream cipher attacks can be certificational 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 different nonce or key must be supplied to each invocation of the cipher. Application designers must also recognize that most stream ciphers provide not authenticity but privacy: 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 like DES can be used to generate a keystream in output feedback (OFB) mode. However, when not using full feedback, the resulting stream has a period of around 2³² blocks on average; for many applications, the period is far too low. For example, if encryption is being performed at a rate of 8 megabytes per second, a stream of period 2³² blocks will repeat after about an hour.

Some applications using the stream cipher RC4 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 ideally unrelated (such as generated by a well-seeded CSPRNG or a cryptographic 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.

Usage

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 secure wireless connection. If a block 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 be padding. Block ciphers must be used in ciphertext stealing or residual 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, and WAKE.

Comparison

Stream cipher	Creation date	Speed (cycles per byte)	(bits)			Attack
Stream cipher	Creation date	Speed (cycles per byte)	Effective key- length	Initialization vector	Internal state	Best known	Computational complexity
A5/1	1989	?	54 or 64 (in 2G)	22 (in 2G)	64	Active KPA OR KPA time–memory tradeoff	~ 2 seconds OR 2^39.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 lengths L ≤ 2⁴⁴. Correlation attack for L ≥ 2⁴⁸.	2⁸⁰ resp. 2¹²⁸ for L ≤ 2⁴⁴.
CryptMT	2005	?	Variable	up to 19968	19968	— (2008)	— (2008)
Crypto-1	Pre-1994	?	48	16	48	Active KPA (2008)	40 ms OR 2⁴⁸ (2008)^[3]
E0 (cipher)	Pre-1999	?	Variable (usually 128)	4	132	KPA (2005)	2³⁸ (2005)^[4]
FISH	1993	?	Variable	?	?	Known-plaintext attack	2¹¹
Grain	Pre-2004	?	80	64	160	Key derivation	2⁴³
HC-256	Pre-2004	4 (W_P4)	256	256	65536	?	?
ISAAC	1996	2.375 (W_64-bit) – 4.6875 (W_32-bit)	8–8288 (usually 40–256)	—	8288	(2006) First-round weak-internal-state-derivation	4.67×10¹²⁴⁰ (2001)
MICKEY	Pre-2004	?	80	Variable (0 to 80)	200	Differential Fault Attack (2013)	2^32.5 (2013)^[5]
MUGI	1998–2002	?	128	128	1216	— (2002)	~ 2⁸²
PANAMA	1998	2	256	128?	1216?	Hash collisions (2001)	2⁸²
Phelix	Pre-2004	up to 8 (W_x86)	256 + a 128-bit nonce	128?	?	Differential (2006)	2³⁷
Pike	1994	?	Variable	?	?	— (2004)	— (2004)
Py	Pre-2004	2.6	8–2048? (usually 40–256?)	64	8320	Cryptanalytic theory (2006)	2⁷⁵
Rabbit	2003-Feb	3.7(W_P3) – 9.7(W_ARM7)	128	64	512	— (2006)	— (2006)
RC4	1987	7 W_P5 ^[6]	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-bytes key-derivation OR KPA	2¹³ OR 2³³
Salsa20	Pre-2004	4.24 (W_G4) – 11.84 (W_P4)	256	a 64-bit nonce + a 64-bit stream position	512	Probabilistic neutral bits method	2²⁵¹ for 8 rounds (2007)
Scream	2002	4–5 (W_soft)	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	2⁻⁶
SOSEMANUK	Pre-2004	?	128	128	?	?	?
Trivium	Pre-2004	4 (W_x86) – 8 (W_LG)	80	80	288	Brute force attack (2006)	2¹³⁵
Turing	2000–2003	5.5 (W_x86)	?	160	?	?	?
VEST	2005	42 (W_ASIC) – 64 (W_FPGA)	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
Stream cipher	Creation date	Speed (cycles per byte)	Effective key- length	Initialization vector	Internal state	Best known	Computational complexity

Trivia

United States National Security Agency 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.

Notes

↑ Deane, Arthur; Kraus, Aaron (2021). "Chapter 3: Domain 3: Security Architecture and Engineering". The Official (ISC)2 CISSP CBK Reference (6th ed.). Hoboken, New Jersey: John Wiley & Sons, Inc. p. 232. ISBN 978-1-119-78999-4.
↑ "Do the ChaCha: Better mobile performance with cryptography". 23 February 2015.
↑ Garcia, Flavio D.; de Koning Gans, Gerhard; Muijrers, Ruben; van Rossum, Peter; Verdult, Roel; Schreur, Ronny Wichers; Jacobs, Bart (4 October 2008). "Dismantling MIFARE Classic" (PDF). 13th European Symposium on Research in Computer Security (ESORICS 2008), LNCS, Springer. Archived from the original (PDF) on 23 February 2021. Retrieved 25 June 2022.
↑ Lu, Yi; Meier, Willi; Vaudenay, Serge (2005). "The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption". Advances in Cryptology – CRYPTO 2005 (PDF). Lecture Notes in Computer Science. Vol. 3621. Santa Barbara, California, USA. pp. 97–117. CiteSeerX 10.1.1.323.9416 . doi:10.1007/11535218_7. ISBN 978-3-540-28114-6.{{cite book}}: |journal= ignored (help)CS1 maint: location missing publisher (link)
↑ Banik, Subhadeep; Maitra, Subhamoy; Sarkar, Santanu (2013). "A Differential Fault Attack on MICKEY 2.0". Cryptology ePrint Archive.
↑ P. Prasithsangaree and P. Krishnamurthy (2003). "Analysis of Energy Consumption of RC4 and AES Algorithms in Wireless LANs" (PDF). IEEE Globecom. Archived from the original (PDF) on 2013-12-03.

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Cryptanalysis</span> Study of analyzing information systems in order to discover their hidden aspects

Cryptanalysis refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

<span class="mw-page-title-main">Block cipher mode of operation</span> Cryptography algorithm

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

Articles related to cryptography include:

In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream. The earliest description of such a cipher was given in 1892 by French mathematician Arthur Joseph Hermann. Usually, the book to be used would be agreed ahead of time, while the passage to be used would be chosen randomly for each message and secretly indicated somewhere in the message.

In cryptography, confusion and diffusion are two properties of a secure cipher identified by Claude Shannon in his 1945 classified report A Mathematical Theory of Cryptography. These properties, when present, work together to thwart the application of statistics, and other methods of cryptanalysis.

Gilbert Sandford Vernam was a Worcester Polytechnic Institute 1914 graduate and AT&T Bell Labs engineer who, in 1917, invented an additive polyalphabetic stream cipher and later co-invented an automated one-time pad cipher. Vernam proposed a teleprinter cipher in which a previously prepared key, kept on paper tape, is combined character by character with the plaintext message to produce the ciphertext. To decipher the ciphertext, the same key would be again combined character by character, producing the plaintext. Vernam later worked for the Postal Telegraph Company, and became an employee of Western Union when that company acquired Postal in 1943. His later work was largely with automatic switching systems for telegraph networks.

In cryptography, WAKE is a stream cipher designed by David Wheeler in 1993.

VEST (Very Efficient Substitution Transposition) ciphers are a set of families of general-purpose hardware-dedicated ciphers that support single pass authenticated encryption and can operate as collision-resistant hash functions designed by Sean O'Neil, Benjamin Gittins and Howard Landman. VEST cannot be implemented efficiently in software.

Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommend a maximum length of output per pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.

In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message.

In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. Modern symmetric-key ciphers are specifically designed to be immune to such an attack. In other words, modern encryption schemes are pseudorandom permutations and are designed to have ciphertext indistinguishability. If an algorithm is found that can distinguish the output from random faster than a brute force search, then that is considered a break of the cipher.

In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator used in stream ciphers, based on three linear-feedback shift registers. Its output is a combination of two LFSRs which are stepped (clocked) in an alternating fashion, depending on the output of a third LFSR.

<span class="mw-page-title-main">Crypto-1</span> Stream cipher

Crypto1 is a proprietary encryption algorithm and authentication protocol created by NXP Semiconductors for its MIFARE Classic RFID contactless smart cards launched in 1994. Such cards have been used in many notable systems, including Oyster card, CharlieCard and OV-chipkaart.

Correlation attacks are a class of cryptographic known-plaintext attacks for breaking stream ciphers whose keystreams are generated by combining the output of several linear-feedback shift registers (LFSRs) using a Boolean function. Correlation attacks exploit a statistical weakness that arises from the specific Boolean function chosen for the keystream. While some Boolean functions are vulnerable to correlation attacks, stream ciphers generated using such functions are not inherently insecure.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

References

Matt J. B. Robshaw, Stream Ciphers Technical Report TR-701, version 2.0, RSA Laboratories, 1995 (PDF).
Beth, Thomas; Piper, Fred (1985). The Stop and Go Generator (PDF). EUROCRYPT '84. pp. 88–92. doi: 10.1007/3-540-39757-4_9 . Archived (PDF) from the original on 2019-03-29.
Christof Paar, Jan Pelzl, "Stream Ciphers", Chapter 2 of "Understanding Cryptography, A Textbook for Students and Practitioners". (companion web site contains online cryptography course that covers stream ciphers and LFSR), Springer, 2009.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Deane, Arthur; Kraus, Aaron (2021). "Chapter 3: Domain 3: Security Architecture and Engineering". The Official (ISC)2 CISSP CBK Reference (6th ed.). Hoboken, New Jersey: John Wiley & Sons, Inc. p. 232. ISBN 978-1-119-78999-4.

[2] "Do the ChaCha: Better mobile performance with cryptography". 23 February 2015.

[3] Garcia, Flavio D.; de Koning Gans, Gerhard; Muijrers, Ruben; van Rossum, Peter; Verdult, Roel; Schreur, Ronny Wichers; Jacobs, Bart (4 October 2008). "Dismantling MIFARE Classic" (PDF). 13th European Symposium on Research in Computer Security (ESORICS 2008), LNCS, Springer. Archived from the original (PDF) on 23 February 2021. Retrieved 25 June 2022.

[4] Lu, Yi; Meier, Willi; Vaudenay, Serge (2005). "The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption". Advances in Cryptology – CRYPTO 2005 (PDF). Lecture Notes in Computer Science. Vol. 3621. Santa Barbara, California, USA. pp. 97–117. CiteSeerX 10.1.1.323.9416 . doi:10.1007/11535218_7. ISBN 978-3-540-28114-6.{{cite book}}: |journal= ignored (help)CS1 maint: location missing publisher (link)

[5] Banik, Subhadeep; Maitra, Subhamoy; Sarkar, Santanu (2013). "A Differential Fault Attack on MICKEY 2.0". Cryptology ePrint Archive.

[6] P. Prasithsangaree and P. Krishnamurthy (2003). "Analysis of Energy Consumption of RC4 and AES Algorithms in Wireless LANs" (PDF). IEEE Globecom. Archived from the original (PDF) on 2013-12-03.

[1]

[2]

[3]

[4]

[5]

[6]