Stream Cipher

What is Cryptography?

The cores of cryptography are:

• Secret key establishment
• Secure communication

Beyond the basic:

• Digital signature
• Anonymous communication
• Anonymous digital cash: OK to spend once, identify uncovered for double spending.
• Secure multi-party computation without trusted auth.
• Zero knowledge

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

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}$

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\}^n \to \{0, 1\}^s$ 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 .

Do not use glibc random for crypto!

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!

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.