Chapter 4:Message Authentication Codes

# 4.Message Authentication Codes

# 4.1 消息完整性

# 4.1.1 保密性与完整性

密码学的基本目标是使各方能够安全地通信。但是，“安全通信”究竟意味着什么呢？在第3章中，我们展示了如何实现保密性；也就是说，我们展示了如何使用加密来防止被动窃听者了解在开放通道上发送的消息。然而，并非所有的安全问题都与保密性有关，也并非所有的对手都仅限于被动窃听。在许多情况下，对于能够在信道上==注入消息或修改消息==的主动对手来说，保证消息完整性（或消息认证）同样重要甚至更为重要。我们考虑两个激励示例，分别对应于图1.1和1.2的设置。
首先，想象一位用户通过互联网与其银行进行通信。当银行收到一项从该用户帐户转账$1,000至某个其他用户X的请求时，银行必须考虑以下事项：

请求是否真实？也就是说，发出此请求的确实是该用户，还是由一个对手（可能是X本身）冒充合法用户发出的请求？
假设合法用户发出了转账请求，银行收到的请求是否与该用户发送的完全相同？或者在请求通过互联网发送时，例如，转账金额是否被修改？

请注意，标准的纠错技术不足以解决第二个问题。纠错码只能检测和恢复影响传输的一小部分的“随机”错误，但它们对于可以选择在哪里引入任意数量更改的恶意对手不起任何保护作用。
实际上，在涉及Web cookie时需要消息完整性的非常不同的场景。用于Web流量的HTTP协议是无状态的，因此当客户端和服务器在某个会话中通信时（例如，当用户[客户端]在商家[服务器]的网站上购物时），作为该会话的一部分生成的任何状态（例如，用户购物车的内容）通常会放置在一个“cookie”中，该cookie由用户存储，并随每个用户发送给商家的消息一起包含。假设某个用户存储的cookie包括用户购物车中的商品及其价格，如商家向不同用户提供不同的价格（反映折扣和促销或用户特定的定价）所做的操作。如果用户能够修改其存储的cookie以更改其购物车中商品的价格，则这是不可取的。因此，商家需要一种技术来确保其存储在用户处的cookie的完整性。请注意，cookie的内容（即商品及其价格）不是机密的，实际上，用户必须知道它们。这里的问题纯粹是完整性问题。
通常，不能假定通信的完整性而不采取特定措施来确保它。事实上，任何未受保护的在线购买订单、在线银行业务、电子邮件或短信消息都不能一般地信任其来自所声称的来源并且在传输过程中没有被修改。不幸的是，人们通常是信任的，因此像呼叫者ID或电子邮件返回地址等信息在许多情况下被视为“来源证明”，即使它们相对容易被伪造。这为可能造成损害的攻击留下了可乘之机。
在本章中，我们将展示如何通过使用加密技术来实现消息完整性，以检测在未受保护的通信通道上发送的欺骗消息或消息篡改。请注意，我们无法希望完全防止消息注入或消息篡改，因为这只能在物理层面进行防御。相反，我们将保证任何这样的行为将被诚实的各方检测到。

# 4.1.2 加密与消息认证

保密性和消息完整性的目标不同，因此实现它们的技术和工具也不同。不幸的是，保密性和完整性经常被混淆并不必要地交织在一起，因此让我们明确一点：==加密通常不会提供任何完整性，并且不能假定加密能够确保消息认证，除非它是专门为此目的而设计的==（这是我们将在第 5.2 节中详细讨论的内容）。

有人可能错误地认为，加密解决了消息认证问题（实际上这是一种常见的错误）。这是由于一种模糊且不正确的推理，即由于密文完全隐藏了消息的内容，因此攻击者不可能以任何有意义的方式修改加密消息。尽管这种推理具有直观吸引力，但它完全是错误的。我们通过展示到目前为止所介绍的所有加密方案都不提供消息完整性来说明这一点。

使用流密码进行加密。考虑一种加密方案，其中发送方基于共享密钥（以及可能的IV）生成伪随机码，并通过将伪随机码与消息进行异或运算来计算密文，例如构造 $(3.17), (3.28) 和 (3.31)$ 以及OFB和CTR模式。在这种情况下，密文非常容易被篡改：翻转密文中的任意一位会导致底层消息中相应的一位也被翻转。因此，给定加密了（可能未知的）消息 $m$ 的密文 $c$ ，则攻击者可以生成一个修改后的密文 $c_{0}$ ，使得 $m_{0} := {Dec}_{k} (c_{0})$ 与 $m$ 相同，但其中特定的一些位被翻转。这种简单的攻击可能会带来严重的后果。例如，假设一个用户要从她的银行账户中转移某个以二进制表示的美元数额。翻转最低有效位的效果是将该数额增加或减少 $1$ 美元，而翻转第 $11$ 个最低有效位的效果则是将该数额增加或减少超过 $1, 000$ 美元！有趣的是，攻击者不一定会得知她是在增加还是减少初始数额，即攻击者不知道她是翻转了 $0$ 还是 $1$ 。但如果攻击者对初始数额有一些部分知识，例如知道它小于 $1, 000$ 美元，那么她所引入的修改就会产生可预测的效果。

需要强调的是，这种攻击并不违反加密方案的保密性。实际上，同样的攻击也适用于一次性密码加密方案，这表明即使具有完美保密性也不足以确保最基本的消息完整性。

使用块密码进行加密。上述攻击利用了翻转密文中的单个位会使底层明文除了相应的位（也被翻转）之外保持不变的事实。人们可能希望使用更为复杂的方式利用块密码的加密方案可以防止这种攻击，例如，如果解密涉及对密文的某个部分 $x$ 进行（强）伪随机置换 $F$ 的逆操作，则如果 $x$ 和 $x_{0}$ 相差一个位，则 $F_{k}^{- 1} (x)$ 和 $F_{k}^{- 1} (x_{0})$ 将是完全不相关的。然而，对密文进行单比特修改仍然可能导致部分可预测的明文更改。例如，在使用ECB模式时，将密文的第 $i$ 块的一个比特翻转只会影响明文的第 $i$ 块，而所有其他块都保持不变。（当然，ECB模式甚至不能保证最基本的保密性，但这与当前讨论无关。）尽管对明文的第 $i$ 块的影响可能无法预测，但更改该块（同时保持其他所有内容不变）可能代表了一种有害攻击。此外，明文块的顺序可以通过仅更改相应的密文块的顺序（而不影响任何块）来更改，并且可以通过删除密文块来截断消息。

对于CBC模式，翻转IV的第 $j$ 位仅更改第一个消息块 $m_{1}$ 的第 $j$ 位（因为 $m_{1} = F_{k}^{- 1} (c_{1}) \oplus I V_{0}$ ，其中 $I V_{0}$ 是修改后的IV）；所有其他明文块保持不变。因此，CBC加密消息的第一个块可以任意修改。我们将在5.1.1节中看到这种简单的攻击可能会带来灾难性的后果。

最后，需要注意的是，我们迄今为止看到的所有加密方案都具有这样的性质，即特定长度的每个字符串都是有效的密文，因此对于攻击者来说，“欺骗”某个通信方代表发送一个正确长度的任意字符串，即使攻击者不知道底层消息是什么，也是微不足道的。在消息完整性的背景下，即使是这种攻击也应该被排除。

# 4.2 消息认证码（MACs）– 定义

我们已经看到，通常情况下，加密并不能解决消息完整性的问题。相反，需要一种额外的机制使通信双方能够知道消息是否被篡改。解决这个问题的正确工具是消息认证码（message authentication code,MAC）。消息认证码的目的是防止攻击者在不被接收方检测到的情况下修改一方发送给另一方的消息，或者注入新消息。与加密的情况类似，只有当通信双方拥有攻击者不知道的某些秘密信息时，才有可能实现这一点（否则，没有什么可以阻止攻击者冒充发送消息的一方）。在这里，我们继续考虑通信双方共享一个秘密密钥的私钥设置。

与私钥加密的情况类似，对于MACs，存在两种规范的应用场景（参见第1.2节）：确保两个通信方之间的完整性（例如，我们早期的用户与她的银行之间的通信示例），或者一个用户在一段时间内与自己通信（例如，我们早期的Web cookie示例，或者一个用户保护他的硬盘内容）。

消息认证码的语法

在正式定义消息认证码的安全性之前，我们先定义什么是MAC以及它是如何使用的。希望进行身份验证通信的两个用户首先需要预先生成和共享一个秘密密钥 $k$ 。当一方想要向另一方发送消息 $m$ 时，她使用共享密钥和消息计算出一个标记 $t$ ，并将消息 $m$ 和 $t$ 发送给另一方。标记是使用标记生成算法 $M a c$ 计算的；因此，重述我们刚才所说的，发送方计算 $t \leftarrow M a c_{k} (m)$ ，并将 $(m, t)$ 传输给接收方。接收到 $(m, t)$ 后，第二方通过运行验证算法 $V r f y$ 来验证 $t$ 是否是消息 $m$ 的有效标记（相对于共享密钥）或不是。这是通过将共享密钥以及消息 $m$ 和标记 $t$ 作为输入的方式来完成的，该验证算法 $V r f y$ 指示给定的标记是否有效。具体地：

定义4.1：消息认证码（或MAC）由三个概率多项式时间的算法 $(G e n, M a c, V r f y)$ 组成，其满足以下条件：

密钥生成算法 $G e n$ 将安全参数 $1^{n}$ 作为输入，并输出一个密钥 $k$ ，其中 $| k | \geq n$ 。
标记生成算法 $M a c$ 将密钥 $k$ 和消息 $m \in {0, 1}^{*}$ 作为输入，并输出一个标记 $t$ 。由于此算法可能是随机的，因此我们将其写为 $t \leftarrow M a c_{k} (m)$ 。
确定性验证算法 $V r f y$ 将密钥 $k$ 、消息 $m$ 和标记 $t$ 作为输入。它输出一个位 $b$ ，其中 $b = 1$ 表示有效， $b = 0$ 表示无效。我们将其写为 $b := V r f y_{k} (m, t)$ 。

需要满足对于每个 $n$ ，对于 $G e n (1^{n})$ 输出的每个密钥 $k$ 和每个 $m \in {0, 1}^{*}$ ，都有 $V r f y_{k} (m, M a c_{k} (m)) = 1$ 。

如果存在一个函数 $λ$ ，对于 $G e n (1^{n})$ 输出的每个 $k$ ，算法 $M a c$ 仅对消息 $m \in {0, 1}^{λ (n)}$ 定义，则称该方案为长度为 $λ (n)$ 的固定长度MAC。

与私钥加密一样， $G e n (1^{n})$ 几乎总是选择一个均匀的密钥 $k \in {0, 1}^{n}$ ，此时我们省略 $G e n$ 。

规范验证。对于确定性消息认证码（即，其中 $M a c$ 是确定性算法），执行验证的规范方法是简单地重新计算标记并检查是否相等。换句话说， $V r f y_{k} (m, t)$ 首先计算 $t^{'} \leftarrow M a c_{k} (m)$ ，然后仅当 $t^{'} = t$ 时输出 $1$ 。即使对于确定性MAC，也有用定义单独的 $V r f y$ 算法来明确区分要发送的消息的身份验证和验证接收到的消息的真实性的语义。

消息认证码的安全性
我们现在定义消息认证码的默认安全性概念。这个定义背后的直觉是，没有有效的攻击者应该能够在任何“新”的消息上生成有效的标记，这些消息之前没有被通信双方之一发送（并进行身份验证）。

与任何安全定义一样，为了形式化这个概念，我们需要定义攻击者的能力以及什么应该被视为方案的“破解”。由于我们只考虑概率多项式时间的攻击者，因此真正的问题是如何模拟攻击者与通信双方的交互。在消息认证的设置中，观察诚实方之间的通信的攻击者可能能够看到那些方发送的所有消息以及它们对应的标记。攻击者也可能能够影响这些消息的内容，无论是直接还是间接地（例如，如果攻击者的外部行为影响了方发送的消息）。例如，在前面的Web cookie示例中，用户自己的操作会影响存储在他计算机上的Cookie的内容。

为了模拟上述情况，我们允许攻击者请求任意消息的标记。形式上，我们给攻击者访问 MAC oracle $M a c k (\cdot)$ 的权限；攻击者可以反复提交任意选择的消息 $m$ 给这个oracle，并且会得到一个标记 $t \leftarrow M a c k (m)$ 作为回报。（对于长度固定的MAC，只能提交正确长度的消息。）

攻击者“破解”方案的条件是，如果它成功输出一个伪造品，即，如果它输出一个消息 $m$ 和一个标记 $t$ ，使得（1）标记 $t$ 是消息 $m$ 的有效标记（即 $V r f y_{k} (m, t) = 1$ ），且（2）诚实方以前没有对 $m$ 进行身份验证（即，攻击者以前没有从其oracle请求消息 $m$ 的标记）。这些条件意味着，如果攻击者向诚实方之一发送 $(m, t)$ ，那么该方将错误地认为 $m$ 是由另一个合法方发送的（因为 $V r f y_{k} (m, t) = 1$ ），即使实际上不是这样。

如果无法被上述方式破解，那么MAC被称为在自适应选择消息攻击下存在性不可伪造的。 “存在性不可伪造”指的是攻击者无法伪造任何消息的有效标记；即使攻击者可以在攻击期间进行适应性选择的消息攻击，也应该保持这种安全性。

上述讨论导致我们考虑以下关于消息认证码 $Π = (G e n, M a c, V r f y)$ 、攻击者 $A$ 和安全参数 $n$ 的实验：

消息认证实验 $M a c - f o r g e_{A, Π} (n)$ :

运行 $G e n (1^{n})$ 以生成密钥 $k$ 。
攻击者 $A$ 获得输入 $1^{n}$ 和访问 $M a c k (\cdot)$ 的oracle权限。攻击者最终输出 $(m, t)$ 。让 $Q$ 表示攻击者 $A$ 提交给其oracle的所有查询的集合。
当且仅当（1） $V r f y_{k} (m, t) = 1$ 且（2） $m \notin Q$ 时，攻击者 $A$ 成功。在这种情况下，实验的输出定义为 $1$ 。

如果没有有效的攻击者能够以非可忽略概率成功执行上述实验，那么MAC就是安全的。

定义4.2：如果对于所有概率多项式时间的攻击者 $A$ ，存在一个可以忽略的函数 $n e g l$ ，使得下面公式成立，则称消息认证码 $Π = (G e n, M a c, V r f y)$ 在自适应选择消息攻击下存在性不可伪造的，或者称其为安全的。

P r [M a c - f o r g e_{A, Π} (n) = 1] \leq n e g l (n)

这个定义是否太严格？上述定义在两个方面都相当严格。首先，定义允许攻击者对其选择的任何消息重复请求标记。其次，如果攻击者能够在以前未经认证的任何消息上输出有效标记，攻击者就被认为已经“破解”了该方案。可能有人认为，定义中的这两个组成部分都不现实且过于严格，因为在实际应用中，诚实的参与方只会对“有意义”的消息进行认证（攻击者可能仅有有限的控制权），而伪造只有在伪造一个“有意义”的消息上的有效标记时才会对系统造成损害。为什么不调整定义以适应这一点呢？

关键点在于，什么构成“有意义”的消息完全取决于应用程序。虽然某些MAC的应用可能只对英语消息进行认证，但其他应用可能对电子表格文件、数据库条目和原始数据进行认证。协议也可以被设计为对任何内容进行认证，实际上某些用户认证协议就是这样做的。通过使MAC的安全定义尽可能强大，我们确保安全的MAC在广泛的目的下都可以应用，而不必担心MAC与特定应用程序语义的兼容性问题。

重放攻击。重放攻击是指攻击者简单地重新发送先前经过认证的消息及其（有效的）标记。上述定义和消息认证码本身并不能防止这种攻击。这并不意味着重放攻击不是一个严重的安全问题！考虑一下这样一种情况：一个用户（比如Alice）向她的银行发送一个请求，请求将$1,000从她的账户转移给另一个用户（比如Bob）。在此过程中，Alice可以计算一个标记并将其附加到请求中，以便银行知道请求是真实的。如果消息认证码是安全的，那么Bob将无法拦截请求并将金额更改为$10,000，因为这将涉及到对未经认证的消息进行有效标记伪造。然而，没有任何方法可以防止Bob将Alice的消息（及其标记）重复发送十次给银行。如果银行接受了这些消息中的每一个，那么最终的结果仍然是将$10,000转移到Bob的账户，而不是期望的$1,000。

MAC不能阻止重放攻击，因为MAC的定义(定义4.1)中并没有将任何“状态”包括在验证算法中(因此每当有效的(m,t)对出现在验证算法中，总是输出1)。然而，对重放攻击的防御(如果这种防御是必要的话),留给了应用层。MAC进行这种结构化定义的原因是，不想假设任何与应用相关的语义；特别地，是否需要将重放的消息作为“有效的”消息，完全由应用程序决定。

有两种常用的防御重放攻击的技术涉及系列号或者时间戳。第一种方法的基本思想是将每个消息 $n$ 都分配一个序列号 $i$ ,则MAC通过连接后的消息 $i | | m$ 来计算。(实际上，不是这么简单，因为连接必须以一种特定的方式完成，这种方式中训 $i | | m$ 唯一地确定 $i$ 和 $m$ 。但是这里略过这一细节。)假设发送者在每条消息附加上独一无二的序列号，接收者追踪所收到的序列号，这样，任意一次成功的重放消息 $m$ 都需要在新的连接信息 $i^{'} | | m$ 上伪造一个有效的MAC 标记，这里 $i^{'}$ 是从未被使用过的。这被MAC的安全性所排除。

使用序列号的缺点是接收者需要存储所接收到的所有序列号(如果通信发生在一个专用会话中，发送者很容易每发送一个消息便增加一次序列号，接收者只需要存储接收到的最高序列号)。为了解决这个问题，可采用时间戳的方式。在这种方式下，发送者将消息发送的时间戳附加到消息上(精确到毫秒),而不是将序列号附上去。当接收者收到消息，它需要检查包含的时间戳是否在可接受的时间区间里。这种方法也有缺陷，需要消息的发送方和接收方有同步的钟表，且在这种情况下，重放攻击仍然可能会发生，只要它足够快。

对重放攻击的进一步讨论超出了本书的范围，读者可以查阅其他有关网络安全的书籍。

# 4.3 构造安全的消息认证码

# 4.3.1 固定长度的 MAC

伪随机函数是构造安全消息认证码的自然工具。直观上，如果标签 $t$ 是通过将伪随机函数应用于消息 $m$ 而获得的，那么在以前未验证的消息上伪造标签需要对手正确猜测在“新”输入点上伪随机函数的值。猜测随机函数在新点上的值的概率为 $2^{- n}$ （如果函数的输出长度为 $n$ ）。对于伪随机函数猜测这样的值的概率仅可能略微更大。

上述想法在构造 4.5 中展示，为短消息提供了安全的固定长度 MAC。在第 4.3.2 节中，我们展示了如何扩展此方法以处理任意长度的消息。在第 4.4、4.5 和 6.3.2 节中，我们探讨了更高效的 MAC 构造方法。

定理 4.6 如果 $F$ 是伪随机函数，则构造 4.5 对于长度为 $n$ 的消息是安全的固定长度 MAC。

CONSTRUCTION 4.5

假设 $F$ 是一个长度保持的伪随机函数。构造一个长度为 $n$ 的消息的固定长度 MAC，具体如下：

Mac：输入一个密钥 $k \in {0, 1}^{n}$ 和一个消息 $m \in {0, 1}^{n}$ ，输出标签 $t := F_{k} (m)$ 。
Vrfy：输入一个密钥 $k \in {0, 1}^{n}$ ，一个消息 $m \in {0, 1}^{n}$ 和一个标签 $t \in {0, 1}^{n}$ ，如果 $t = F_{k} (m)$ ，则输出 $1$ ，否则输出 $0$ 。

这个构造方法的直观思想是，对于一个消息 $m$ ，使用伪随机函数 $F_{k}$ 计算出一个标签 $t$ ，并将 $(m, t)$ 作为消息认证码。因为对于一个伪随机函数 $F$ ，用在一个新的输入上伪造输出的概率非常小，所以这个构造方法是安全的。

我们需要证明对于任何概率多项式时间的攻击者 $A$ ，它成功伪造一个有效的标签的概率是可忽略的。如果 $A$ 可以成功伪造一个 $(m, t)$ ，那么它必须正确地猜测出一个之前从未见过的消息 $m$ 的标签 $t = F_{k} (m)$ 。对于伪随机函数 $F$ ，这个猜测的概率是 $2^{- n}$ ，因此攻击者的成功概率是可忽略的。
证明：与以前基于伪随机函数的方案的分析方式相同，我们首先用真正的随机函数替换伪随机函数，并显示这对于攻击者的成功概率具有有限的影响。然后我们分析使用真正的随机函数时的方案。设 $A$ 是概率多项式时间的攻击者。考虑消息认证码 $\tilde{Π} = (\tilde{G e n}, \tilde{M a c}, \tilde{V r f y})$ ，它与构造 4.5 中的 $Π = (M a c, V r f y)$ 相同，除了在伪随机函数 $F_{k}$ 的位置上使用真正的随机函数 $f$ 。也就是说， $\tilde{G e n} (1^{n})$ 的工作方式是选择一个均匀的 $f \in F u n c_{n}$ ， $\tilde{M a c}$ 计算标签时与 $M a c$ 完全相同，只是将 $F_{k}$ 替换为 $f$ 。

我们展示存在一个可忽略函数 $negl$ 使得

Pr [{Mac-forge}_{A, Π} (n) = 1] - Pr [{Mac-forge}_{A, \tilde{Π}} (n) = 1] \leq negl (n) . (4.1)

为了证明这一点，我们构造一个多项式时间的区分器 $D$ ，该区分器可以访问某个函数 $O$ 的 oracle，并其目标是确定 $O$ 是伪随机函数（即等于 $F_{k}$ ，其中 $k \in {0, 1}^{n}$ 是均匀的）还是随机函数（即等于 $f$ ，其中 $f \in F u n c_{n}$ 是均匀的）。为此， $D$ 模拟 $A$ 的消息认证实验，并观察 $A$ 是否成功在“新”消息上输出有效的标签。如果是，则 $D$ 猜测它的 oracle 是伪随机函数；否则， $D$ 猜测它的 oracle 是随机函数。具体操作如下：

区分器 $D$ ：

给定输入 $1^{n}$ 和一个 oracle $O : {0, 1}^{n} \to {0, 1}^{n}$ ， $D$ 的操作如下：

运行 $A (1^{n})$ 。每当 $A$ 将其 MAC oracle 查询到消息 $m$ （即每当 $A$ 请求消息 $m$ 的标签）时，用以下方式回答此查询：

使用 $O$ 查询 $m$ 并获得响应 $t$ ，将 $t$ 返回给 $A$ 。

当 $A$ 在执行结束时输出 $(m, t)$ ，执行以下操作：

(a) 使用 $O$ 查询 $m$ 并获得响应 $t_{0}$ 。

(b) 如果满足条件：(1) $t_{0} = t$ ，且 (2) $A$ 从未在消息 $m$ 上查询过其 MAC oracle，则输出 $1$ ；否则输出 $0$ 。

显然， $D$ 是多项式时间运行的。如果 $D$ 的 oracle 是一个均匀的 $F_{k}$ ，那么当 $D$ 作为 $A$ 的子例程运行时， $A$ 的视图与在 Mac-forge $_{A}, Π (n)$ 实验中的视图完全相同。此外， $D$ 输出 $1$ 的条件正是 $M a c$ -forge $_{A}, Π (n) = 1$ 。因此，

Pr [D^{F_{k} (.)} (1^{n}) = 1] = Pr [M a c - f o r g e_{A, Π} (n) = 1],

其中 $k \in {0, 1}^{n}$ 是在上述左侧均匀选择的。如果 $D$ 的 oracle 是一个随机函数，那么当 $D$ 作为 $A$ 的子例程运行时， $A$ 的视图与在 Mac-forge $_{A}, e Π (n)$ 实验中的视图完全相同。此外， $D$ 输出 $1$ 的条件正是 $M a c$ -forge $_{A}, e Π (n) = 1$ 。因此，

Pr [D^{f (.)} (1^{n}) = 1] = Pr [M a c - f o r g e_{A, \tilde{Π}} (n) = 1],

其中 $f \in F u n c_{n}$ 是均匀选择的。由于 $F$ 是伪随机函数且 $D$ 是多项式时间运行的，存在可忽略函数 $negl$ ，使得

| Pr [D^{F_{k (.)}} (1^{n}) = 1] - Pr [D^{f (.)} (1^{n}) = 1] | \leq negl (n) .

这意味着方程式 (4.1) 成立。为了完成证明，我们观察到

Pr [{Mac-forge}_{A, \tilde{Π}} (n) = 1] \leq 2^{- n} (4.2),

因为对于任何不属于 $Q$ 的消息 $m$ ， $A$ 未向其 MAC oracle 查询时，标签 $t_{0} = f (m)$ 从 $A$ 的角度来看是均匀分布的（因为所有输入的 $f$ 的值是均匀且独立的）。因此， $A$ 正确猜测 $t_{0}$ （对于任何 $m \notin Q$ ）的概率为 $2^{- n}$ 。

方程式 (4.1) 和 (4.2) 结合在一起表明

Pr [{Mac-forge}_{A}, Π (n) = 1] \leq 2^{- n} + negl (n),

从而完成了定理的证明。

# 4.3.2 扩展到任意长度的 MAC

该文本讨论了构造4.5的局限性，这是一种从伪随机函数构造安全消息认证码（MAC）的方法。该构造只能处理固定长度、而且相当短的消息。在大多数实际应用中，这些限制是不可接受的。我们在这里展示了如何从长度为n的消息的任意固定长度MAC构造处理任意长度消息的MAC。我们所展示的构造并不是非常高效的，不太可能在实践中使用；我们后续小节将看到更有效的构造安全MAC的方法。这里介绍这个构造方法是因为他的简洁和通用。

设 $Π^{^{'}} = (M a c^{^{'}}, V r f y^{^{'}})$ 是一个适用于长度为 $n$ 的消息的安全固定长度MAC。在介绍基于 $Π^{^{'}}$ 构造处理任意长度消息的MAC之前，我们排除了一些简单的想法，并描述了必须防止的一些典型攻击。

第一个想法是将消息 $m$ 解析为 $n$ 比特块 $m_{1}, . . ., m_{d}$ ，并分别对每个块进行认证，即计算 $t_{i} := M a c_{k}^{^{'}} (m_{i})$ 并输出 $< t_{1}, . . ., t_{d} >$ 作为标签。这可以防止对手在未被检测到的情况下发送任何以前未经身份验证的块。然而，它并不能防止块重排攻击，其中攻击者对已经认证的消息中的块进行重新排列。具体来说，如果 $< t_{1}, t_{2} >$ 是消息 $m_{1}, m_{2}$ 的有效标签（其中 $m_{1} \neq m_{2}$ ），那么攻击者可以在新消息 $m_{2}, m_{1}$ 上构造有效标签 $< t_{2}, t_{1} >$ ，这是Definition 4.2所不允许的。
我们可以通过在每个块的旁边认证一个块索引来防止上述攻击。也就是说，我们现在计算 $t_{i} = M a c_{k}^{^{'}} (i ∥ m_{i})$ ，并输出 $< t_{1}, . . ., t_{d} >$ 作为标签（现在 $| m_{i} | < n$ ）。这并不能防止截断攻击，攻击者可以简单地从消息末尾删除块（并删除相应的标签块）。
我们可以通过在每个块旁边认证消息长度来防止截断攻击。也就是说，我们现在计算 $t_{i} = {Mac}_{k}^{'} (ℓ | | i |) m_{i})$ ，其中 $ℓ$ 表示消息长度（以比特为单位）。通过这种方式，我们可以防止攻击者截断消息而不被检测到。注意，将消息长度作为单独的块进行认证是不起作用的。然而，这种方案容易受到“混合和匹配”攻击的影响，其中攻击者组合来自不同消息的块。例如，如果攻击者分别获得消息 $m = m_{1}, . . ., m_{d}$ 和 $m^{^{'}} = m_{1}^{^{'}}, . . ., m_{d}^{^{'}}$ 的标签 $< t_{1}, . . ., t_{d} >$ 和 $< t_{1}^{^{'}}, . . ., t_{d}^{^{'}} >$ ，则它可以在消息 $m_{1}, m_{2}^{^{'}}, m_{3}^{^{'}}, m_{4}^{^{'}}, . . .$ 上输出有效标签 $< t_{1}, t_{2}^{^{'}}, t_{3}, t_{4}^{^{'}}, . . . >$ 。

我们可以通过在每个块中还包括一个随机的“消息标识符”来防止最后一种攻击，从而防止攻击者组合来自不同消息的块。这将导致Construction 4.7。（该方案仅处理长度小于 $2^{n / 4}$ 的消息，但这是一个指数上界。）

# 4.4 CBC-MAC

定理4.6和4.8表明，可以从具有块长度 $n$ 的伪随机函数构造出适用于任意长度消息的安全消息认证码。这原则上证明了可以从块密码构造安全MAC。不幸的是，由此得到的构造非常低效：为了在长度为 $d n$ 的消息上计算标签，块密码需要评估 $4 d$ 次，并且标签长度超过 $4 d n$ 比特。幸运的是，有更有效的构造方法可用。我们首先探讨一种仅依赖于块密码的构造方法。

# 4.4.1 基本构造方法

CBC-MAC是最早被标准化的消息认证码之一。给出了一种基本版本的CBC-MAC，它是在认证任何固定长度的消息时都是安全的，这被称为Construction 4.9。（请参见图4.1。）我们需要注意的是，当需要认证不同长度的消息时，这种基本方案在一般情况下并不安全；请参见下面的进一步讨论。

定理4.10 如果 $ℓ$ 是一个多项式，且F是一个伪随机函数，则Construction 4.9对长度为 $ℓ (n) \cdot n$ 的消息是一个安全MAC。

定理4.10的证明比较复杂。在下一节中，我们将证明一个更一般的结果，从而得出上述定理。尽管Construction 4.9可以显然地扩展以处理不同长度的消息，但只有当被认证的消息的长度是固定的并且由发送者和接收者事先达成协议时，才能保证安全性（参见练习4.13）。这种构造与Construction 4.5相比，可以认证更长的消息，是其优势所在。与Construction 4.7相比，基本的CBC-MAC更加高效，对于长度为 $d n$ 的消息，只需要d个块密码评估，并且标签长度为n。
CBC-MAC vs. CBC-mode encryptionCBC-MAC和CBC模式加密有些相似，但也存在一些重要的区别：

目的不同：CBC-MAC的目的是在保证消息完整性的同时生成一个固定长度的认证标签，而CBC模式的目的是加密消息以保护其机密性。
输出不同：CBC-MAC的输出是一个固定长度的认证标签，而CBC模式的输出是加密后的消息。
加密方式不同：CBC-MAC使用密钥和初始化向量对消息进行加密，并将最后一个加密块作为标签输出。而CBC模式将前一个加密块与当前消息块进行异或操作，并使用密钥对结果进行加密。
安全性分析不同：CBC-MAC的安全性建立在伪随机函数的基础上，而CBC模式的安全性建立在伪随机密码本的基础上。

总的来说，CBC-MAC和CBC模式加密虽然有些相似，但是它们的目的、输出、加密方式和安全性分析都存在差异。因此，在设计安全通信系统时，需要根据需要选择正确的加密模式和认证方案来保护消息的机密性和完整性。

Secure CBC-MAC for arbitrary-length messages. 为了以可证明安全的方式处理任意长度消息，我们可以对Construction 4.9进行两种修改。这里为了简单起见，我们假设所有被认证的消息长度都是n的倍数，并且Vrfy拒绝任何长度不是n的倍数的消息。在下一节中，我们将处理消息长度可以是任意长度的更一般情况。

第一种修改是使用一个不同的IV来处理每个消息块。具体地，对于一个消息 $M = M_{1} ‖ M_{2} ‖ \dots ‖ M_{d}$ ，我们可以使用一个随机的IV $I V_{0}$ ，并将其与第一个消息块 $M_{1}$ 进行异或操作，然后使用密钥对结果进行加密，得到第一个加密块 $T_{1}$ 。接下来，我们将 $T_{1}$ 与第二个消息块 $M_{2}$ 进行异或操作，并使用密钥对结果进行加密，得到第二个加密块 $T_{2}$ 。重复这个过程，直到处理完所有的消息块，最后将最后一个加密块作为认证标签。

第二种修改是在每个消息块的末尾添加一个填充块。具体地，对于一个消息 $M = M_{1} ‖ M_{2} ‖ \dots ‖ M_{d}$ ，我们可以将每个消息块 $M_{i}$ 的末尾填充到长度为n的倍数，将填充块与消息块进行异或操作，然后使用密钥对结果进行加密，得到加密块 $T_{i}$ 。最后，将最后一个加密块作为认证标签。

这两种修改方法都可以证明是安全的，并且可以处理任意长度的消息。在实际应用中，使用哪种方法取决于具体的需求和限制。

# 4.5 GMAC和Poly1305

CBC-MAC的一个缺点是它需要对被认证消息的长度进行线性数量的密码学运算（具体来说，是块密码的评估）。在这里，我们介绍两种（相关的）构造安全MAC的方法，它们可以更加高效。这些MAC已经被多个互联网标准采用。
我们在4.5.1节中提出了一个构建安全MAC的一般范式，然后在4.5.2节中分别介绍了该范式的两个具体实现：GMAC和Poly1305。

好的，让我更详细地介绍一下GMAC和Poly1305。

# 4.5.1GMAC

GMAC（Galois/Counter Mode MAC）是一种基于Galois域的认证加密模式，它使用一个伪随机数生成器（PRG）生成的密钥流对消息进行加密，并使用乘法来计算MAC。GMAC的安全性建立在GCM（Galois/Counter Mode）加密模式的安全性基础上，GCM是一种同时提供认证和加密的加密模式。

GMAC的认证标签计算方式如下：

初始化一个计数器ctr为0。
对于每个n比特的消息分组 $M_{1}, M_{2}, . . ., M_{d}$ ，使用PRG生成一个n比特的密钥流 $K_{1}, K_{2}, . . ., K_{d}$ 。
对于每个密钥流 $K_{i}$ 和计数器值ctr，计算 $K_{i} \cdot x^{c t r}$ ，其中 $x$ 是Galois域中的一个固定元素。
将所有乘积结果进行异或操作，得到最终的认证标签。

其中，步骤3中的乘法是Galois域上的乘法，它可以高效地实现为位运算和异或操作。GMAC的优点是可以在硬件加速器中高效地实现，且在保证安全性的同时具有高性能。

# 4.52Poly1305

Poly1305是一种使用128位密钥和128位消息块的认证算法，它基于多项式算术，可以在软件中高效地实现。Poly1305的安全性建立在Diffie-Hellman问题的难度上。

Poly1305的认证标签计算方式如下：

使用一个128位密钥将消息分成若干个128位的消息块。
初始化一个128位的多项式 $H$ 为0。
对于每个消息块 $M_{i}$ ，将其与一个预定义的常数 $r$ 进行结合，并使用密钥对结果进行加密，得到一个128位的加密结果 $E_{i}$ 。
将加密结果 $E_{i}$ 与多项式 $H$ 相加，并对结果取模，得到一个新的多项式 $H^{'}$ 。
重复步骤3和4，直到处理完所有的消息块。
将多项式 $H^{'}$ 与另一个128位的常数 $s$ 相结合，并对结果进行取模，得到最终的认证标签。

Poly1305的优点是可以在软件中高效地实现，且具有较高的安全强度。它被广泛用于一些加密库中，如libsodium。

总的来说，GMAC和Poly1305都是高效且安全的MAC算法，可以根据具体的需求和限制选择使用。

编辑

上次更新: 2025/04/01, 01:48:12

← PChapter 3:rivate-Key Encryption Chapter 5:CCA-Security and Authenticated Encryption→