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 (K,M,C)(\mathcal{K, M, C}): ∀m∈M,k∈K:D(k,E(k,m))=m\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

c=E(k,m)=k⊕m∴D(k,c)=k⊕c\begin{align} c =E(k, m) = k \oplus m \\ \therefore D(k, c) = k\oplus c \end{align}

Information Theoretic Security

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

DEF: A cipher (E, D) over (K,M,C)(\mathcal{K, M, C}) has perfect secrecy if ∀m0,m1∈M,len(m0)=len(m1)\forall m_0, m_1 \in \mathcal{M}, len(m_0) = len(m_1) and ∀c∈(C)Pr[E(k,m0)=c]=Pr[E(k,m1)=c]\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 K\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→{0,1}sG: \{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 12+ϵ\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→{0,1}nG:K \to \{0, 1\}^n, the Advantage is defined as:

AdvPRG[A,G]=∣Pr[A(G(k)=1)]−Pr[A(r)=1]∣∈[0,1] Adv_{PRG}[A, G] = | Pr[A(G(k)=1)] - Pr[A(r)=1] | \in [0, 1]

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, m0,m1∈Mm_0, m_1 \in \mathcal{M}, and the two distributions are computation non-distinguishable.