Chapter 4 消息鉴别码¶

引言

消息的私密性和完整性有着完全不同的目标，加密并未解决消息鉴别的问题，因此需要额外的机制使得通信各方了解消息是否被篡改，即 消息鉴别码（message authentication code）。

消息鉴别码的目的是阻止敌手进行不被检测到的对消息的修改。在加密情况下，只有在通信各方都掌握了敌手不可知的秘密时才可能实现（否则，没有办法来阻止对手伪装某一方来发送信息），这里将继续考虑双方共享密钥情形。

1 消息鉴别码的定义¶

消息鉴别码（MAC）是一个概率多项式时间算法的三元组 $\text{(Gen, Mac, Vrfy)}$，满足：
1. 密钥产生算法 $\text{Gen}$：$k \leftarrow \text{Gen}(1^n)$，$|k| \geq n$
2. 标记生成算法 $\text{Mac}$：$t \leftarrow \text{Mac}_k(m)$，$m \in \{0,1\}^*$
3. 校验算法 $\text{Vrfy}$：$b := \text{Vrfy}_k(m,t)$，$b=1$ 意味着有效，$b=0$ 则无效
对于每一个 $n$，$\text{Gen}(1^n)$ 输出的每一个$k$，以及每一个$m \in \{0,1\}^*$，都有$\text{Vrfy}(m, \text{Mac}_k(m)) = 1$。
如果 $\text{(Gen, Mac, Vrfy)}$ 满足：对 $\text{Gen}(1^n)$ 输出的每一个$k$，算法 $\text{Mac}_k$ 仅对消息 $m \in \{0,1\}^{l(n)}$ 有定义，且 $\text{Vrfy}_k$ 在任意 $m \notin \{0,1\}^{l(n)}$ 时输出 0，则称 $\text{(Gen, Mac, Vrfy)}$ 是一个固定长度的消息鉴别码（MAC），其消息长度为 $l(n)$

消息鉴别码实验 $\text{Mac-forge}_{\mathcal{A},\Pi}(n)$

运行 $\text{Gen}(1^n)$ 产生一个随机密钥 $k$
敌手被给予输入值 $1^n$，并能访问预言机 $\text{Mac}_k(\cdot)$，最后输出一对 $(m,t)$ 的值，并用 $\mathcal{Q}$ 表示所有 $\mathcal{A}$ 对预言机的询问集合
实验的输出结果为 $1$，当且仅当：$\text{Vrfy}(m,t)=1$，$m\notin \mathcal{Q}$

如果没有敌手能在上述实验中，以不可忽略的概率成功，则认为 MAC 是安全的。

一个消息鉴别码 $\Pi = (\text{Gen}, \text{Mac}, \text{Vrfy})$，如果对所有的多项式时间敌手 $\mathcal{A}$，存在一个可忽略函数 $\text{negl}$，满足 $$ \Pr[\text{Mac-forge}_{\mathcal{A},\Pi}(n) = 1] \leqslant \text{negl}(n) $$ 则它是适应性选择消息攻击下存在性不可伪造的，或者说消息鉴别码是安全的。

2 构造安全的消息鉴别码¶

A fixed-length MAC from any pseudorandom function

假设 $F$ 是一个伪随机函数，长度为 $n$ 的消息的固定长度的 MAC 定义如下：

$\text{Gen}$：输入参数 $1^n$，均匀随机地选择 $k \leftarrow \{0,1\}^n$
$\text{Mac}$：输入密钥 $k \in \{0,1\}^n$ 和消息 $m \in \{0,1\}^n$，输出标记 $t := F_k(m)$，如果$|m| \neq |k|$则没有输出
$\text{Vrfy}$：输入密钥 $k \in \{0,1\}^n$，消息 $m \in \{0,1\}^n$，以及标记 $t \in \{0,1\}^n$，当且仅当 $t \stackrel{?}{=} F_k(m)$ 时输出1，如果 $|m| \neq |k|$输出 0

如果 $F$ 是一个伪随机函数，那么上述构造方法是长度为 $n$ 的消息的定长 MAC，这种 MAC 是在适应性选择消息攻击下存在性不可伪造的。

将定长消息的 MAC 扩展到变长消息：

A MAC for arbitrary-length messages from any fixed-length MAC

假设 $Π' = (\text{Gen}', \text{Mac}', \text{Vrfy}')$ 是针对长度为 $n$ 的消息的定长 MAC。对 MAC 的定义如下：

$\text{Gen}$：同 $\text{Gen}'$。
$\text{Mac}$：输入密钥 $k \in \{0,1\}^n$ 和消息 $m \in \{0,1\}^*$，消息长度 $l < 2^{\frac{n}{4}}$，将 $m$ 分成 $d$ 个分块 $m_1\cdots, m_d$，每个长度为$n/4$。（必要时用 0 填充最后一个分块。）然后，选择一个随机的标识符 $r \leftarrow \{0,1\}^{\frac{n}{4}}$。

对 $i = 1, \cdots, d$，计算标记 $t_i \leftarrow \text{Mac}'_k(r\mathbin\|i\mathbin\|l\mathbin\|m_i)$，其中，$i,l$ 被唯一地编码成长度为 $n/4$ 的字符串。最后，输出标记 $t := \langle r, t_1, \cdots, t_d \rangle$。
$\text{Vrfy}$：输入密钥 $k \in \{0,1\}^n$ 和消息 $m \in \{0,1\}^*$，消息的长度 $l < 2^{\frac{n}{4}}$，标记 $t = \langle r, t_1, \cdots, t_d \rangle$，将 $m$ 分成 $d$ 个分块 $m_1,\dots,m_d$，每个分块长度为 $n/4$。（必要时用 0 填充最后一个分块）。当且仅当 $d' = d$，且对于 $1 \leq i \leq d$ 时，$\text{Vrfy}'_k(r\mathbin\|i\mathbin\|l\mathbin\|m_i, t_i) = 1$，输出1。

如果 $Π'$ 是一个长度为 $n$ 的消息的安全定长 MAC，那么上述构造方法所得到的 MAC 是在适应性选择消息攻击下存在性不可伪造的。

3 CBC-MAC¶

引言

上一节的内容表明：在仅给定一个定长输入的伪随机函数的情况下，可以构造（任意长度的消息）安全的消息鉴别码，这原则上说明 MAC 能通过分组加密构造，但该构造方法非常低效：为了计算消息长度为 $l·n$ 的 MAC 标记，需要应用分组加密 $4l$ 次，MAC 标记长度为 $(4l + 1)n$ 比特。因此引入 CBC-MAC。

Basic CBC-MAC (for fixed-length messages)

令 $F$ 是一个伪随机函数，固定的长度函数 $l$。基本的 CBC-MAC 构造如下：

$\text{Gen}$：输入 $1^n$，均匀随机选择 $k \leftarrow \{0,1\}^n$
$\text{Mac}$：输入一个密钥 $k \in \{0,1\}^n$ 和长度为 $l(n)·n$ 的消息 $m$，完成如下（令 $l = l(n)$）：

(1) 将 $m$ 解析分块 $m_1,\cdots, m_l$，每个 $m_i$ 的长度为 $n$，并令 $t_0 := 0^n$

(2) 对 $i = 1,\cdots,l$，令 $t_i = F_k(t_{i-1} \oplus m_i)$。输出 $t_l$ 作为标记
$\text{Vrfy}$：输入一个密钥 $k \in \{0,1\}^n$，长度为 $l(n)·n$ 的消息 $m$，和长度为 $n$ 的标记 $t$，当且仅当 $t \stackrel{?}{=} \text{Mac}_k(m)$ 时，输出 1

令 $l$ 是一个多项式，如果 $F$ 是一个伪随机函数，上述构造方法是一个长度为 $l(n)·n$ 的消息的定长 MAC。该 MAC 是适应性选择消息攻击下存在性不可伪造的。

CBC-MAC 与 CBC 加密模式的比较

CBC 加密模式使用一个随机初始向量（IV），这对安全性来说非常重要。与此相反，CBC-MAC 不用 IV（或者说 IV 为固定值，$IV = 0^n$），这对其安全性来说是十分重要的。确切地说，CBC-MAC 使用随机的 IV 反而是不安全的。
在 CBC 模式加密中，所有的分块 $t_i$（在 CBC 模式加密中被叫做 $c_i$）都被加密算法作为密文的一部分输出，但是在 CBC-MAC 中只输出最后分块。这看起来是技术上的差别，基于这一事实：在加密中，所有的分块都要输出以进行解密，但是对 MAC 而言这是不必要的，而且 CBC-MAC 输出所有分块时反而是不安全的。

为了得到可变长度消息 CBC-MAC 的安全版本，可对上述构造方法进行的修改，下面三种办法能被证明是安全的：

对长度为 $l$ 的输入消息应用伪随机函数（分组加密）来获得一个密钥 $k_l$（令 $k_l := F_k(l)$），然后使用密钥 $k_l$ 计算基本 CBC-MAC。这确保了不同的（独立计算的）密钥用于不同长度的消息鉴别
预先考虑长度为 $|m|$ 的消息（记为 $n$ 比特字符串），然后对该消息计算出基本 CBC-MAC。注意将分块的长度附加到消息末尾是不安全的。
改变方案，这样生成两个不同的密钥，$k_1 \leftarrow \{0,1\}^n$ 和 $k_2 \leftarrow \{0,1\}^n$。然后，鉴别消息 $m$，首先使用 $k_1$ 计算出 $m$ 的基本 CBC-MAC，记为 $t$，然后输出结果 $\hat{t} := F_{k_2}(t)$。

第三种方案有优势，因为在计算 MAC 之前不用知道消息的长度。它的劣势是需要两份密钥。然而，以伪随机函数的两个额外应用为代价，可以存储单一的密钥 $k$，并在开始计算前推导出 $k_1 = F_k(1)$ 和 $k_2 = F_k(2)$。

4 构造 AE 方案¶

$\text{CCA}$不可区分实验$\text{PrivK}_{\mathcal{A},\Pi}^{\text{cca}}(n)$

通过运行 $\text{Gen}(1^n)$ 生成一个密钥 $k$
敌手 $\mathcal{A}$ 被指定输入 $1^n$，可使用预言机 $\text{Enc}_k(\cdot)$ 和 $\text{Dec}_k(\cdot)$，它输出一对长度相等的消息 $m_0, m_1$
随机选择比特 $b \leftarrow \{0,1\}$，则计算密文 $c \leftarrow \text{Enc}_k(m_b)$ 并将其提供给 $\mathcal{A}$，我们把 $c$ 叫做挑战密文
敌手 $\mathcal{A}$ 继续使用预言机 $\text{Enc}_k(\cdot)$ 和 $\text{Dec}_k(\cdot)$，但是不允许用挑战密文本身来问询 $\text{Dec}_k(\cdot)$，最终，$\mathcal{A}$ 输出一个比特 $b'$
如果 $b' = b$，实验的输出为 1，否则输出 0

一个对称密钥加密方案 $\Pi$ 满足如下条件：对所有的概率多项式时间敌手$\mathcal{A}$，存在一个可忽略的函数 $\text{negl}$，使得

\[ \Pr\left[\text{PrivK}_{\mathcal{A},\Pi}^{\text{cca}}(n) = 1\right] \leq \frac{1}{2} + \text{negl}(n) \]

则称其为选择密文攻击条件下不可区分加密（或者是 CCA 安全的）。
CCA 安全具有不可延展性：如果敌手试图去修改一个指定的密文，结果要么是一个非法密文，要么是一个和原明文没有任何关系的明文的密文。

不可伪造加密实验 $\text{Enc-Forge}_{\mathcal{A},\Pi}(n)$

通过运行 $\text{Gen}(1^n)$ 生成一个密钥 $k$
敌手 $\mathcal{A}$ 被指定输入 $1^n$，可使用预言机 $\text{Enc}_k(\cdot)$，输出密文 $c$.
令 $m := \text{Dec}_k(c)$, 用 $\mathcal{Q}$ 表示 $\mathcal{A}$ 向其加密预言机发起的所有查询构成的集合，当且仅当 $m \neq \perp$ 且 $m \notin \mathcal{Q}$ 时输出为 1

若对于所有概率多项式时间敌手 $\mathcal{A}$，都存在一个可忽略函数 $\text{negl}$，使得：

\[ \Pr[\text{Enc-Forge}_{\mathcal{A},\Pi}(n) = 1] \leq \text{negl}(n) \]

则称私钥加密方案 $\Pi$ 是不可伪造的。
若某私钥加密方案同时满足CCA安全与不可伪造，则该方案是一个认证加密（authenticated encryption, AE）方案。

Previous Attempts

Encrypt-and-authenticate

\[ Enc_m = <\text{Enc}_{k_E}(m), \text{Mac}_{k_M}(m)> \]

在这种方法中，加密与消息认证是独立进行的，MAC 并不保证任何保密性，因此 $\text{Mac}_{k_M}(m)$ 有可能向窃听者泄露关于 $m$ 的信息。
Authenticate-then-encrypt

\[ \text{Enc}_k(m) \leftarrow \text{Enc}_{k_E}\left(m \mathbin{\|} \text{Mac}_{k_M}(m)\right) \]

其解密算法 $\text{Dec}'_{k_E,k_M}(c)$ 如下：
1. 计算 $\tilde{m} := \text{Dec}_{k_E}(c)$，若检测到填充错误，返回“bad padding”并终止
2. 将 $\tilde{m}$ 解析为 $m\|t$，若 $\text{Vrfy}_{k_M}(m,t) = 1$，则返回 $m$；否则输出“authentication failure”
由于攻击者能够区分这两种错误消息，故可以通过 POA 攻破该方案。

最终我们选择的方案是 Encrypt-then-authenticate，具体构造如下。

A generic construction of an authenticated encryption scheme

令 $\Pi_E = (\text{Gen}_E, \text{Enc}, \text{Dec})$ 是一个对称密钥加密方案，并令 $\Pi_M = (\text{Gen}_M, \text{Mac}, \text{Vrfy})$ 是一个消息鉴别码。定义一个加密方案如下 $(\text{Gen}^\prime, \text{Enc}^\prime, \text{Dec}^\prime)$：

$\text{Gen}^\prime$：输入参数 $1^n$，运行 $\text{Gen}_E(1^n)$ 和 $\text{Gen}_M(1^n)$，分别得到密钥 $(k_E, k_M)$
$\text{Enc}^\prime$：输入密钥 $(k_E, k_M)$ 和明文消息 $m$，计算 $c \leftarrow \text{Enc}_{k_E}(m)$ 和 $t \leftarrow \text{Mac}_{k_M}(c)$，并输出密文 $\langle c, t \rangle$
$\text{Dec}^\prime$：输入密钥 $(k_E, k_M)$ 和密文 $\langle c, t \rangle$，先检查 $\text{Vrfy}_k(c, t) \stackrel{?}{=} 1$ 是否成立，如果是，则输出 $\text{Dec}_{k_E}(c)$，否则输出 $\perp$

如果 $\Pi_E$ 是一个 CPA 安全的对称密钥加密方案，且 $\Pi_M$ 是 Strong-MAC，那么上述构造方案是一个 AE 安全的对称密钥加密方案。

证明

设 $\text{ValidQuery}$ 表示 $\mathcal{A}$ 向其解密预言机提交了一个新且有效的密文 $\langle c,t \rangle$，即满足 $\text{Vrfy}_{k_M}(c,t) = 1$ 的密文，则有：

引理

$Pr[\text{ValidQuery}]$ 是可忽略函数。

直观地，这是由于如果事件 $\text{ValidQuery}$ 发生，那么敌手伪造了新消息 $c$ 的有效标记 $t$。正式地，假设 $q(\cdot)$ 是一个多项式，该多项式的上界是 $\mathcal{A}$ 对解密预言机查询的次数，考虑敌手 $\mathcal{A}_M$ 攻击消息鉴别码 $\Pi_M$（即运行实验 $\text{Mac-forge}_{\mathcal{A}_M, \Pi_M}(n)$）：

敌手 $\mathcal{A}_M$

$\mathcal{A}_M$ 输入参数为 $1^n$，并能访问预言机 $\text{Mac}_{k_M}(\cdot)$

均匀随机地选择 $k_E \leftarrow \{0,1\}^n$ 和 $i \leftarrow \{1,\cdots,q(n)\}$
输入参数 $1^n$，运行 $\mathcal{A}$，当 $\mathcal{A}$ 对消息 $m$ 做加密预言机问询时，按下面的方式进行回答：
1. 计算 $c \leftarrow \text{Enc}_{k_E}(m)$
2. 对 MAC 预言机做问询 $c$，并接收响应值 $t$，返回 $\langle c,t \rangle$到$\mathcal{A}$
挑战密文也按照同样的方式进行准备（随机选择一个比特位 $b \leftarrow \{0,1\}$，对消息 $m_b$ 进行加密）。

当 $\mathcal{A}$ 对密文 $\langle c,t \rangle$ 做出一个解密预言机问询时，按照下面的方式进行回答：
1. 如果 $\langle c,t \rangle$ 是之前对消息 $m$ 所做的加密预言机问询的回应，那么返回 $m$
2. 如果这是第 $i$ 次使用新的 $c$ 值对解密预言机的问询，输出 $\langle c,t \rangle$ 并停止
3. 否则，输出 $\perp$

本质上来说，$\mathcal{A}_M$ 的策略是猜测 $\mathcal{A}$ 的第 $i$ 次新解密查询是 $\text{ValidQuery}$，若此时 $\langle c,t \rangle$ 恰好是 $\text{ValidQuery}$，则 $\mathcal{A}_M$ 输出该 $\langle c,t \rangle$，从而在 $\text{Mac-forge}$ 实验中成功。

若 $\text{ValidQuery}$ 发生，设它对应 $\mathcal{A}$ 的第 $j$ 次新解密查询（$j \in \{1,\dots,q(n)\}$），$\mathcal{A}_M$ 选的 $i$ 恰好等于 $j$ 的概率是 $\frac{1}{q(n)}$，故：

\[ \Pr[\text{Mac-forge}_{\mathcal{A}_M, \Pi_M}(n) = 1] \geq \Pr[\text{ValidQuery}] \times \frac{1}{q(n)} \]

不可伪造实验中，攻击者成功的概率 = $\Pr[\text{ValidQuery}]$，而 $\Pr[\text{ValidQuery}] = \text{negl}(n)$，因此攻击者在不可伪造实验中成功的概率可忽略，该方案满足不可伪造性。

引理

存在一个可忽略的函数$\text{negl}$，满足 $$ \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A}, \Pi}^{\text{cca}}(n)=1 \land \text{ValidQuery}\right] \leq \frac{1}{2}+\text{negl}(n) $$

现在使用 $\Pi_E$ 的 CPA 安全，令 $\mathcal{A}$ 的假设保持不变，考虑下述敌手 $\mathcal{A}_E$ 使用选择明文攻击的方法对 $\Pi_E$ 进行攻击：

敌手$\mathcal{A}_E$

$\mathcal{A}_E$ 的输入为 $1^n$，访问预言机 $\operatorname{Enc}_k(\cdot)$

均匀随机选择 $k_2 \leftarrow \{0,1\}^n$
以输入参数 $1^n$ 运行 $\mathcal{A}$，当 $\mathcal{A}$ 对消息 $m$ 做出一个加密预言机询问时，按照下面的方式进行回答：
1. 对加密预言机做询问 $m$，并得到应答 $c$
2. 计算 $t \leftarrow \operatorname{Mac}_{k_2}(c)$，并返回 $\langle c, t \rangle$ 给 $\mathcal{A}$；
当 $\mathcal{A}$ 对密文 $\langle c, t \rangle$ 做出一个解密预言机询问时，按照下面的方式进行回答：
1. 如果 $\langle c, t \rangle$ 是之前对 $m$ 加密预言机询问的应答，那么返回 $m$
2. 否则，输出 $\perp$
当 $\mathcal{A}$ 输出消息 $(m_0, m_1)$ 时，输出同样的消息接收一个挑战密文 $c$ 作为应答。计算 $t \leftarrow \operatorname{Mac}_{k_2}(c)$，并将 $\langle c, t \rangle$ 作为挑战密文返回给 $\mathcal{A}$。如上所述继续回答 $\mathcal{A}$ 的预言机询问
输出与 $\mathcal{A}$ 的输出一样的比特 $b'$

如果 $\text{ValidQuery}$ 事件不发生，则 $\mathcal{A}$ 做出的任何解密询问的正确应答是 $\perp$，那么 $\mathcal{A}$ 作为 $\mathcal{A}_E$ 的子例程的视图概率分布与 $\mathcal{A}$ 在实验 $\operatorname{PrivK}_{\mathcal{A},\Pi}^{\text{cca}}(n)$ 中视图的概率分布是相同的，则有：

\[ \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A}_E,\Pi_E}^{\text{cpa}}(n)=1 \land \overline{\text{ValidQuery}}\right] = \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A},\Pi}^{\text{cca}}(n)=1 \land \overline{\text{ValidQuery}}\right] \]

\[ \begin{aligned} \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A}_E,\Pi_E}^{\text{cpa}}(n)=1\right] &\geqslant \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A}_E,\Pi_E}^{\text{cpa}}(n)=1 \land \overline{\text{ValidQuery}}\right] \\ &= \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A},\Pi}^{\text{cca}}(n)=1 \land \overline{\text{ValidQuery}}\right]_{\circ} \end{aligned} \]

因为 $\Pi_E$ 是 CPA 安全的，那么就存在一个可忽略函数 $\text{negl}$，满足 $\operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A}_E,\Pi_E}^{\text{cpa}}(n)=1\right] \leqslant \frac{1}{2}+\text{negl}(n)$，所以该加密方案是 CCA 安全的，证毕。