Stream Ciphers

Models plaintext as a bit stream, combined with a random keystream via a reversible operation, bitwise XOR.

Both encryption and decryption must generate the identical keystream $k_i$.

• No error propagation
  A bit error in a transmitted ciphertext bit corrupts only the corresponding decrypted plaintext bit.
• Efficient for real-time data (audio, video streaming) when the keystream generation algorithm is fast.

Key Space

The key space is determined by the keystream generator, not by the message length. A generator with a uniformly selected $b$-bit secret key has $2^b$ candidate keys. The initialization vector is public and does not enlarge this space.

For a one-time pad protecting an $n$-bit message, the key is an independently random $n$-bit string. Its key space has $2^n$ members. Each key may encrypt only 1 message.

Stream Encryption Scheme

A stream cipher is already a complete encryption scheme. It needs no mode of operation.

• Arbitrary length
  The keystream is generated to any length and XORed with the plaintext bit by bit. No padding, and ciphertext length equals plaintext length.
• Randomisation
  The keystream generator takes an initialization vector alongside the key, so the same plaintext under the same key gives different ciphertext for different IVs.

Keystream Generator

A function that generates a stream of pseudorandom bits $k_0, k_1, k_2, \dots$ from a short secret key. Used in practical stream ciphers.

A secure keystream generator must satisfy:

• Long period
  The period $N$ of the repetition of the sequence, where $k_i = k_{i+N}$, must be large for all $i$.
• Pseudo-randomness
  The sequence must pass statistical random number tests.
• Unpredictability
  Computationally infeasible to determine the full keystream from any part of it, of any length.

Malleability

An encryption scheme is malleable iff an attacker can transform a ciphertext of an unknown message $m$ into a ciphertext of a related message $f(m)$, without knowing $m$ or the key.

The XOR-combiner stream cipher is malleable. Given $c = m \oplus k$, the attacker chooses a mask $\Delta$ and sends $c' = c \oplus \Delta$.

The plaintext changes by exactly $\Delta$, an attacker-chosen relation, with no other change. Flipping bit $i$ of $c$ flips bit $i$ of the plaintext.

Malleability here follows from 2 properties together, not from the keystream being random or pseudorandom.

• The combiner is XOR, which is linear and known to the attacker.
• No integrity check covers the ciphertext.

Removing either property breaks the attack. A self-synchronising stream cipher feeds past ciphertext bits into the keystream, so a flipped bit garbles a run of following plaintext instead of one clean bit.

A scheme is non-malleable iff any tampering with the ciphertext makes it decrypt to a value unrelated to $m$, or makes decryption reject.

Breaking the Cipher

Reusing a keystream $k$ across 2 messages $m_1$ and $m_2$ produces ciphertexts $c_1 = m_1 \oplus k$ and $c_2 = m_2 \oplus k$.

The keystream cancels. An attacker holding $c_1$ and $c_2$ recovers $m_1 \oplus m_2$ without $k$. Plaintext redundancy separates it into $m_1$ and $m_2$. Knowing one plaintext gives the other directly.

Knowing one plaintext also recovers the keystream, $k = c_1 \oplus m_1$. Any further message under the same $k$ can then be forged. The attacker picks $m'$ and sends $c' = m' \oplus k$, which decrypts to $m'$, an existential forgery.

Examples

One-Time Pad

To encrypt a message $m$ (of length $n$), a keystream $k$ (of length $n$) is generated that is random and never reused. The message bits are XORed with the keystream bits to produce the ciphertext.

Impractical as it requires a key as long as the message and never reused, but applications need a short key and reuse it across many messages.