Stream cipher attacks, malleability, and real constructions

Updated 06 Nov 2026

•
The Two-Time Pad attack
- •
  Attack mechanism
  - •
    when two plaintexts $m_1$ and $m_2$ are encrypted under the same keystream $k$ :
    
    •
    $c_1 = m_1 \oplus k, \quad c_2 = m_2 \oplus k$
  - •
    an eavesdropper intercepting $c_1$ and $c_2$ computes their bitwise XOR:
    
    •
    $c_1 \oplus c_2 = (m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2$
  - •
    the keystream $k$ cancels out entirely, leaving the raw XOR sum of both plaintexts exposed to cryptanalysis.
- •
  Plaintext recovery via ASCII heuristics
  - •
    Space character property -> ASCII space (hex 0x20, binary 00100000) XORed with an alphabetic letter flips its case:
    
    •
    $\text{' '} \oplus \text{'A'} = 0\text{x}20 \oplus 0\text{x}41 = 0\text{x}61 = \text{'a'}$
    •
    $\text{' '} \oplus \text{'a'} = 0\text{x}20 \oplus 0\text{x}61 = 0\text{x}41 = \text{'A'}$
  - •
    letter XOR letter produces characters in the range $0\text{x}00 \dots 0\text{x}1\text{F}$ .
- •
  Algorithmic recovery
  1. 1.
    inspect positions where $(c_1 \oplus c_2)[i] \ge 0\text{x}40$
  2. 2.
    at these positions, exactly one message contains a space character, and the other contains an alphabetic letter
  3. 3.
    frequency analysis and dictionary n-grams determine which stream holds the space, simultaneously recovering the plaintext character in both messages
- •
  Historic and protocol vulnerabilities
  - •
    Venona Project (1940s) -> Soviet intelligence accidentally duplicated one-time pad sheets, enabling US intelligence to decrypt thousands of diplomatic transmissions over decades
  - •
    Microsoft PPTP -> Point-to-Point Tunneling Protocol initialized separate client and server communication channels using the exact same RC4 key and direction counter, allowing eavesdroppers to XOR opposing traffic streams
  - •
    Disk encryption vulnerability -> stream ciphers should never be used for sector-level disk encryption: modifying a document and saving it re-encrypts the sector under the same key, revealing the exact diff ( $c_1 \oplus c_2 = m_{\text{old}} \oplus m_{\text{new}}$ )
- •
•
Malleability and lack of integrity
- •
  Definition
  - •
    a cipher is malleable if an attacker can intercept a ciphertext $c$ , apply a transformation to produce $c'$ , such that $c'$ decrypts to a predictable, related plaintext $m'$ , without the attacker ever knowing the secret key or the original plaintext
- •
  Bit-flipping attack on stream ciphers
  - •
    given ciphertext $c = m \oplus k$ , an active attacker crafts a perturbation patch $p \in \{0, 1\}^L$ and injects $c' := c \oplus p$
  - •
    decryption under key $k$ yields:
    
    •
    $D(k, c') = c' \oplus k = (c \oplus p) \oplus k = (m \oplus k \oplus p) \oplus k = m \oplus p$
  - •
    the attacker fullyh controls the resulting modification in the decrypted plaintext
- •
  Worked modification scenario
  - •
    intercepted encrypted email contains the header "From: Bob"
  - •
    attacker computes patch $p := \text{"Bob"} \oplus \text{"Eve"}$ and XORs $p$ into the ciphertext at the matching offset
  - •
    recipient decrypts "From: Eve"; decryption succeeds with zero cryptographic errors
- •
•
RC4 stream cipher and its cryptanalytic failure
- •
  Architecture (Ron Rivest 1987)
  - •
    software-oriented stream cipher operating on bytes with a 2048-bit internal state:
    
    •
    array $S[0..255]$ containing a permutation of bytes $0 \dots 255$
    
    •
    two 8-bit index pointers $i$ and $j$
  - •
    Key Scheduling Algorithm (KSA) -> initializes $S[i] = i$ , then scrambles the array based on key $k$ :
    
    •
    j = 0 for i in range(256): j = (j + S[i] + k[i % key_len]) % 256 S[i], S[j] = S[j], S[i]
  - •
    Pseudo-Random Generation Algorithm (PRGA) -> generates output stream byte-by-byte:
    
    •
    i = (i + 1) % 256 j = (j + S[i]) % 256 S[i], S[j] = S[j], S[i] output = S[(S[i] + S[j]) % 256]
- •
  Cryptanalytic biases
  - •
    Initial byte biases (Fluhrer-Mantin-Shamir / Roos) -> the 2nd output byte equals 0 with probability $2/256$ , twice the expected probability of $1/256$ . The 1st and 3rd bytes also exhibit significant non-uniformity
  - •
    Digram bias (Fluhrer-McGrew) -> the consecutive byte sequence 00 appears with probability $1/256^2 \cdot (1 + 1/256)$ , detectable after several gigabytes of stream output
  - •
    Related-key vulnerabilities (FMS attack) -> when keys share common prefixes (as in WEP's $IV \parallel k$ ), internal state correlation leaks key bytes directly from early keystream bytes
- •
  Current status -> banned by IETF for TLS (RFC 7465); completely deprecated for all modern cryptographic engineering
•
Linear Feedbck Shift Registers (LFSR)
- •
- •
  Mechanism
  - •
    hardware-optimized shift register consisting of $n$ memory cells $(u_t, \dots, u_{t+n-1})$ holding bits in $GF(2)$ .
  - •
    at each clock cycle $t$ :
    
    1.
    output the leftmost bit $u_t$
    
    2.
    shift register contents left by one cell
    
    3.
    compute feedback bit as the XOR sum of designated tap positions $T \subseteq \{0, \dots, n-1\}$ :
    
    •
    $u_{t+n} = \bigoplus_{j \in T} u_{t+j}$
    4.
    feed the resulting bit into the rightmost cell
- •
  Toy 3-bit worked example
  - •
    $n=3$ , tap set $T = \{0, 1\}$ , initial state $(1, 0, 0)$ .
  - •
    feedback bit: $1 \oplus 0 = 1$ . Next state: $(0, 0, 1)$ .
  - •
    sequence of states: $(1,0,0) \to (0,0,1) \to (0,1,0) \to (1,0,1) \to (0,1,1) \to (1,1,1) \to (1,1,0) \to (1,0,0)$ .
  - •
    maximal period is $2^n - 1 = 2^3 - 1 = 7$ . reading output bits produces stream: $1, 0, 0, 1, 0, 1, 1$ .
- •
  Cryptographic insecurity: The Berlekamp-Massey algorithm
  - •
    because the feedback relation is strictly linear in $GF(2)$ , any $n$ -stage LFSR has linear complexity at most $n$
  - •
    observing only $2n$ consecutive output bits allows the Berlekamp-Massey algorithm to recover the tap polynomial and full internal state in $O(n^2)$ time
  - •
    raw, unfiltered LFSRs provide zero cryptographic security
- •
  Non-linear filtering and combining
  - •
    deployed systems combine multiple LFSRs using non-linear boolean functions or irregular clocking:
    
    •
    GSM A5/1 and A5/2 (3 LFSRs with stop-and-go clocking). Broken in practice.
    
    •
    Bluetooth E0 (4 LFSRs with finite-state summation). Broken.
•
Content Scrambling System (CSS)
- •
  Achitecture
  - •
    proprietary stream cipher developed for DVD-Video copy protection (1996)
  - •
    built from two LFSRs:
    
    •
    LFSR-17 -> 17 bits long, initialized with 16 key bits and 1 fixed bit (bit 4 set to 1).
    
    •
    LFSR-25 -> 25 bits long, initialized with 24 key bits and 1 fixed bit (bit 4 set to 1).
  - •
    Effective key size -> $16 + 24 = 40$ bits (constrained by 1990s US export regulations).
  - •
    Keystream combination -> byte outputs from both LFSRs are added modulo 256 with the carry bit forwarded to the next cycle.
- •
  Cryptanalysis and complete collapse
  - •
    a 40-bit key space allows exhaustive brute-force search in $2^{40}$ operations.
  - •
    Stevenson attack (known-plaintext attack)
    
    •
    guess the 16 secret bits of LFSR-17 ( $2^{16} = 65,536$ possibilities)
    
    •
    run LFSR-17 to produce candidate output bytes
    
    •
    subtract candidate bytes from known MPEG packet header keystream bytes to deduce the required output of LFSR-25
    
    •
    check whether the deduced stream satisfies the linear recurrence of LFSR-25
    
    •
    fully recovers the complete 40-bit key in under 1 second on a personal computer
- •
  Cryptographic lesson -> proprietary algorithms and security through obscurity cannot compensate for short key lengths and linear algebraic structures.
•
Salsa20 modern stream cipher
- •
  Origin and standardization
  - •
    designed by Daniel J. Bernstein for the European eSTREAM project (concluded 2008; selected for the final software portfolio). Precursor to ChaCha20
- •
  Core architecture
  - •
    operates in counter mode on a $4 \times 4$ matrix of 32-bit words (64 bytes total):
    
    •
    4 constant words ("expand 32-byte k").
    
    •
    8 key words (256-bit key).
    
    •
    2 stream counter words (64-bit block position).
    
    •
    2 nonce words (64-bit nonce).
  - •
    ARX primitive -> uses only Addition modulo $2^{32}$ , bitwise Rotation, and XOR (a ^= (b + c) <<< d).
  - •
    eliminates data-dependent table lookups, rendering the implementation immune to cache-timing side-channel attacks.
  - •
    20 rounds -> 10 double-rounds alternating between column-rounds and row-rounds.
  - •
    Feed-forward addition -> final state is word-wise added to the initial state ( $x + h(x)$ ), preventing backward inversion of the permutation.
- •
  Performance and security
  - •
    throughput exceeds 600 MB/s on commodity x86 hardware.
  - •
    highly parallelizable: block $i$ can be computed independently without calculating preceding blocks (random access seek).
  - •
    fully secure against classical and quantum cryptanalysis, with zero known practical attacks.
- •

Linked references 1

cryptography-1-boneh

◌ Explore connections in Graph view

Stream cipher attacks, malleability, and real constructions

The Two-Time Pad attack

Malleability and lack of integrity

RC4 stream cipher and its cryptanalytic failure

Linear Feedbck Shift Registers (LFSR)

Content Scrambling System (CSS)

Salsa20 modern stream cipher

Linked references 1