4. 密码学专题 - 分组密码工作模式

作者: furnace | 来源:发表于2020-05-10 11:05 被阅读0次

4. 密码学专题 - 分组密码工作模式
分组密码的工作模式
3. 密码学专题 - 分组密码
密码学学习笔记：分组密码操作模式
【密码学系列】|| 分组密码的工作模式详解
【猫说系列】密码学
5.1 密码学专题 - 对称加密算法 - 详解 DES 算法
密码学之对称加密
密码学之对称加密
分组密码工作模式

密码学专题 - 分组密码工作模式

分组密码只能加密固定长度的分组，如果需要加密一段并非恰好一个分组长度的数据，就需要使用分组密码工作模式，这也用来指称使用某个分组加密算法来构造的加密函数。

在开始介绍本章内容之前，我们要提醒一点。本章所讨论的加密模式可以防止窃听者读取所加密的消息流，但它们不提供任何认证，因此攻击者仍可以篡改消息，有时甚至可以任意方式篡改。很多人觉得这难以置信，但这很容易理解。加密模式下的解密函数仅仅解密数据，解密出来的内容可能没有任何意义，但还是将某个 (修改过的) 密文解密为 (修改过的并且毫无意义的) 明文。不能认为这些无意义的消息不会造成损害，因为系统的安全性依赖于系统其他部分，这往往也会导致很多问题。此外，对于某些加密方案，解密修改后的密文并一定产生 “垃圾消息”，某些模式允许针对性的明文修改，甚至许多数据格式可以通过局部地随机修改来操纵。

几乎在任何情况下，被篡改的消息所导致的损害远超过泄露明文所引发的损害。因此，需要将加密和认证结合起来。

4.1 填充

一般来说，分组密码工作模式是一种将一段明文 P 加密为密文 C 的方法，其中明文和密文可以是任意长度。大多数模式要求明文 P 的长度恰好是分组大小的整数倍，这就需要对明文进行填充。有多种填充明文的方法，但需要遵循的最重要的规则是：填充必须是可逆的，也就是说必须可以从填充后的消息中唯一地恢复出原始消息。

一个非常简单的填充规则是添加 0 直到消息的长度符合要求，这并不是一个很好的填充方法。这并不是可逆的，比如明文 p 和 p||0 具有相同的填充结果。(这里使用运算符 || 来表示连接。)

一个填充规则满足如果明文已经符合长度要求就无须进行填充是非常理想的，但这很难对所有情况都满足。对可逆的填充方案，都可以找到一些长度已适合但还需进行填充的消息，实际上所有填充规则都会给明文增加至少一个字节。

那么，应该如何填充明文？用 $P$ 来表示明文， $l(P)$ 表示 $P$ 的长度，以字节为单位， $b$ 为分组密码的分组大小 (以字节为单位)。我们建议使用以下两种填充方案之一：

在明文接下来的第一个字节中填充 128，然后填充 0 直到整个长度满足 $b$ 的倍数。填充 0 的字节数介于 $1,...,b-1$ 之间。
首先计算需要填充的字节数，该字节个数 $n$ 满足 $1 \leq n \leq b$ 并且 $n + l(P)$ 是 $b$ 的倍数。然后在明文后附加 $n$ 个字节，每个字节填充的值为 $n$ 。

上述两种方案都是可靠的。没有密码学分支来讨论填充，只需填充方法满足可逆性都是适用的。上面给出的两种方法只是最简单的填充方法，还可以在明文 $P$ 前先加入 $P$ 的长度，在 $P$ 之后填充 $P$ 一直到 $b$ 的倍数。这种方法需要在处理数据前预先知道明文 $P$ 的长度，有时却无法预知。

一旦填充后的长度是分组大小的倍数，就可以将填充后的明文分成多个分组。明文 $P$ 被分成一个分组序列 $P_1,...,P_k$ ，分组个数 $k$ 可由公式 $\lceil {l(P)+1/b} \rceil$ 来计算，这里符号 $\lceil ... \rceil$ 表示向上取整。在本章其余大部分地方，我们都假设明文是由整数个分组 $P_1,...,P_k$ 组成。

当采用随后介绍的分组密码工作模式来解密密文后，填充部分必须被移除。用于移除填充的代码还应该检测是否使用了正确的填充，填充的每个字节必须被验证填充了正确的值，一个错误的填充应如同认证错误来处理。

4.2 ECB

电子密码本 (ECB) 是最简单的加密长明文的工作模式，它的定义如下：
$C_i=E(K_i,P_i) \qquad i=1,...,k$

该工作模式非常简单：只需要分别加密明文消息的每个分组。当然，情况也并非如此简单，否则就不会安排一整章来讨论分组密码的工作模式。任何时候都不要使用 ECB 模式，该模式有严重的缺陷，在这里引入只是为了提醒你不要去使用它。

ECB 模式存在什么问题？如果两个明文分组是完全相同的，那么相应的密文分组也是相同的，这对攻击者是可见的。依赖于消息的结构，这会向攻击者泄露很多信息。

在很多情况下会出现重复的大分组文本，例如本章中多次出现 “密文分组” 这个词。如果两次出现都恰好落在分组的范围内，那么表示一个明文分组重复出现了。在大多数 Unicode 字符串中，每隔一个字节有一个 0 值，这就极大地增加了出现重复分组的机会。很多文件格式中会出现由多个 0 组成的大分组，这也导致大量重复分组的出现。总的来说，这个性质使得 ECB 模式基本不会被使用。

4.3 CBC

密码分组链 (CBC) 是应用最广泛的分组密码工作模式之一。通过将每个明文分组与前一个密文分组进行异或操作，该模式避免了 ECB 模式的问题。CBC 模式标准形式定义如下：
$C_i=E(K,P_i \bigoplus C_{i-1}) \qquad i=1,...,k$

使用前一个密文分组来 “随机化” 明文避免了 EBC 模式所存在的问题，相同的明文分组将加密为不同的密文分组，显著减少了攻击者所能获取的信息。

我们还需回答采用什么值作为 $C_0$ ，这个值被称为初始化向量，或者 IV。下面分析几种选取 IV 的策略。

4.3.1 固定 IV

不要使用固定 IV，这会在加密消息的第一个分组时引入 ECB 模式所存在的问题。如果两个不同消息的首个明文分组相同，那么它们起始的密文分组也会相同。实际应用中的消息经常会以相似或相同的分组开始，而我们不想让攻击者检测到这一点。

4.3.2 计数器 IV

另一种方法是使用一个计数器作为 IV。对于第一个消息，让 IV = 0; 对于第二个消息，令 IV = 1。同样，这也不是一种好的方案。正如之前提到，实际应用中很多消息内容的开头都是相似的，如果不同消息的第一个块差别较小，那么经过异或操作，计数器 IV 就可能抵消这个差别，重新生成相同的密文分组。例如 0 与 1 只是一位有所不同，如果两个消息开头的明文分组恰好只是在这个位上不同 (这类情况发生的概率要远大于所想象的)，那么这两个消息的起始密文分组将会相同。攻击者会敏捷地发现两个明文之间的差别，这是安全的加密方案所不允许的。

4.3.3 随机 IV

ECB 模式与采用固定 IV 或者计数器 IV 的 CBC 模式所存在的问题都源于明文消息并不是非常随机的，明文通常有固定的开头或者非常可预测的结构，选择明文的攻击者甚至可以控制明文的结构。在 CBC 模式中，密文分组被用于 “随机化” 明文分组，但对第一个明文分组，必须使用初始化向量 IV，因此应该采用随机 IV。

这就引发了另一个问题，随机选择的 IV 必须让解密方知道，才能够正确解密。一个标准的解决方案是选择随机 IV 并作为第一个密文块放在消息所对应的密文之前发送给接收者。相应的加密过程如下：
$C_0 := 随机分组值$

$C_i := E(K,P_i \bigoplus C_{i-1}) \qquad i=1,...,k$

这里明文 $P_1,...,P_k$ 就被加密为 $C_0,...,C_k$ 。注意，密文是以 $C_0$ (而不是 $C_1$ ) 开始的，密文要比明文多一个分组。对应的解密过程如下：
$P_i := D(K,C_i) \bigoplus C_{i-1} \qquad i=1,...,k$

使用随机 IV 的主要缺点就是密文比明文多一个分组，对于长度较短的消息来说，将导致消息长度的显著增长，这通常是人们不希望的。

4.3.4 瞬时 IV

还有另一种解决方案，该方案分为两步。首先，为每一个用该密钥加密的消息分配一个唯一的数，称为瞬时值 (nonce, number used once)，瞬时值的关键是它的唯一性，对于同一个密钥，相同的瞬时值不能使用两次。通常，瞬时值是消息的某种编号，可能与其他信息结合而构成。在大多数系统中本已对消息进行编号，如用于保证消息正确的顺序或者检测重复消息等。瞬时值本身不需要保密，但一个瞬时值只能使用一次。

在 CBC 模式中，就是用瞬时 IV 加密的方法来得到初始向量 IV。

在典型的场景下，发送者对消息进行连续编号，并在每次传输时发送这个消息编号。发送者发送消息的过程如下：

为消息分一个消息编号。通常，消息的编号由一个从 0 开始的计数器提供，而计数器在任何时候都不能返回 0，否则就会破坏唯一性。
由消息编号构造唯一的瞬时值。对给定的密钥，瞬时值不仅在这台计算机中是唯一的，甚至在整个系统都是唯一的。例如，同一个密钥用于加密双向的通信，此时瞬时值应该由消息编号与消息的发送方向标识组成。瞬时值的大小应该是分组密码的单个分组大小。
用分组密码加密瞬时值得到 IV。
在 CBC 模式下使用此 IV 对消息加密。
在密文中添加足够的信息使接收者能够恢复这个瞬时值。有一种方法是在明文的前面附加消息编号，或者通过可靠信道传输密文，这时消息编号将是隐含的，IV 值本身 (公式中的 $C_0$ ) 不需发送。

包含在消息中的额外信息通常比随机 IV 模式少得多。对大多数系统来说，32 ~ 48 位的消息计数器已经足够大了，而随机 IV 需要 128 位的 IV 开销。大部分的通信系统都需要消息计数器，或者使用隐含计数器的可靠传输信息，因此这种方式生成 IV 并没有增加消息的开销。

如果攻击者可以完全掌握瞬时值的生成，那么在生成 IV 时这个瞬时值需要采用一个单独的密钥来进行加密。任何实际系统都需要确保瞬时值的唯一性，但是并不是说可以任意选取瞬时值，所以在大多数情况下就如加密消息一样使用相同的密钥加密瞬时值。

4.4 OFB

到目前为止所介绍的模式都是以某种方式用分组密码对消息分组进行加密，输出反馈模式 (OFB) 与此不同，它并不是将消息作为加密函数的输入进行加密。相反，输出反馈模式使用分组密码生成一个伪随机字节流 (称为密钥流)，然后将其与明文进行异或运算得到密文。这种用生成随机密钥流进行加密的方案称为流密码。一些人似乎认为流密码的安全性并不高，其实完全不是这样，只要使用恰当，流密码是非常有用的。流密码在使用时要非常小心，对流密码的误用如重复使用瞬时值，很容易使用系统变得不安全。像 CBC 这样的工作模式即使在被误用的情况下仍然能够正常工作，相比之下更加健壮。而流密码的优点比它的缺点更加突出。

OFB 可以定义为：
$K_0 := IV$

$\qquad \qquad \qquad \qquad \qquad K_i := E(K,K_{i-1}) \qquad i=1,...,k$

$\qquad C_i := P_i \bigoplus K_i$

这里同样使用 IV 值 $K_0$ 重复进行加密生成密钥流 $K_1,...,K_k$ ，然后明文与密钥流进行异或运算生成密文。

这个 IV 必须是随机的，如同在 CBC 中一样，IV 可以随机地选择并同密文一起发送出去，了可以由一个瞬时值生成。

OFB 的一个优点是它的解密运算和加密运算完全相同，这样实现起来非常容易。因为仅需要实现分组密码的加密函数，而无须再实现解密运算。

OFB 的另一个优点是不需要对明文进行填充。如果将密钥流看作一个字节序列，加密时可以使用和消息明文同样长度的字节。换句话说，如果最后一个明文分组并非 “全满”，那么只需要发送那些和明文对应的密文字节。无须对明文进行填充，降低了开销，这一点对长度较短的消息来说非常重要。

当然由于 OFB 模式使用流密码，还面临一个风险。一旦有两个不同的消息使用了同一个 IV，那么这两个消息就被相同的密钥流加密。这会引发非常严重的后果。假设 $P$ 与 $P'$ 是两个不同消息的明文，它们被相同的密钥流分别加密为 $C$ 与 $C'$ ，现在攻击者可以计算 $C_i \bigoplus C_i' = P_i \bigoplus K_i \bigoplus P_i' \bigoplus K_i = P_i \bigoplus P_i'$ 。也就是说，攻击者可以计算出两个明文的差别。如果攻击者已知其中一个明文 (这在现实生活中常常发生)，那么就能够很容易地求出另外一个明文。有些著名的攻击甚至可以从未知明文中通过明文之间的差别来恢复这两个未知明文的信息。

OFB 的另一个问题是如果一个密钥分组重复出现，那么随后密钥分组序列就与之前的重复了。对于长度较大的消息来说，密钥分组序列中有可能出现循环。另外，如果一个消息的 IV 与另外一个消息所对应的密钥分组序列中的某一个密钥分组相同，那么两个消息的一部分就使用了相同的密钥流。在这两种情况下，都使用相同的密钥流对不同的消息分组进行加密，这不是一种安全的加密方案。

在这成为可能之前已加密了大量的数据，这根本上来说是一种在密钥流分组和初始点之间的碰撞攻击，所以在发生碰撞之前至少能加密 $2^{64}$ 个数据分组。这也是为何 128 位长度的分组密码仅能提供 64 位安全性的一个例子。如果限制每个密钥所能加密的数据量，就可以降低密钥分组重复的可能性。但尽管如此，碰撞的风险仍然存在，假如不幸出现了碰撞，整个消息的保密性就无法保证了。

4.5 CTR

还有另一种分组密码的工作模式称为计数器模式，简称为 CTR。这种模式已经被使用很多年，却一直没有被称作为 DES 的标准模式，因此被很多教材所忽略。最近，CTR 已由美国国家标准和技术研究所 (NIST) 标准化。与 OFB 模式一样，计数器模式也是一种流密码模式，定义如下：
$\qquad \qquad \qquad \qquad \qquad K_i := E(K,Nonce||i) \qquad i=1,...,k$

$C_i := P_i \bigoplus K_i$

如同所有的流密码一样，加密时必须使用某种形式的唯一瞬时值。大多数系统都是用消息编号与某些附加数据来生成瞬时值，以保证它的唯一性。

CTR 有两个问题。第一个同 OFB 一样。第二个是瞬时值的唯一性。

4.6 如何选择工作模式

之前已经介绍了几种模式，但是只有两种模式可以考虑使用：CBC 模式和 CTR 模式。之前已经说明 ECB 模式不够安全。而且 OFB 虽然是一个不错的工作模式，但是 CTR 模式在某些方面更优，而且避免了短循环的问题。因此没有理由丢弃 CTR 而选择 OFB。

那么，在 CBC 模式和 CTR 模式中应该选择哪一个呢？我们之前建议使用 CTR 模式。但是随着密码学的发展，我们现在更加倾向于选择随机 IV 下的 CBC 模式。为什么会有这种改变呢？因为目前已经存在很多由不于不能够正确生成瞬时值所导致的应用安全问题的例子。即使是系统面临攻击时，CTR 还是一个很好的模式，但是前提是应用必须要能够生成唯一的瞬时值，这会成为很多问题和安全漏洞的主要源头。随机 IV 下的 CBC 模式虽然有一些缺点 (密文更长，明文需要填充，系统需要随机数生成器)，但是具有更强的健壮性，即使误用也能很好地工作。在很多系统中，瞬时值生成都是一个非常困难的问题。所以不建议采用需要使用瞬时值的任何模式。当然这也包括瞬时 IV 下的 CBC 模式。因此，如果在开发应用时需要使用加密模式，建议安全起见使用随机 IV 下的 CBC 模式。

需要注意的是加密模式仅仅提供保密性，也就是说，攻击者无法获取所传输的数据的信息，但不包括你正在通信、在何时通信、通信的数据量、在和谁通信等这些信息。对这些外部信息进行的分析称为流量分析 (traffic analysis)。

项目源代码

项目源代码会逐步上传到 Github，地址为 https://github.com/windstamp。

Contributor

Windstamp, https://github.com/windstamp

4. 密码学专题 - 分组密码工作模式
密码学专题 - 分组密码工作模式分组密码只能加密固定长度的分组，如果需要加密一段并非恰好一个分组长度的数据，就需...
分组密码的工作模式
简介密码学中，分组（block）密码的工作模式（mode of operation）允许使用同一个分组密码密钥对...
3. 密码学专题 - 分组密码
密码学专题 - 分组密码分组密码是密码系统的基本组成部分这一。可以说分组密码是密码学最容易理解的部分，在大多数应...
密码学学习笔记：分组密码操作模式
前言最近在分组密码学习的过程中，了解了AES分组密码以及分组密码的五种操作模式。目前已知的对AES的分析攻击都比...
【密码学系列】|| 分组密码的工作模式详解
用心分享，共同成长没有什么比你每天进步一点点更实在了本文已经收录至我的GitHub，欢迎大家踊跃star?。Gi...
【猫说系列】密码学
【密码学】 1、对称加密 2、非对称加密3、DES 4、分组密码5、公钥密码学6、Hash7...
5.1 密码学专题 - 对称加密算法 - 详解 DES 算法
密码学专题 - 对称加密算法 - DES 算法 5.1 DES 的描述 DES 是一个分组加密算法，它以 64 位...
密码学之对称加密
1.密码学简介 2.对称加密 3.分组加密模式 4.非对称加密 5.单向散列函数 6.消息认证码 7.数字签名 8...
密码学之对称加密
1.密码学简介 2.对称加密 3.分组加密模式 4.非对称加密 5.单向散列函数 6.消息认证码 7.数字签名 8...
分组密码工作模式
今天天气不是很完美，阴沉、冷，感觉特别的压抑。记得当年学习 C 语言的指针时，选择了一个阳光明媚、风和日丽的晴天去...