Stream Cipher

A symmetric cipher is defined over $(\mathcal{K, M, C})$: $\forall m \in \mathcal{M}, k \in \mathcal{K}: D(k, E(k, m)) = m$.

The Encryption E is always randomized, while D is deterministic.

The One Time Pad(OTP)

Vernam 1917

Information Theoretic Security

(Shannon 1949): Cipher text should reveal no “info” about Plain Text.

DEF: A cipher (E, D) over $(\mathcal{K, M, C})$ has perfect secrecy if $\forall m_0, m_1 \in \mathcal{M}, len(m_0) = len(m_1)$ and $\forall c \in \mathcal(C)$:

$P_r[E(k, m_0) = c] = P_r[E(k, m_1) = c]$

where k is unified distributed in $\mathcal{K}$ ($k \xleftarrow{\mathcal{R}} \mathcal{K}$)

Lemma: OTP has perfect secrecy if key length $\geq$ message length.

Pseudo Random Generator

We can use pseudo random generator, aka PRG: use a seed to generate the key to avoid sending the key with longer length than the message:

$G: \{0, 1\}^s \to \{0, 1\}^n$ and n $\gg$ s

The stream cipher use the pseudo random pad instead of OTP, it does NOT have perfect secrecy, but might be secure enough if PRG is unpredictable.

• The hacker can predict some part of the message, to get the key
• Then predict the key to cover the remaining text.

The PRG is predictable if the chance to predict the bit is larger than $\frac{1}{2} + \epsilon$. The $\epsilon$ determines how hard and how much data needs to be collected to launch the attack, — it should be polynomial .

Weak PRGs

glib random():

r[i] = (r[i-3] + r[i-31]) % 2^32
output r[i] >> 1

Attacks on Stream Cipher

Use OTP twice is dangerous:

• Project Venona (1941 - 1946)
• MS-PPTP

WEP uses 24bit IV concatenated with private k to encrypt the message:

• the key is rotated after 16M messages
• and the key is incremented by one for each key, and PRG(RC4) will generate the same pad for related keys. It only take 10^6 frames to detect k!

No integrity! The attacker can apply $\oplus$ on cipher text to mutate the plain text!

Real time stream ciphers:

• RC4, Used in HTTPS and WEP.
• CSS uesd linear feedback shift register(LFSR), easy for break about $2^{17}$ time.

PRG Security

Uses a statistical test, A and the $G:K \to \{0, 1\}^n$, the Advantage is defined as:

If Adv is close to 0, A and PRG are not distinguishable.

The PRG is secure if the existing efficient statistical test A, and Adv is negligible.

Thm(Yao’82)

Semantic Security

Use Shannon’s idea with relaxation, $m_0, m_1 \in \mathcal{M}$, and the two distributions are computation non-distinguishable.