复习一下密码学。
分组密码的工作模式简介
密码学中,区块(block)密码的工作模式(mode of operation)允许使用同一个区块密码密钥对多于一块的数据进行加密,并保证其安全性。区块密码自身只能加密长度等于密码区块长度的单块数据,若要加密变长数据,则数据必须先被划分为一些单独的密码块。通常而言,最后一块数据也需要使用合适填充方式将数据扩展到符合密码块大小的长度。一种工作模式描述了加密每一数据块的过程,并常常使用基于一个通常称为初始化向量的附加输入值以进行随机化,以保证安全。
工作模式主要用来进行加密和认证。对加密模式的研究曾经包含数据的完整性保护,即在某些数据被修改后的情况下密码的误差传播特性。后来的研究则将完整性保护作为另一个完全不同的,与加密无关的密码学目标。部分现代的工作模式用有效的方法将加密和认证结合起来,称为认证加密模式。
虽然工作模式通常应用于对称加密,它亦可以应用于公钥加密,例如在原理上对 RSA 进行处理,但在实用中,公钥密码学通常不用于加密较长的信息,而是使用结合对称加密和公钥加密的混合加密方案。
初始化向量(IV)
初始化向量(IV,Initialization Vector)是许多工作模式中用于将加密随机化的一个位块,由此即使同样的明文被多次加密也会产生不同的密文,避免了较慢的重新产生密钥的过程。
初始化向量与密钥相比有不同的安全性需求,因此 IV 通常无须保密,然而在大多数情况中,不应当在使用同一密钥的情况下两次使用同一个 IV。对于 CBC 和 CFB,重用 IV 会导致泄露明文首个块的某些信息,亦包括两个不同消息中相同的前缀。对于 OFB 和 CTR 而言,重用 IV 会导致完全失去安全性。另外,在 CBC 模式中,IV 在加密时必须是无法预测的;特别的,在许多实现中使用的产生 IV 的方法,例如 SSL2.0 使用的,即采用上一个消息的最后一块密文作为下一个消息的 IV,是不安全的。
填充(padding)
块密码只能对确定长度的数据块进行处理,而消息的长度通常是可变的。因此部分模式(即 ECB 和 CBC)需要最后一块在加密前进行填充。有数种填充方法,其中最简单的一种是在明文的最后填充空字符以使其长度为块长度的整数倍,但必须保证可以恢复明文的原始长度;例如,若明文是 C 语言风格的字符串,则只有串尾会有空字符。稍微复杂一点的方法则是原始的 DES 使用的方法,即在数据后添加一个 1 位,再添加足够的 0 位直到满足块长度的要求;若消息长度刚好符合块长度,则添加一个填充块。最复杂的则是针对 CBC 的方法,例如密文窃取,残块终结等,不会产生额外的密文,但会增加一些复杂度。布鲁斯·施奈尔和尼尔斯·弗格森提出了两种简单的可能性:添加一个值为 128 的字节(十六进制的 80),再以 0 字节填满最后一个块;或向最后一个块填充 n 个值均为 n 的字节。
CFB,OFB 和 CTR 模式不需要对长度不为密码块大小整数倍的消息进行特别的处理。因为这些模式是通过对块密码的输出与明文进行异或工作的。最后一个明文块(可能是不完整的)与密钥流块的前几个字节异或后,产生了与该明文块大小相同的密文块。流密码的这个特性使得它们可以应用在需要密文和明文数据长度严格相等的场合,也可以应用在以流形式传输数据而不便于进行填充的场合。
常用模式
电子密码本(ECB)
最简单的加密模式即为电子密码本(Electronic codebook,ECB)模式。需要加密的消息按照块密码的块大小被分为数个块,并对每个块进行独立加密。
ECB 的缺点在于同样的明文块会被加密成相同的密文块,因此它不能很好的隐藏数据模式。在某些场合,这种方法不能提供严格的数据保密性,因此并不推荐用于密码协议中。
ECB 模式也会导致使用它的协议不能提供数据完整性保护,易受到重放攻击的影响,因此每个块是以完全相同的方式解密的。例如,“梦幻之星在线:蓝色脉冲”在线电子游戏使用 ECB 模式的 Blowfish 密码。在密钥交换系统被破解而产生更简单的破解方式前,作弊者重复通过发送加密的“杀死怪物”消息包以非法的快速增加经验值。
密码块链接(CBC)
1976 年,IBM 发明了密码分组链接(CBC,Cipher-block chaining)模式。在 CBC 模式中,每个明文块先与前一个密文块进行异或后,再进行加密。在这种方法中,每个密文块都依赖于它前面的所有明文块。同时,为了保证每条消息的唯一性,在第一个块中需要使用初始化向量。
若第一个块的下标为 1,则 CBC 模式的加密过程如下:
$$
C_i = E_K(P_i \oplus IV) \\
IV = C_i
$$
其解密过程如下:
$$
P_i = D_K(C_i) \oplus IV \\
IV = C_i
$$
CBC 是最为常用的工作模式。它的主要缺点在于加密过程是串行的,无法被并行化,而且消息必须被填充到块大小的整数倍。解决后一个问题的一种方法是利用密文窃取。
注意在加密时,明文中的微小改变会导致其后的全部密文块发生改变,而在解密时,从两个邻接的密文块中即可得到一个明文块。因此,解密过程可以被并行化,而解密时,密文中一位的改变只会导致其对应的明文块完全改变和下一个明文块中对应位发生改变,不会影响到其它明文的内容。
填充密码块链接(PCBC)
填充密码块链接(PCBC,Propagating cipher-block chaining)或称为明文密码块链接(Plaintext cipher-block chaining),是一种可以使密文中的微小更改在解密时导致明文大部分错误的模式,并在加密的时候也具有同样的特性。
PCBC 的加密过程如下:
$$
C_i = E_K(P_i \oplus IV) \\
IV = P_i \oplus C_i
$$
其解密过程如下:
$$
P_i = D_K(C_i) \oplus IV \\
IV = P_i \oplus C_i
$$
PCBC 主要用于 Kerberos v4 和 WASTE 中,而在其它场合的应用较少。对于使用 PCBC 加密的消息,互换两个邻接的密文块不会对后续块的解密造成影响。正因为这个特性,Kerberos v5 没有使用 PCBC。
密文反馈(CFB)
密文反馈(CFB,Cipher feedback)模式类似于 CBC,可以将块密码变为自同步的流密码;工作过程亦非常相似,CFB 的解密过程几乎就是颠倒的 CBC 的加密过程:
$$
C_i = E_K(IV \oplus P_i) \\
P_i = E_K(IV \oplus C_i) \\
IV = C_i
$$
上述公式是描述的是最简单的 CFB,在这种模式下,它的自同步特性仅仅与 CBC 相同,即若密文的一整块发生错误,CBC 和 CFB 都仍能解密大部分数据,而仅有一位数据错误。若需要在仅有了一位或一字节错误的情况下也让模式具有自同步性,必须每次只加密一位或一字节。可以将移位寄存器作为块密码的输入,以利用 CFB 的自同步性。
为了利用 CFB 制作一种自同步的,可以处理任意位情况错误的流密码,需要使用一个与块的大小相同的移位寄存器,并用 IV 将寄存器初始化。然后,将寄存器内容使用块密码加密,然后将结果的最高 $x$ 位与明文的 $x$ 进行异或,以产生密文的 $x$ 位。下一步将生成的 $x$ 位密文移入寄存器中,并对下面的 $x$ 位明文重复这一过程。解密过程与加密过程相似,以 IV 开始,对寄存器加密,将结果的高 $x$ 与密文异或,产生 $x$ 位明文,再将密文的下面 $x$ 位移入寄存器。
下式中 $S_i$ 是移位寄存器的第 $i$ 个状态,$a \ll x$ 是指将 $a$ 移位 $x$ 位,$head(a, x)$ 是指 $a$ 的高 $x$ 位,$n$ 则是指 IV 的位数。
$$
C_i = head(E_K(S_{i-1}), x) \oplus P_i \\
P_i = head(E_K(S_{i-1}), x) \oplus C_i \\
S_i = ((S_{i-1} \ll x) + C_i) mod\ 2^n \\
IV = S_i
$$
若密文的 $x$ 位发生错误,则密码在移位寄存器恢复与加密时的状态相同之前,输出不正确的结果,而当寄存器状态恢复后,密码即可以重新同步,恢复正常输出,因此最多只有一块数据发生错误。
与 CBC 相似,明文的改变会影响接下来所有的密文,因此加密过程不能并行化;而同样的,与 CBC 类似,解密过程是可以并行化的。在解密时,密文中一位数据的改变仅会影响两个明文块:对应明文块中的一位数据与下一块中全部的数据,而之后的数据将恢复正常。
CFB 拥有一些 CBC 所不具备的特性,这些特性与 OFB 和 CTR 的流模式相似:只需要使用块密码进行加密操作,且消息无需进行填充(虽然密文窃取也允许数据不进行填充)。
输出反馈(OFB)
输出反馈模式(Output feedback, OFB)可以将块密码变成同步的流密码。它产生密钥流的块,然后将其与明文块进行异或,得到密文。与其它流密码一样,密文中一个位的翻转会使明文中同样位置的位也产生翻转。这种特性使得许多错误校正码,例如奇偶校验位,即使在加密前计算,而在加密后进行校验也可以得出正确结果。
由于 XOR 操作的对称性,加密和解密操作是完全相同的:
$$
C_i = P_i \oplus O_i \\
P_i = C_i \oplus O_i \\
O_i = E_K(O_{i-1}) \\
IV = O_i
$$
每个使用 OFB 的输出块与其前面所有的输出块相关,因此不能并行化处理。然而,由于明文和密文只在最终的异或过程中使用,因此可以事先对 IV 进行加密,最后并行的将明文或密文进行并行的异或处理。
可以利用输入全 0 的 CBC 模式产生 OFB 模式的密钥流。这种方法十分实用,因为可以利用快速的 CBC 硬件实现来加速 OFB 模式的加密过程。
计数器模式(CTR)
PS:CTR 模式(Counter mode,CM)也被称为 ICM 模式(Integer Counter Mode,整数计数模式)和 SIC 模式(Segmented Integer Counter)。
与 OFB 相似,CTR 将块密码变为流密码。它通过递增一个加密计数器以产生连续的密钥流,其中,计数器可以是任意保证长时间不产生重复输出的函数,但使用一个普通的计数器是最简单和最常见的做法。使用简单的、定义好的输入函数是有争议的:批评者认为它“有意的将密码系统暴露在已知的、系统的输入会造成不必要的风险”。目前,CTR 已经被广泛的使用了,由输入函数造成的问题被认为是使用的块密码的缺陷,而非 CTR 模式本身的弱点。无论如何,有一些特别的攻击方法,例如基于使用简单计数器作为输入的硬件差错攻击。
CTR 模式的特征类似于 OFB,但它允许在解密时进行随机存取。由于加密和解密过程均可以进行并行处理,CTR 适合运用于多处理器的硬件上。
注意图中的“nonce”与其它图中的 IV(初始化向量)相同。IV、随机数和计数器均可以通过连接,相加或异或使得相同明文产生不同的密文。
References
https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation