Crypto101 阅读笔记（2）

流加密

流加密（Stream Cipher）是对称密钥加密算法的一种，用来加密比特流。

流加密算法有两种，一种是利用块加密算法，利用某种工作模式，加密比特流；另一种从设计就是为了比特流考虑的算法。

ECB 模式

利用前一篇里面的块加密算法，很容易构想出一个原始简单的流加密算法。就是把比特流分割成一个个的具有块大小的数据块，然后对每一块分别使用块加密算法进行加密。

这种方式叫做 ECB（Electronic Code Book mode）模式。这种加密模式最大的问题是相同的原明文块会被转变成相同的加密块。

CBC 模式

CBC 模式，Cipher Block Chining。CBC 模式就是明文数据块在加密之前会和前一个加密过得到的密文块进行异或运算。这个模式的问题是第一个明文块，没有前一个加密块。所以要引入一个 IV（Initialization Vector），初始化向量作为最初的加密块使用。IV 必须随机，不可预测，但没必要加密，重要的是不可预测。

CBC_encryption

与 CBC 模式很相似的模式还有 CFB 和 OFB 模式。

CBC 模式下基于可预测 IV 的攻击

在 AES 系统中，IV 通常都是可以从密文 C 中读到的。

一种常用的 AESCipher 的 Python 实现如下：

import base64
from Crypto.Cipher import AES
from Crypto import Random

class AESCipher:
    def __init__( self, key ):
        self.key = key

    def encrypt( self, raw ):
        raw = pad(raw)
        iv = Random.new().read( AES.block_size )
        cipher = AES.new( self.key, AES.MODE_CBC, iv )
        return base64.b64encode( iv + cipher.encrypt( raw ) ) 

    def decrypt( self, enc ):
        enc = base64.b64decode(enc)
        iv = enc[:16]
        cipher = AES.new(self.key, AES.MODE_CBC, iv )
        return unpad(cipher.decrypt( enc[16:] ))

其中 IV 都是可以直接知道的。但是 IV 可知并不是什么问题，主要的问题是，IV 要不可被预知。

假设某条加密过的数据 $C_1$ 的 IV 是 $IV_a$ 可知，针对我们即将输入进去的数据的 IV 我们可预知，即 $IV_m$，我们可构造明文数据 $P_m = IV_m \oplus IV_a \oplus G$，其中，G 是我们猜测的 C1 的原文。

然后由

$$
C_m = E(k, IV_m \oplus P_m) \
= E(k, IV_m \oplus(IV_m \oplus IV_a \oplus G)) \
= E(k, IV_a \oplus G)
$$

这里通过比较 $C_m$ 和 $C_1$，可以验证对于 $C_1$ 猜测的原文 G 是否正确。

CBC 模式下把 key 用作 IV 的攻击

把 key 用作 IV 是不安全的。

假设 Alice 的明文 P 包含三个 block，分别为 $P_1 P_2 P_3$，在 CBC 模式下用 key 加密，并且 IV 也是 key。得到的密文 C 为 $C_1 C_2 C_3$ 发送给了 Bob。

在 Bob 接收到密文之前，Mallory 截获了密文。然后把密文篡改成 $C^{‘} = C_1ZC_1$，其中 Z 是全 0 的一个块。当 Bob 接收到被篡改过的密文并解密 $C^{‘}$ 之后，得到三个明文串 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$。

$$P^{‘}_1 = D(k, C_1) \oplus IV = D(k, C_1) \oplus k = P_1 $$

$$P^{‘}_2 = D(k, Z) \oplus C_1 = R$$

$$P^{‘}_3 = D(k, C_1) \oplus Z = D(k, C_1) = P_1 \oplus IV$$

其中 R 是一个无所谓的串。

到此，Mallory 在得知 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$ 的情况下，就可以推算出 IV，由于 key 就是 IV，所以就推算出了 key。

到这里我有个疑惑，Mallory 是怎么得知 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$。然后发现书中这样的一句话 “Under the chosen-ciphertext attack assumption”。这句话的意思是，攻击者可以通过给定某一个特定的密文 C 给解密者并且获得对应解密后的明文结果。通常是利用解密端软件的某些 bug 或者漏洞。所以这里 Mallory 是可以拿到对应的 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$ 的。所以说，这种漏洞的利用还是比较难的。

Padding

Padding 就是填充的意思。

在 CBC 模式下，假设了每个加密块都是块加密算法的 block size 大小。但事实上，真正的数据流的长度是不定的。那么对于最后一块数据，长度不足一个 block 时候，就需要在末尾填充一些其他数据来满足长度要求。这个就是 Padding。

最简单的思维是，填充某个固定的字节，例如 0。问题是，无法区分填充字节和原来的数据。

更好，更常用的方法是 PKCS#5/PKCS#7。基本思想是，对于后面少几个字节，就把几全部填充进去。例如一个 8 个字节的 block，原始数据是 12 34 45，差 5 个字节。那么就填充成 12 34 45 05 05 05 05 05。当某个数据刚好是 block 的整数倍，不需要填充时，则在最后面填充一整个 block。

CBC Padding attack

使用 Padding attack 只需要两点，一段需要解密的密文 $C_i$，和一个可以响应 Padding 是否合法的目标程序。这里假设填充方法是上面说的 PKCS#5/PKCS#7。

首先攻击者构造一个随机串 $R = r_1,r_2,r_3…r_b$。然后，攻击者不停的尝试随机串 $R$ 的最后一个字符 $r_b$，目的是得到一个填充合法的结果。最差的情况是使得最后的明文串 $P_i$ 的最后一位 $P_b$ 是 01。根据上述 PKCS 的填充原理，01 必然是一个合法的填充结果。

这时我们得到填充合法的结果，我们有此时的随机串 $R$。但是并不知道填充的位数。但是可以知道的是，$P_i$ 的末尾必然是

$01$
$02\ 02$
$03\ 03\ 03$
… 这些情况。

当然，从概率上而言，结尾是 $01$ 的可能性最大。

这里，我们假设最后的明文 $P_i = p_0p_1p_2p_3p_4030303$，其中 $p_0p_1p_2p_3p_4$ 是什么并不会影响我们进行填充正确性的检验。

所以我们从 $r_0$ 开始尝试变动，这样会导致最后的 $P_i = p^{‘}_0p_1p_2p_3p_4030303$。但是这样并不会影响我们进行填充正确性的检验。所以我们可以继续变动下一位 $r_1$，这样一直下去，直到填充正确性检验失败，我们就可以知道有多少位的填充 padding。从实际工作角度，我们或许没必要猜测是几位。我们就假定末尾是 01。当填充正确性检验通过的时候，我们不知道最后实际是几位，但是我们只需要变动一下倒数第二位，一旦校验失败，则说明 Padding 一定不是 01，这时我们不管他，继续尝试 $r_0$，直到能说明 Pading 是 01 为止。

接下来，我们假设最后的填充是 $01$，这是最坏的情况。

那么就有 $D(C_i)[b] \oplus r_b = 01$，这样我们可以计算出 $D(C_i)[b]$，即$C_i$被算法 D 解密之后的中间结果的最后一位。要注意这个中间结果，我们做这么多，目的就是这个中间结果，这个中间结果是不会变动的。

接下来我们去尝试倒数第二位。首先，根据上面的等式，我们可以推出 $D(C_i)[b] \oplus r_b \oplus 01 \oplus 02 = 01 \oplus 01 \oplus 02 = 02$，也就是让 $r_b = r_b \oplus 01 \oplus 02$，这时最后的填充位就变成了 02，这样，我们去暴力尝试 R 的倒数第二位，使得最后填充检验通过。这时，我们就可以得到$D(C_i)[b-1]$，也就是这个中间结果的倒数第二位。不断重复这个过程，我们可以得到整个中间结果串 $D(C_i)$。

这时，我们拿出密文 $C_i$ 的前一个密文串 $C_{i-1}$，根据 CBC 的工作模式，这里 $C_{i-1} \oplus C_i = P_i$。就这样，我们得到了解密后的结果 $P_i$。然后重复整个过程，我们可以解出所有的明文，除了第一块，因为我们不知道 IV。

RC4

RC4，十分简单，但是已经被攻破。而且很快，13.9 cycles/bit。AES-128 CTR 模式是 12.6 cycles/bit，CBC 模式是 16 cycles/bit。

Salsa20

Salsa20 是一种新的流加密算法。目前有两个版本，Salsa20/12 和 Salsa20/8。其中 12 和 8 表示循环次数，从原始的 20 降下来。与 Salsa20 相似的还有 ChaCha。

Salsa20 和 ChaCha 都非常快。

Salsa20 有个特点就是可以从任意一段进行加密解密。意味着算法可以并行。

CTR 模式

CTR 模式，也叫 counter 模式。

工作流程很简单，一个初始化的随机数 N，然后 N 和一个计数器连起来。和 key 加密后产生 key stream 再和明文 P 异或产生密文 C。每加密一块后计数器就加一。循环往复。

和 Salsa20 一样，可以从任意一段开始，也就是可以并行。

文章目录

流加密