流密码（Stream ciphers）

1. Pseudo-random generators

Stream Ciphers: making OTP practical

idea: replace “random” key by “pseudorandom” key

The string s is stretched using some efficient, deterministic algorithm G that maps ‘l-bit strings to L-bit strings. Thus, the key space for this modified one-time pad is $\{0,1\}^l$ , while the message and ciphertext spaces are $\{0,1\}^L$

For $s ∈ \{0,1\}^l$ and m, $c ∈ \{0,1\}^L$ , encryption and decryption are defined as follows:

$E(s, m) := G(s) ⊕ m$ and $D(s, c) := G(s) ⊕ c$ .

This modified one-time pad is called a stream cipher, and the function G is called a pseudorandom generator.

If $l < L$ , then by Shannon’s Theorem, this stream cipher cannot achieve perfect security;

however, if G satisfies an appropriate security property, then this cipher is semantically secure.

PRG must be unpredictable

PRG is unpredictable if it is not predictable

⇒ ∀i: no “eff” adv. can predict bit (i+1) for “non-neg” ε

2. Negligible vs. non-negligible

In practice: ε is a scalar and

– ε non-neg: $ε ≥ 1/2^{30}$ (likely to happen over 1GB of data)

– ε negligible: $ε ≤ 1/2^{80}$ (won’t happen over life of key)

In theory: ε is a function $ε: Z^{≥0} ⟶ R^{≥0}$ and

– ε non-neg: $∃d: ε(λ) ≥ 1/λ^d$ (ε ≥ 1/poly, for many λ)

– ε negligible: $∀d, λ≥λ_d : ε(λ) ≤ 1/λ^d$ (ε ≤ 1/poly, for large λ)

PRGs: the rigorous theory view

PRGs are “parameterized” by a security parameter λ

PRG becomes “more secure” as λ increases

Seed lengths and output lengths grow with λ

For every λ=1,2,3,… there is a different PRG Gλ :

Gλ : $K_λ ⟶ \{0,1\}^{n(λ)}$

(in the lectures we will always ignore λ )

3. Attacks on OTP and stream ciphers

Attack 1: two time pad is insecure !!

Never use stream cipher key more than once !!

$C_1 \leftarrow m_1 ⊕ PRG(k)$

$C_2 \leftarrow m_2 ⊕ PRG(k)$

$C_1 ⊕ C_2 \rightarrow m_1⊕ m_2$

Enough redundancy in English and ASCII encoding that:

$m_1⊕ m_2 \rightarrow m_1, m_2$

Real world examples

Project Venona
MS-PPTP (windows NT)
802.11b WEP

Attack 2: no integrity (OTP is malleable)

Modifications to ciphertext are undetected and have predictable impact on plaintext

enc: $m ⊕ k$

$(m ⊕ k) ⊕ p$

dec: $((m ⊕ k) ⊕ p )⊕ k \rightarrow m⊕p$

4. Real-world Stream Ciphers

Old example (software): RC4 (1987)

Weaknesses:

Bias in initial output: $Pr[ 2^{nd}\ byte = 0 ] = 2/256$
Prob. of (0,0) is $1/256^2 + 1/256$
Related key attacks

Old example (hardware): CSS (badly broken)

Linear feedback shift register (LFSR):

DVD encryption (CSS): 2 LFSRs
GSM encryption (A5/1,2): 3 LFSRs
Bluetooth (E0): 4 LFSRs

all broken

CSS: seed = 5 bytes = 40 bits

加密DVD电影，混淆系统CSS，面向硬件设计的流密码，基于线性反馈移位寄存器LFSR。右移，最后一位扔掉，第一位是之前的异或结果。 LFSR的种子就是寄存器的初始状态。

CSS用了两个LFSR，一个17位一个25位。

种子是，第一个的是1+key的前两个字节=17bits; 第二个是1+key的后三个字节=25bits

两个LFSR运行8次，输出8位，相加，mod256，一轮输出一个字节。这个字节和电影数据里的字节进行异或加密，CSS是个简单的流密码。2^17次可以破解。很容易。

Modern stream ciphers: eStream

PRG: $\{0,1\}^s × R ⟶ \{0,1\}^n$

seed × nonce

Nonce: a non-repeating value for a given key.

E(k, m ; r) = m ⊕ PRG(k ; r)

The pair (k, r) is never used more than once.

eStream: Salsa 20

Salsa20: $\{0,1\}^{128\ or\ 256} × \{0,1\}^{64} ⟶ \{0,1\}^n$

Salsa20( k ; r) := H( k , (r, 0)) ll H( k , (r, 1)) ll …

5. PRG Security Defs

如果无法区分G(s) 和 r，就说明G(s)是安全的，流密码也是安全的

Intuitively, if an adversary cannot effectively tell the difference between G(s) and r, then he should not be able to tell the difference between this stream cipher and a one-time pad; moreover, since the latter cipher is semantically secure, so should be the former.

Statistical Tests

一种用于区分伪随机串和真正随机串的算法被称为统计测试。它以一个字符串作为输入，输出0或1。如果在伪随机输入上输出1的概率与在真正随机输入上输出1的概率显著不同，则这种测试称为有效

An algorithm that is used to distinguish a pseudo-random string G(s) from a truly random string r is called a statistical test. It takes a string as input, and outputs 0 or 1. Such a test is called effective if the probability that it outputs 1 on a pseudo-random input is significantly different than the probability that it outputs 1 on a truly random input.

Advantage

Given r, the adversary computes and outputs a bit b ∈ {0,1}.

For b = 0,1, let $W_b$ be the event that A outputs 1 in Experiment b.

We define A’s advantage with respect to G as

$PRGadv[A, G] := |Pr[W_0] − Pr[W_1] |$

Secure PRGs: crypto definition

Def: We say that $G:K ⟶\{0,1\}^n$ is a secure PRG if

PRGadv[A, G] is negligible for all efficient adversaries A.

Easy fact: a secure PRG is unpredictable

We show: PRG predictable ⇒ PRG is insecure

Thm (Yao’82): an unpredictable PRG is secure

Let $G:K ⟶\{0,1\}^n$ be PRG

“Thm”: if ∀ i ∈ ,0, … , n-1} PRG G is unpredictable at pos. i

then G is a secure PRG.

If next-bit predictors cannot distinguish G from random then no statistical test can !!

6. Semantic security

What is a secure cipher?

Attacker’s abilities: obtains one ciphertext (for now)

Possible security requirements:

attempt #1: attacker cannot recover secret key
attempt #2: attacker cannot recover all of plaintext
Recall Shannon’s idea: CT should reveal no “info” about PT

Semantic Security (one-time key)

攻击者A发出等长的m0和m1，挑战者选取随机密钥k发出m0或m1的加密结果。

在实验0里，挑战者输出m0的加密

在实验1里，挑战者输出m1的加密

攻击者视图试图去猜他得到的是m0还是m1的加密

定义事件Wb为在实验b中攻击者输出1的所有事件

接下来，这就是攻击者A对加密机制E的语义安全的优势

定义两个事件概率的差距

Adv趋近于1，意味着攻击者能很好地区分实验0和1，也就是可以区分M0和M1的加密。

Adv趋近于0，意味着攻击者不能区分实验0和1

E是一个对称加密机制，是语义安全的。对所有有效的攻击者(破解成功)，优势可以忽略(Adv~0)。

总的来说，就是攻击者获得m0和m1，无法区分这两个分布。

2. 密码学笔记-流密码（Stream ciphers）