# 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*.