# 「Cryptography-Boneh」:Stream Cipher 1

Stream Cipher部分中，本文主要阐述了什么是PRG？Stream Cipher的另一种安全的定义（依靠PRG的unpredictable)。

## Symmetric Ciphers: difinition

Def :a cipher difined over $\mathcal{(K,M,C)}$ is a pair of “efiicient “ algorithms $(E,D)$ where

$$E :\mathcal{K \times M \longrightarrow \mathcal{C}} \quad ,\quad D:\mathcal{K\times\mathcal{C}\longrightarrow\mathcal{M}} \\ s.t. \quad \forall m\in \mathcal{M},k\in \mathcal{K}:D(k,E(k,m))=m$$

$\mathcal{(K,M,C)}$ 分别是密钥空间、明文空间、密文空间。

1. $E$ is ofen randomized. 即加密算法E总是随机生成一些bits，用来加密明文。

2. $D$ is always deterministic. 即当确定密钥和明文时，解密算法的输出总是唯一的。

3. “efficient” 的含义

• 对于理论派：efficient表示 in polynomial time（多项式时间）
• 对于实践派：efficient表示 in a certain time

### Definition of OTP

• $\mathcal{M=C=}{0,1}^n\quad \mathcal{K}={0,1}^n$
• $E：\quad c = E(k,m)=k\oplus m \quad$
• $D:\quad m = D(k,c)=k\oplus c$

• 证明其一致性方程

Indeed

$D(k,E(k,m))=D(k,k\oplus m)=k\oplus (k\oplus m)=0\oplus m=m$

：当然，根据异或的性质，key $k=m\oplus c$

### Information Theoretic Security

#### Perfect Security Def:

A cipher $(E,D)$ over $\mathcal{(K,M,C)}$ has perfect security if $\forall m_0,m_1 \in \mathcal{M}\ (|m_0|=|m_1|) \quad \text{and} \quad \forall c\in \mathcal{C}$
$$Pr[E(k,m_0)=c]=Pr[E(k,m_1)=c] \qquad \text{where} \ k\overset{R}{\longleftarrow}\mathcal{K}$$

$k \overset{R}\longleftarrow \mathcal{K}$ 的意思是 $k$ 是 从$\mathcal{K}$ 中随机取的，即随机变量 $k$ 的取值是均匀分布。

#### 对attacker来说 ：

• $\Rightarrow$ Given CT can’t tell if msg is $m_0 \ \text{or}\ m_1$ (for all $m_i$ ) .

【攻击者不能区分明文到底是 $m_?$ 】

• $\Rightarrow$ most powerful adv.(adversary) learns nothing about PT from CT.

【不管攻击者多聪明，都不能从密文中得到密文的信息】

• $\Rightarrow$ no CT only attack!! (but other attackers possible).

【唯密文攻击对OTP无效】

### OTP has perfect secrecy

Lemma : OTP has perfect secrecy.

Proof

1. 要证明： $Pr[E(k,m_0)=c]=Pr[E(k,m_1)=c] \qquad \text{where} \ k\overset{R}{\longleftarrow}\mathcal{K}$

2. 表达式： $\forall m, c: \quad \operatorname{Pr}_{k}[E(k,m)=c]=\frac{\# \text{keys} \ k \in \mathcal{K} \quad s.t.\; E(k,m)=c}{|\mathcal{K}|}$

对于任意m,c, $\operatorname{Pr}_{k}[E(k,m)=c]$ 等于能将m加密为c的密钥个数除以密钥空间的大小。

3. $\because |\mathcal{K}|$ 是相同的，所以即证 ： $\{ \# \text{keys} \ k \in \mathcal{K} \quad s.t.\; E(k,m)=c \}=\text{const}$
4. 对于任意 m,c，能将m加密为c的OTP key只有一个： $k=m\oplus c$

5. $\therefore$ OTP has perfect secrecy.

### key-len $\geq$ msg-len

Thm: perfect secrecy $\Rightarrow$ $|\mathcal{K}|\geq|\mathcal{M}|$

# Pseudorandom Generators（伪随机数生成器）

## Stream Ciphers: making OTP practical

Stream Ciphers（流密码）的思想就是：用PRG（pseudorandom Generators） key 代替 “random” key。

PRG其实就是一个function G：${ 0,1 }^s\longrightarrow { 0,1 }^n \quad, n>>s$ 。

• 函数G是确定的，随机的只有s，s也是G的输入。
• PRG的输出应该是 “look random”（下文会提到的PRG必须是unpredictable）

Stream Ciphers的过程如上图所示：通过PRG，将长度较短的k映射为足够长的G(k)，G(k)异或m得到密文。

：流密码没有perfect secrecy。因为它不满足key-len $\geq$ msg-len，流密码的密钥长度远小于明文长度。

## PRG must be unpredictable

PRG如果predictable，流密码安全吗？

### Suppose predictable

$\exists:\quad G(k)|_{1,2,...,i}\quad \overset{alg.}\longrightarrow \quad G(k)|_{i+1,...,n}$

1. 如果attacker has prior knowledge：已知一段密文前缀的对应明文（m斜线字段）（比如在SMTP协议中，报文的开头总是”from”）

2. attacker将该密文字段与已知明文字段异或，得到G(k)的前缀。

3. 因为PRG是可预测的，所以可以通过G(k)的前缀计算出G(k)的剩下部分。

4. 得到的G(K)就可以恢复m。

### Predictable: difinition

Predictable Def :

$\exists$ "eff" alg. A and $\exists$ $0\leq i\leq n-1$ ， s.t. $Pr_{k \overset{R}\leftarrow \mathcal{K} } {[A(G(k)|_{1,2,...,i})=G(k)|_{i+1}]}>1/2 +\epsilon$

for non-negligible $\epsilon$ (e.g. $\epsilon=1/2^{30}$)

Unpredictable Def :

Q：假设 $\mathrm{G}: \mathrm{K} \rightarrow{0,1}^{\mathrm{n}}$ ，满足XOR(G(k))=1，G可预测吗？

W：G可预测，存在i = n-1,因为当已知前n-1位,可以预测第n位。

## Weak PRGs

### Basic LCG

#### Definition

Basic LCG has four public system parameters:

an integer q, two constants a,b $\in { 0,…,q-1}$ , and a positive integer $w\leq q$ .

The constant a is taken to be relatively prime to q.

【有四个公开参数：整数q，两个q剩余系下的常数a,b，（a与q互素）和一个小于等于q的正整数w。】

We use $\mathcal{S}_q$ and $\mathcal{R}$ to denote the sets: $\mathcal{S}_{q}:=\{0, \ldots, q-1\} ; \quad \mathcal{R}:=\{0, \ldots,\lfloor(q-1) / w\rfloor\}$ Now, the generators $G_{\mathrm{lcg}}: \mathcal{S}_{q} \rightarrow \mathcal{R} \times \mathcal{S}_{q}$ with seed $s\in\mathcal{S}_{q}$ defined as follows: $G_{\operatorname{lcg}}(s):=(\lfloor s / w\rfloor, \quad a s+b \bmod q)$

【LCG的输出是一对数，$(\lfloor s / w\rfloor, \quad a s+b \bmod q)$ 】

### Variant: Blum-Micali construction

#### how to attack in JDKv8

1. 在迭代的第一次输出中，LCG就 reveal 26bits of the seed s。

2. 对于s剩下的后22个bits，attacker can easily recover them by exhausitive search(穷举)：

3. 对于每个可能的取值，attacker都能得到一个候选seed $\hat{s}$

4. 用 $\hat{s}$ 来验证我们所直接得到的LCG的输出。

5. 如果 $\hat{s}$ 验证失败，则到第三步继续穷举。直至验证成功。

6. 当穷举至正确的s时，就可以直接预测LCG的剩余输出。

### Cryptanalysis ：elegant attack

#### Suppose

Suppose : q is large (e.g. $q=2^{512}$ ), and $G_{lcg}^{(n)}$ outputs about half the bits of the state s per iteration.

【q很大， $G_{lcg}^{(n)}$ 每次输出s的一半左右的bits】

More precisely, suppose: $w<\sqrt{q}/c$ for fixed c（e.g. $c=32$ ）

【保证输出s前一半左右bits的这个条件】

Suppose the attacker is given two consecutive outputs of the gnerator $r_i,r_{i+1}\in \mathcal{R}$ .

【已知两个连续输出 $r_i,r_{i+1}\in \mathcal{R}$ 】

#### Attacker Knows

1. $r_{i}=\left\lfloor s_{i} / w\right\rfloor \quad \text { and } \quad r_{i+1}=\left\lfloor s_{i+1} / w\right\rfloor=\left\lfloor\left(a s_{i}+b \bmod q\right) / w\right\rfloor$

【已知： $r_i,r_{i+1},w,a,b,q$；未知： $s_i$ 】

2. $r_{i} \cdot w+e_{0}=s \quad \text { and } \quad r_{i+1} \cdot w+e_{1}=a s+b+q x \qquad (0\leq e_0,e_1<w<\sqrt{q}/c)$

【 去掉floor符号和mod：$e_0,e_1$ 是 $s_i,s_{i+1}$ 除 $w$ 的余数】

【已知： $r_i,r_{i+1},w,a,b,q$；未知： $s_i,e_0,e_1,x$ 】

3. re-arranging: put $x$ and $s$ on the left

$s=r_{i} \cdot w+e_{0} \quad \text { and } \quad a s+q x=r_{i+1} w-b+e_{1}$

【把未知参数s，x放在等式左边，方便写成矩阵形式】

4. $s \cdot\left(\begin{array}{l}1 \ a\end{array}\right)+x \cdot\left(\begin{array}{l}0 \ q\end{array}\right)=\boldsymbol{g}+\boldsymbol{e} \quad \text { where } \quad \boldsymbol{g}:=\left(\begin{array}{c}r_{i} w \ r_{i+1} w-b\end{array}\right) \quad \text { and } \quad \boldsymbol{e}:=\left(\begin{array}{c}e_{0} \ e_{1}\end{array}\right)$

【已知： $\boldsymbol{g},a,q$ ，未知：$\boldsymbol{e},s,x$ 】

5. to break the generator it suffices to find the vector $\boldsymbol{u}:=\boldsymbol{g}+\boldsymbol{e}$ .

【令 $u\in {Z}^2$ , $\boldsymbol{u}:=\boldsymbol{g}+\boldsymbol{e}=s \cdot(1, a)^{\mathrm{T}}+x \cdot(0, q)^{\mathrm{T}}$ 】

【如果我们求出了 $\boldsymbol{u}$ ，那可以用线性代数的知识解出 $s$ 和 $x$ ,再用 $s$ 来预测PRG的剩下输出】

6. konws $\boldsymbol{g}$ , knows $\boldsymbol{e}$ is shorter, and $|\boldsymbol{e} |_{\infty}$ is at most $\sqrt{q}/c$ , knows that $\boldsymbol{u}$ is “close” to $\boldsymbol{g}$ .

【e向量很小，$|\boldsymbol{e} |_{\infty}$ 上界是$\sqrt{q}/c$ ，u离g很近】

Taxicab norm or Manhattan(1-norm)

${\|}A{\|}_1=\max \{ \sum|a_{i1}|,\sum|a_{i2}|,...,\sum|a_{in}| \}$ （列和范数，A矩阵每一列元素绝对值之和的最大值）

Euclidean norm(2-norm)

$\|\mathbf{x}\|=\left(\sum_{i=1}^{n}\left|x_{i}\right|^{2}\right)^{1 / 2}$

$\infty$-范数

$\|A\|_{\infty}=\max \{ \sum|a_{1j}|,\sum|a_{2j}|,...,\sum|a_{mj}| \}$ （行和范数，A矩阵每一行元素绝对值之和的最大值）
1. attack can figure the lattice with attacking LCG.

the lattice is generated by the vectors $(1,5)^T$ and $(0,29)^T$ , the attacker has a vector $\boldsymbol{g}=(9,7)^T$ and wishes to find the closest lattice vector $\boldsymbol{u}$ .

【上图是 $(1,5)^T$ 和 $(0,29)^T$ 两个向量生成的的格点，希望能从以上格点找到离已知 $\boldsymbol{g}$ 向量最近的格点】

$\mathcal{L}_a$ :由 $(1, a)^{\mathrm{T}},(0, q)^{\mathrm{T}}$ 作为基向量生成的点集合。

1. The problem is a special case of a general problem call the closest vector problem: given a lattice $\mathcal{L}$ and a vector $\boldsymbol{g}$ ,find a vector in $\mathcal{L}$ that is closest to $\mathcal{g}$ .

There is an efficient polynomial time algorithm for this problem.[2]

【问题归结于 closest vector problem问题，在已知栅格点集合中找离某一向量最近的点，此问题已有多项式时间算法】

#### step 8 above

Lemma :
* For at least $(1-16/c^2)\cdot q$ of the a in $\mathcal{S}_q$ , the lattice $\mathcal{L}_a\sub Z_2$ has the following property: for every $\boldsymbol{g} \in Z^2$ there is at most one vector $\boldsymbol{u}\in \mathcal{L}_a$ such that $\|\boldsymbol{g}-\boldsymbol{u}\|_{\infty}<\sqrt{q}/c$ . *

【假设c=32，这个定理表示的意思是：a在$\mathcal{S}_q$ 的所有取值，有98%的取值保证了 $\mathcal{L}_a$ 中离向量 $\boldsymbol{g}$ 最近的点就是我们所求的 $\boldsymbol{u}$ 】

Armed with this algorithm the attacker can recover the internal state $s_i$ of the LCG generator from just two outputs $r_i,r_{i+1}$ of the generator and predict the remaining sequence. This attack works for 98% of the $a\in \mathcal{S}_q$.

【这个定理，可以保证文献中那个多项式算法[2]可以解决98%的a的取值】

For completeness we note that some example $a\in \mathcal{S}_q$ in the 2% where the attack fails are a = 1

and a = 2. For these a there may be many lattice vectors in $\mathcal{L}_a$ close to a given $\boldsymbol{g}$ .

【剩下2%的取值，是a=1,a=2这种取值很小的情况，因为Lattice中格点都离太近了】

#### Proof of lemma

• suppose: there are two vectors $u_0,u_1$ close to $g$ , that is , $\left\|\boldsymbol{u}_{i}-\boldsymbol{g}\right\|_{\infty}<\sqrt{q} / c \text { for } i=0,1$ .

【反证：假设有两个u1,u2离向量g很近，那么u1,u2也离的很近】

• by the triangle inequality, have $\left\|\boldsymbol{u}_{0}-\boldsymbol{u}_{1}\right\|_{\infty} \leq\left\|\boldsymbol{u}_{0}-\boldsymbol{g}\right\|_{\infty}+\left\|\boldsymbol{g}-\boldsymbol{u}_{1}\right\|_{\infty} \leq 2 \sqrt{q} / c$ .

【三角不等式得到， $\boldsymbol{u}_0-\boldsymbol{u}_1$ 的行和范数最大是 $\sqrt{q} / c$ 】

• $\boldsymbol{u}:=\boldsymbol{u}_{0}-\boldsymbol{u}_{1}$ is a vector in $\mathcal{L}_a$ ,and $\mathcal{L}_a$ conclude a "short" vector of non-zero vecor of norm at most $B= 2\sqrt{q} / c$ . Let's bound the number of bad a's for which $\mathcal{L}_a$ contains such a "short vector".

【向量集合的加法封闭性，$\mathcal{L}_a$ 中有一种”short vector”, 他的行和范数最大是$2\sqrt{q} / c$】

【我们去找有多少个”short vector” (number of bad a的最大值)，使得有两点$\boldsymbol{u}_0,\boldsymbol{u}_1$ 都离 $\boldsymbol{g}$ 很近】

• set $\boldsymbol{t}=(s, y)^{\mathrm{T}} \in \mathbb{Z}^{2}$ be the “short vector” such that $|t|_{\infty} \leq B$ .

• 【以下情况讨论可以用一般同余方程 $y=a s(\bmod q)$ 求通解的推导过程来理解】

• first consider the case when q is prime.

【先考虑q是素数的情况】

1. $\boldsymbol{t}$ 是$\mathcal{L}_a$ 中的点：存在 $s_a,x_a$ 让 $s_{a} \cdot(1, a)^{\mathrm{T}}+x_{a} \cdot(0, q)^{\mathrm{T}}=\boldsymbol{t}=(s, y)^{\mathrm{T}}$ 等式成立。
2. $\Rightarrow$ $s=s_a$ 和 $y=as_a\pmod{q}$ , 而且 $s\neq0$ 。

3. $y=as\pmod{q}$ ，由于q是素数， $a$ 可以唯一确定，得到 $a=y s^{-1} \bmod q$ 。

4. Hence, when q is prime, every non-zero short vector t is contained in at most one lattice $\mathcal{L}_a$ for some $a\in \mathcal{S}_q$ .

【每一个 $\boldsymbol{t}$ 都最多唯一对于 $\mathcal{L}_a$ 中的一个a】

5. ∞-范数的图如下图，所以”short vector” 的个数不超过这个正方形中的格点数，即 $=(2B)^2=16q/c^2$

6. 表述：当 $q$ 是素数时，每一个 “short vector” 对应一个 $a$ 的取值。

表述： $a$ 最多有 $16q/c^2$ 个。

• second consider the case when q is not prime.

1. $y=a s(\bmod q)$ ,q 不是质数，令 $d=\gcd(s,q)$ ，y肯定也是d的倍数

2. $\Rightarrow y/d=a\cdot s/d \pmod{q/d}$ ,且 $\gcd(s/d,q/d)=1$

3. $a_0$ 是 $a$ 在 mod $q/d$ 下的逆元。【同余方程的通解推导过程可以去看看】

4. 那么$y/d=a\cdot s/d \pmod{q/d}$ 中解 $a=a_0\cdot y/d$

5. $y=a s(\bmod q)$ 的通解就是 $a=a_0\cdot y/d + k\times q/d$ ($k=0,1,…d-1$ ) ，解数是 $d$ .

6. 表述：$y$ 最多有 $2B$ 个取值，但是只有 $2B/d$ 个 $y$ 使得方程有解。

表述：所以 $\boldsymbol{t}$向量的 $y$ 值最多只有 $2B/d$ 个。即”short vector” 只有 $2B/d \cdot2B$ 个

表述：每个 $y$ 使方程有解，但其解数是 $d$ 个。即每一个 “short vector” 对应 $d$ 个 $a$ 值。

表述：同样, $a$ 最多有 $16q/c^2$ 个。

• 综上， $\mathcal{S}_q$ 中最多有 $16q/c^2$ 个 bad $a$ 。

• Therefore, for $(1-16/c^2)\cdot q$ of the a values in $\mathcal{S}_q$ , the lattice $\mathcal{L}_a$ contains no non-zero short vectors and the lemma follows.

【证毕】

# Reference

1. LCG的数学部分来自Dan教授密码学的公开书:「A Graduate Course in Applied Cryptography」by D. Boneh and V.shoup

2. A. M. Frieze, R. Kannan, and J. C. Lagarias. Linear congruential generators do not produce random sequences. In FOCS, pages 480{484, 1984}.

3. P. C. van Oorschot and M. J. Wiener. Parallel collision search with application to hash functions and discrete logarithms. In Proceedings of the 2nd ACM Conference on Computer and Communications Security, pages 210{218, 1994}.