Go back

Stream Ciphers

Topics

• Introduction
• Pseudorandom Bit Generators
• Linear Feddback Shift Registers
• A5/1
• RC4
• Salsa and ChaCha
• Streamciphers in Wireless Security

1. Introduction

Stream ciphers are symmetric encryption algorithms that encrypt data one bit or byte at a time using a keystream generated by a pseudorandom bit generator (PRBG). They are efficient and well-suited for high-speed or resource-constrained environments, but their security relies heavily on the properties of the keystream.

2. Pseudorandom Bit Generators (PRBGs)

Idea: as noted, the one-time pad is a perfect secracy (semantically secure against ciphertext-only attacks by an adversary with infinite computational resources. However, it needs a key as long as the message. So what if we generate a long key from a short key?
A PRBG expands a short, random seed into a long pseudorandom output called a keystream. This keystream is XORed with the plaintext in a manner similar to a one-time pad, but is generated deterministically.

Definition

A pseudorandom bit generator (PRBG) is a deterministic algorithm that takes as input a short random seed, and outputs a longer pseudorandom sequence, also known as a keystream

Key Properties:

• Indistinguishability: The output should appear random to any efficient adversary.
• Unpredictability: Given part of the keystream, it should be infeasible to compute unseen parts.
In order to achieve the properties above, a PRBG must have: (Discussing more on it in LFSR secion)
• Long Period: The sequence should not repeat within the ciphertext length.
• High Linear Complexity: The keystream should not be representable by a short recurrence relation. (Linear complexity stands for the degree of the smallest recurrence relation that could generate the sequence)
• Random noise-like characteristics: It is typically measured by statistical tests

Stream cipher

We can use a pseudorandom bit generator to construct a stream cipher.
The seed is the secret key shared by Alice and Bob.

Note that unlike the one-time pad, a stream cipher will not have perfect secrecy.
Instead, security depends on the quality of the PRBG.

Components of a PRBG

A pseudorandom bit generator consists of:

• Initialize(seed) → state:
A deterministic algorithm that takes as input a seed and outputs a state
• Update&Output(state) → (state', output):
A deterministic algorithm that takes as input a state and outputs an updates state and an output sequence a.k.a keystream.

Stream Cipher Architectures

One-Input PRBGs

Early stream ciphers used a single key as input. This meant one key produced one keystream, and reusing the key for multiple messages was insecure.

Two-Input PRBGs

Modern designs include an Initialization Vector (IV) alongside the key, allowing the same key to produce many different keystreams. The IV is public and transmitted with ciphertext.

Now the key is kept private, but the IV can be made public.
So, one can generate multiple (different) output sequences from the same key but different IV's.

3. Linear Feedback Shift Registers (LFSRs)

LFSRs are simple, fast hardware-friendly components used in many stream ciphers. They use a recurrence relation to generate sequences from an initial state vector.

Example recurrence: st+6 = st+5 ⊕ st+4 ⊕ st+1 ⊕ st

As such, any infinite periodic sequence (s_t) can be defined via a recurrence relation with a first few inital state vector (s₀, s₁, ..., s_n-1).

However, LFSRs have low linear complexity and are predictable, and hence a deterministic PRBG produces a periodic sequence.

Attack on small period: If the period of the keystream is less than the length of a ciphertext, then at least two secions of the message were encrypted using the same portion of the keystream. By XORing these two sections, the keystream cancels out and one obtains the XOR of the plaintext strings. It is then possible to attack such a sum by exploiting the redundancy of the plaintext.

Building a PRBG from a LFSR

A single LFSR on its own is not good.
Knowing the output leads to knowing the intermediate state so one can predict all future sequence.

Typically there are three ways of using LFSRs:

• Multiple outputs from the sequence can be sampled and passed through a non-linear filter.
• Multiple LFSRs can be advanced separately using an irregular clock.
• The outputs from multiple LFSRs can be passed through a non-linear combiner.(e.g. A5 cipher used in the GSM mobile phone standard)

4. A5/1

A stream cipher used in GSM mobile telephony. It combines three LFSRs irregularly clocked based on a majority rule.

• 64-bit key initializes three LFSRs of lengths 19, 22, and 23.
• Each LFSR is clocked only if its clocking bit agrees with the majority of all clocking bits.
• Final keystream bit is x18 ⊕ y21 ⊕ z22

Vulnerabilities: A5/1 was reverse-engineered and cracked with precomputation attacks using rainbow tables and GPU hardware.

5. RC4

Designed by Ron Rivest (1987). Widely adopted in SSL/TLS and WEP. Simple and fast but now deprecated.

Key Scheduling Algorithm:

• Initializes a 256-byte array S
• Scrambles it using the key

Keystream Generation:

• Updates two pointers i and j
• Swaps elements in S
• Uses the sum S[i]+S[j] as the keystream byte

Flaws: Biased outputs in early bytes, exploitable with millions of packets. RC4 is officially deprecated as of the 2010s.

6. Salsa20 and ChaCha

Modern stream ciphers by Daniel J. Bernstein. Salsa20 (2005), ChaCha (2008).

• Accepts 256-bit key, 64-bit nonce, 64-bit counter
• Uses a 4x4 matrix of 32-bit words as state
• Processes the state with 20 rounds (10 column and 10 row operations)

Characteristics: Fast in software, strong resistance to cryptanalysis, used in TLS, SSH, QUIC, IPsec

7. Wireless Security and WEP Case Study

WEP used RC4 with a 24-bit IV and a shared key. It aimed to provide confidentiality, integrity, and access control—but failed.

Key Flaws:

• IV Collisions: 24-bit space results in frequent collisions. Two messages with the same IV expose XOR of their plaintexts.
• Linear Integrity Check: Uses CRC-32, which is linear and allows forgery by adjusting checksums.
• Unkeyed Integrity: Known plaintext lets attackers derive keystream and forge valid packets.

FMS Attack:

The Fluhrer-Mantin-Shamir attack (2001) shows how key recovery is possible with 5 million packets. Used widely in tools like aircrack-ng.

Conclusion

Stream ciphers are efficient and powerful but require careful design and implementation. Legacy systems like WEP have shown that weak key handling and poor initialization can completely undermine security.

Modern alternatives like ChaCha20 and AES-CTR are recommended today.