02 消息认证码 · DennyQi's Log

在上一章里当我们讨论“安全(security)”时，其实我们指的是消息的保密性(secrecy)。消息具有保密性，是指具有防止被一个窃听者得知其内容的能力。但有时相比于保密性，我们更在意消息的真实性(authetication)。例如在网购时，或许商家并不在意顾客的订单是否泄露给某些窃听者，而更关心订单的来源以及内容是否被恶意篡改过。保密性和真实性作为安全的两个方面实际上并不具有实际关联，我们之前所讨论的加密(encryption)对保护消息真实性没有任何实质的帮助，它确实能够通过不让敌手知道密文的含义而只能做出不基于文本的修改，但并不为“监测消息是否被修改过”这一目的做出任何贡献。很多时候，只要篡改消息的一个二进制位就有可能彻底改变消息的本意。

消息认证码(Message Authentication Codes, MACs)

我们希望发送方给接收方发送一条消息时，接收方能够判定接收到的消息是否经过了篡改。要能实现这一点，发送方和接收方肯定要提前掌握某些敌手所没有的信息。能实现这一点的办法依然是“私钥”。所以我们依然假设消息的发送方和接收方之间提前约定好了一个私钥 $k$ 。注意，在接下来的讨论中，我们不再关心保密性。我们之后会再来解决如何同时解决保密性和真实性的问题。在这里，私钥 $k$ 不再是用来做加密的，而是用来完成真实性验证的工作的。

我们设计这样一个方案：发送方和接收方提前约定了私钥 $k$ ，一个程序 $\text{Mac}$ 基于 $k$ 和要发送的消息 $m$ 生成一个字符串 $t:=\text{Mac}_k(m)$ ， $t$ 称为标签(tag)，或消息认证码(Mac)。注意，程序 $\text{Mac}$ 可能是确定性的，可能是非确定性的。接收方运行一个验证程序 $\text{Vrfy}$ ，输入 $m,t$ 输出 $t$ 是否是一个合法的标签（0或1）。我们要求 $\text{Vrfy}_k(m,\text{Mac}_k(m))=1$ 必须始终成立。可以看出，接收方就是通过 $\text{Vrfy}$ 的输出来判断消息真实性的。我们把上述方案称为MAC方案。

如果 $\text{Mac}$ 是一个确定性的程序，那么 $\text{Vrfy}$ 的最简单也最标准的实现方式就是再次运行 $\text{Mac}$ 然后比较两次得到的标签，标签合法当且仅当两次的输出相同。这称为标准验证(canonical verification)。如果 $\text{Mac}$ 不是确定性的，那么一个消息能够对应多个可能的标签，此时标准验证是不可行的，需要特别设计 $\text{Vrfy}$ 。

MAC方案的安全性

如何定义一个MAC方案是否安全(secure)呢？由于我们不对保密性做任何假设，因此我们应当假设敌手总是能够截获已发送的消息明文以及对应的标签，这意味着敌手实际上拥有选择任何明文并得知其标签的能力。基于此，如果敌手能够生成一个从未发送过的消息的标签，那么当它把这条消息连同敌手自己生成的标签发送给接收方时，消息的来源就无法辨别，敌手就成功破解了这一MAC方案。所以我们可以基于以下实验定义MAC方案的安全性：给定 $n$ ， $\text{Gen}$ 生成了长度为 $n$ 的密钥 $k$ ；把密钥 $k$ 交给一个 $\text{Mac}$ oracle，输入密钥和任意明文会吐出对应的标签；敌手始终可以选择任意明文丢给oracle，得到对应的标签，这个过程最多重复多项式次；最终，如果敌手能够对于任何一个它从未询问过oracle的消息 $m$ 给出一个标签 $t$ ，使得 $\text{Vrfy}(m,t)$ 输出 $1$ ，就称敌手成功。如果敌手成功的概率 $\leq \text{negl}(n)$ ，就称当前MAC是不可伪造的(unforgeable)，也即这一MAC方案是安全的。

必须指出，以上MAC方案的安全性定义是不针对重放攻击(replay attacks)的。想象发送方发过 $(m,t)$ ，那么敌手只需重复发送 $(m,t)$ ，接收方就完全不能判断消息来源。这很多时候是危险的，例如网购时顾客下单了一次，敌手做重放攻击九次，店家就要顾客交十倍的钱。这是由于MAC的定义中不涉及任何关于状态的量(it is stateless)。以后我们会看到，一些能够保证通信双方同步(synchronized)的方案可以缓解这一问题。

另一方面，如果标签的生成程序是非确定性的，那么以上安全性的定义中也没有排除敌手关于已发送过的消息生成了另一个不同的合法标签的情况。为了把这一情形考虑在内，可以在安全性的定义中把“对于任何一个它从未询问过oracle的消息 $m$ ”改为“对于任何一个二元组 $(m,t)$ ，如果敌手从未用 $m$ 询问过oracle并且oracle输出 $t$ ”，这样定义的MAC称为强不可伪造的(strongly unforgeable)。（容易发现，对于确定性的 $\text{Mac}$ 程序，强不可伪造等价于普通的不可伪造。）

以上安全性的定义是在理论层面的。在实际中，敌手还可以不停给接收方发送二元组 $(m,t)$ ，然后根据接收方的各种物理层面的反应判断当前伪造的标签是否合法。也就是我们实际上在定义中应该假定敌手有确认标签是否合法的能力。我们之所以在定义中没有提到这点，是因为可以证明强不可伪造性下拥有这种能力并不会增加敌手成功的概率。然而，在实际中这一确认标签的能力确实会引发问题。假如接收方的验证程序是按位比较两个字符串，在第一次遇到不同字符时立马停机返回，那么敌手就可以根据检验程序返回输出的时间差来直到得知第一个出错的位置，改正它并不断重复以上操作敌手就能最终伪造出一个合法的标签。这一攻击并不是基于我们假定的模型的，而是利用了真实物理世界中的时间信息。这类方法称为侧信道攻击(side-channel attacks)。为了防止上述这个特定的攻击，我们可以要求MAC的检验程序的输出时间必须是与输入无关的（比如总是比较完所有位置再返回）。

构造具体的MAC方案

定长消息空间

假定消息空间中的消息是定长的，不妨设为 $n$ 。一个最简单的安全MAC方案就是选定一个伪随机函数 $F$ （公开的），基于密钥 $k$ 和消息 $m$ ，生成标签 $t:=F_k(m)$ 。这是一个确定性的MAC方案，验证方只需基于同样的 $F$ 验证是否有 $t=F_k(m)$ 即可（标准验证）。

这个方案是安全的。直观上，把伪随机函数替换为真随机函数只会对概率产生 $\text{negl}$ 的影响；而对于真随机函数，敌手成功在一个 $\{0,1\}^n$ 的标签空间中成功伪造一个长度为 $n$ 的标记的概率只能为 $2^{-n}$ ，因此敌手伪造成功的概率是可忽略的。

下面给出严格证明：设原方案为 $\Pi$ ，把 $F_k$ 替换为真随机函数 $f$ 的方案为 $\Pi'$ ，下证对于任意敌手 $\mathcal{A}$ ， $|\Pr[forge_{\mathcal{A},\Pi}]-\Pr[forge_{\mathcal{A},\Pi'}]|\leq \text{negl}$ 。假设不是这样，也即存在一个敌手 $\mathcal{A}$ 使得 $\geq \text{negl}$ ，那么我们可以构造一个调用 $\mathcal{A}$ 的分辨器 $D$ 来分辨真随机和伪随机（回顾分辨器的定义：设定oracle $O$ 为函数 $f$ 或函数 $F_k$ ，交给分辨器 $D$ ，允许 $D$ 询问 $O$ 多项式次，要求 $D$ 给出判断）：令oracle $O$ 内的函数要么为 $\Pi$ 中的 $F_k$ ，要么为 $\Pi'$ 中的 $f$ 。 $\mathcal{A}$ 不断询问 $O$ 并得到oracle的输出。现在当 $\mathcal{A}$ 输出 $(m,t)$ 时，令 $D$ 把 $m$ 输入 $O$ 得到 $t'$ ，当且仅当 $t=t'$ 时 $D$ 输出 $1$ ，否则输出 $0$ 。注意到，如果 $O$ 里存放的是 $F_k$ ，那么 $O$ 就完美模仿了 $\mathcal{A}$ challenge $\Pi$ 时的oracle，因此 $\mathcal{A}$ 成功的概率就是 $\Pr[forge_{\mathcal{A},\Pi}]$ ，并且 $\mathcal{A}$ 成功当且仅当 $D$ 输出 $1$ ；如果 $O$ 里存放的是 $f$ ，那么 $O$ 就完美模仿了 $\mathcal{A}$ challenge $\Pi'$ 时的oracle，因此 $\mathcal{A}$ 成功的概率就是 $\Pr[forge_{\mathcal{A},\Pi'}]$ ，并且 $\mathcal{A}$ 成功当且仅当 $D$ 输出 $1$ 。而既然 $|\Pr[forge_{\mathcal{A},\Pi}]-\Pr[forge_{\mathcal{A},\Pi'}]|\geq \text{negl}$ ，所以 $|\Pr[D^{F_k}=1]-\Pr[D^f=1]|\geq \text{negl}$ ，这样我们就构造出了一个能分辨真随机和伪随机的分辨器，这与伪随机函数的定义矛盾！所以 $\Pr[forge_{\mathcal{A},\Pi}]\leq \Pr[forge_{\mathcal{A},\Pi'}]+\text{negl}$ 。而根据真随机函数的定义，显然有 $\Pr[forge_{\mathcal{A},\Pi'}]\leq 2^{-n}=\text{negl}$ 。综上， $\Pr[forge_{\mathcal{A},\Pi}]\leq \text{negl}$ ，这样就证明完了。

不定长消息空间

我们可以基于定长的MAC构造一个不定长的MAC，这称为domain extension。解决不定长问题的一个高效方法是分块（本质上和块密码加密的原理完全相同），因此一个自然的方案是把消息分块，每个块 $m_i$ 分别做消息认证码 $\text{Mac}_k(m_i)$ 以后连成一个大的消息认证码 $\text{Mac}_k(m_1)\|\cdots\|\text{Mac}_k(m_d)$ 。但容易发现这是不安全的，敌手只需交换各个消息块和标签的顺序就可以构造一个从未发送过的消息的认证码。为此，我们在每个块里塞进块的编号 $i$ ，分别对每个 $i\| m_i$ 做MAC得到 $\text{Mac}_k(i\|m_i)$ 。然而由于消息长度可以不同，敌手只需扔掉最后几个块就可以伪造一个合法的新MAC。为此，我们在每个块里都塞进“总块数 $\ell$ ”这一参数 $\ell\|i\|m_i$ ，做 $\text{Mac}_k(\ell\|i\|m_i)$ 。然而敌手已经得知了两个同样块数的消息以及每个块对应的标签，那么他可以把两个消息的块交替放置，标签也交替放置，这样就伪造成功了。为此我们对于每个消息，再在标签的最前面塞一个随机数 $r$ ，也就是对于 $m_i$ 做 $\text{Mac}_k(r\|\ell\|i\|m_i)$ 。

我们把上述方案具体描述如下：对于给定消息 $m=m_1\|\cdots \|m_\ell$ ，生成随机数 $r$ 。假设我们有一个定长 $n$ 的MAC方案 $\text{Mac}$ ，规定 $m_i,i,\ell,r$ 都是长度为 $n/4$ 的01串，那么可以令 $t_i:=\text{Mac}_k(r\|\ell\|i\|m_i)$ 。最终，输出 $m$ 对应的标签 $t:=\text{Mac}'_k(m)=r\|t_1\|\cdots\|t_\ell$ 。这一方案是不确定性的，因为它包含了随机数 $r$ 。而整个方案只有 $r$ 是随机的，因此我们把 $r$ 附加在标签上，接收方可以在收到的标签的开头取出 $r$ ，然后用定长的验证程序验证每个 $t_i$ 。

我们证明这一方案是安全的。设敌手 $\mathcal{A}$ 攻破该方案这一事件为 $forge_\mathcal{A}$ ，那么即证 $\Pr[forge_\mathcal{A}]\leq \text{negl}$ 。定义事件 $repeat$ 表示在 $\mathcal{A}$ 询问它的oracle（也即 $\text{Mac}'$ 的oracle）时标签最前面的随机数 $r$ 至少发生过一次重复。定义事件 $NewBlock$ 表示敌手最终给出的challenge $(m,t)$ 中存在一个 $r\|\ell\|i\|m_i$ 不曾出现在先前询问oracle过程中的任何消息的任何一个块中。那么由全概率公式有 $\Pr[forge_\mathcal{A}]=\Pr[forge_\mathcal{A}\land repeat]+\Pr[forge_\mathcal{A}\land \overline{repeat}\land NewBlock]$ $+\Pr[forge_\mathcal{A} \land \overline{repeat}\land \overline{NewBlock}]$ $\leq \Pr[repeat]+\Pr[forge_\mathcal{A}\land NewBlock]$ $+\Pr[forge_\mathcal{A}\land \overline{repeat}\land \overline{NewBlock}]$ 。只需证明这三个概率都是可忽略的。

对于第一个概率， $\Pr[repeat]$ 是可忽略的，因为 $r$ 的取值有 $2^{n/4}$ 种，但询问只会发生多项式次；
对于第二个概率，我们用定长消息空间来归约。对于一个challenge定长MAC的adversary $\mathcal{A}'$ ，我们让 $\mathcal{A}'$ 扮演 $\mathcal{A}$ 的oracle。每当 $\mathcal{A}$ 给 $\mathcal{A}'$ 一个消息 $m$ 时， $\mathcal{A}'$ 把 $m$ 分块，并随机选取一个 $r\in\{0,1\}^{n/4}$ ，接着把每个消息块附加上 $r,\ell,i$ 丢给 $\mathcal{A}'$ 自己的oracle，这样就生成了 $m$ 的标签，返回给 $\mathcal{A}$ 。从 $\mathcal{A}$ 的视角看， $\mathcal{A}'$ 就是一个完美的oracle。当 $\mathcal{A}$ 给出了它的challenge $(m,t)$ 时， $\mathcal{A}'$ 判断事件 $NewBlock$ 是否发生（这是容易做到的，只需记录下此前 $\mathcal{A}$ 丢给它的所有询问的消息和标签）。如果 $NewBlock$ 发生，则 $\mathcal{A}'$ 找到 $(m,t)$ 中的这个new block，把它作为自己的challenge；否则， $\mathcal{A}'$ 可以直接放弃challenge。可以看到，正是因为这个block是new block，所以只要 $\mathcal{A}$ forge成功， $\mathcal{A}'$ 也一定成功。也即 $\Pr[forge_\mathcal{A} \land NewBlock]\leq$ $\Pr[forge_{\mathcal{A}'}]$ 。而因为定长MAC是安全的，有 $\Pr[forge_{\mathcal{A}'}]\leq \text{negl}$ ，这就证明完了。
对于第三个概率，如果 $repeat$ 没有发生，此时如果challenge中的 $r$ 与所有询问时的 $r_i$ 都不同（设共询问oracle $q$ 次，第 $i$ 次用的随机数是 $r_i$ ），那么 $NewBlock$ 一定发生。因此对于 $\Pr[forge_\mathcal{A} \land \overline{repeat}\land \overline{NewBlock}]$ ，一定存在唯一的 $j\in [q]$ 使得 $r=r_j$ ，并且第 $j$ 次询问时的某个消息块与 $m$ 中的某个消息块相同。这说明 $\ell_j=\ell$ 。但是既然 $m$ 与先前的任何一次询问的消息都不同，所以一定存在一个 $i$ 使得 $m$ 的第 $i$ 个块与第 $j$ 次询问的 $m$ 的第 $i$ 个块不同，这就说明这是一个新的块。综上所述，只要 $repeat$ 不发生，就一定发生 $NewBlock$ 。因此 $\Pr[forge_\mathcal{A} \land \overline{repeat}\land \overline{NewBlock}]=0$ 。

综上， $\Pr[forge_{\mathcal{A}}]\leq \text{negl}$ 。

CBC-MAC

既然可以用block cipher来做MAC。我们还可以用chained block cipher(CBC)来做MAC，称为CBC-MAC。在应用情境下，这些方法往往比上面构造的方法效率更高。

对于定长的消息空间，做分块 $m=m_1\cdots m_\ell$ ，选定伪随机函数 $F$ 和密钥 $k$ ，可以令 $t_0=0^n$ ， $t_i=F_k(t_{i-1}\oplus m_i)$ ，输出 $t_\ell$ 作为消息认证码。这是一个确定性的算法，可以证明它是安全的（证明比较复杂，此处省略）。注意到，用链式的方法时我们不再需要把所有的 $t_i$ 拼接起来，而是可以只输出最后那个 $t_i$ ，这使得认证码的长度复杂性得到大大优化。

然而，尽管上面这个CBC-MAC方案本身并不依赖于“定长”这一要求，但可以证明，如果用上述方案生成长度任意的消息的MAC，它将不再是安全的！为了让它对任意长的消息安全，有两种修改方法：一种是把 $m$ 的长度 $|m|$ 转位 $n$ 位二进制串以后加在 $m$ 前面，对 $|m| \| m$ 做上面的CBC-MAC（如果放在后面就不安全了，可以从短到长依次构造由长度的block组成的串，这样就得到了每个前缀的tag）；另一种方法是选取两个密钥 $k_1,k_2$ ，用原先的方案基于密钥 $k_1$ 生成标签 $t$ ，再输出 $F_{k_2}(t)$ 作为新的标签。后者的好处在于不用提前知道消息的长度，坏处在于需要两个密钥。证明省略。