密码学05 MAC

\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert}

Message Authentication Code

简称MAC。通常我们不仅希望保证一条消息的内容没有被泄露（例如你向女神告白的信的内容），还希望我们发出去的消息没有被篡改过（例如你给女神的告白信不会被换成/修改成除了告白信之外的别的东西）。前者属于secrecy的范畴，后者则是integrity的范畴。

之所以会出现这样的需求，是因为我们开始考虑更“强大”的adversary了。原本的EAV-secure模型只能对窃听者进行建模，而通常我们的adversary不仅可以看（窃听），还可以摸（篡改消息）。并且我们发现原有的加密算法是无法保证integrity的。以OTP为例，攻击者在得到密文 $c$ 后，可以通过翻转 $c$ 任意的比特来实现篡改出任意可能的信息。即使他不知道消息本身是什么，他也可以伪造出任意的消息——反正任意的定长比特串都是合法消息

于是就有了MAC的闪亮登场！这样你给女神的真情表白就不会变成痴汉发言，战书，或者是别的什么东西了。

定义

一个MAC包括三个PPT算法，$\text{MAC=(Gen,Mac,Vrfy)}$，其中

$\text{Gen}$ 负责生成一个密钥 $k$，$\text{Mac}_k(m)=t$ 负责根据 $m,k$ 生成一个标签(tag)，$\text{Vrfy}_k(m,t)$ 则会在 $t$ 是 $m$ 的一个合法tag时输出 $1$，否则输出 $0$

这里的 $\text{Vrfy}$ 是确定性算法，而 $\text{Mac}$ 则没有要求。这点是很显然，因为要保证：

1. 正确的tag能被识别

2. 错误的tag能被报出来

也就又是所谓的sound&complete了

看起来很像私钥加密，但是又不太一样：$\text{Vrfy}$ 是需要借助 $m$ 来确认tag的正确性的，因此MAC往往不会单独使用，这里的 $m$ 还需要加密保护起来。

然后就定义了几个性质

Correctness

$\forall k=\text{Gen}(1^n): \text{Vrfy}_k(m,\text{Mac}_k(m))=1$

没啥好说的，这个性质提示我们：

如果我们的 $\text{Mac}$ 是确定性算法，那么我们的 $\text{Vrfy}$ 就可以通过重新计算一次 $\text{Mac}_k(m)$，然后比较 $\text{Mac}_k(m)$ 和 $t$ 是否相同来判断这个tag是否合法。这被称为canonical way

Secrecy

其实就是如何保证我们的消息被篡改后，能从tag中反馈出来？

密码学给出的回答是这样的：如果任何PPT算法都不能造出一个对应的message-tag pair出来，那么我们就可以认为没有人能够给一个修改过后的消息 $m$ 伪造tag，也即不存在消息被篡改后仍然能通过 $\text{Vrfy}$ 了

形式化地写出来是一个 $\text{Mac-forge}_{\cal A,\Pi}$ game：

1. 首先生成一个 $k$，然后给一个 $\text{Mac}_k$ 的oracle给adversary $\cal A$

2. $\cal A$ 可以任意查询oracle，然后输出一对答案 $(m,t)$。期间我们会维护一个集合 $\cal Q$，表示 $\cal A$ 查询过的所有消息

3. 检查 $\text{Vrfy}_k(m,t)$，如果满足1. $\text{Vrfy}_k(m,t)=1$ 且 2. $m\not\in \cal Q$，就得到结果 $1$，否则为 $0$

我们称一个MAC scheme $\Pi$ 是安全的，当且仅当 $Pr\left[\text{Mac-forge}_{\cal A,\Pi}(n)=1\right]\leqslant\text{negl}(n)$。这个安全性的全称也叫being existentially unforgeable under an adaptive chosen-message attack

这个定义就是很好地抓住(capture)了“不能伪造tag”这句话，看下来是很自然的。

如果细心一点可以发现，这里的 $\text{Mac}$ 不一定是确定性算法，因此可以有一个 $m$ 对应多个不同的 $t$，这说明上述定义会出现一些问题——Adversary完全可以给一条已经查询过的消息 $m$ 构造出一个全新的tag。于是自然引出strongly secure MAC的定义：

太懒了，只需要把上面的 $m\not\in\cal Q$ 改成 $(m,t)\not\in\cal Q$ 就好了

结合canonical way的MAC可知，对所有canonical MAC有：如果它是secure的，那么它自然地就是strongly secure的

注意到这个strong secure的安全性要求仍然是很弱的。我们甚至并不要求Adversary输出的消息有含义，而只需要能构造出一条消息和对应的tag就好了。

构造

fixed-length MAC

构造一个定长MAC是比较简单的，只需要用一个PRF就好了。安全性的证明可以通过反证，然后构造一个区分PRF和真随机函数的攻击者 $\cal A$ 来完成，细节就留做习题吧~

arbitrary-length MAC

只讲讲怎么做到任意 $l(n)$ 的整数倍长度，其中 $l$ 是单个 $\text{MAC}$ 的extension factor（回忆上面说的用PRF构造MAC）

假设现在给了 $n$ 个消息块，每个块都能单独用MAC构造tag，那么我们可以这么构造一个整体的tag：

1. 规定 $t_0=IV$，其中通常 $IV=0$，initial vector的意思

2. 规定 $t_i=MAC(t_{i-1}\oplus m_i)$

最后输出 $t_n$ 就好了

安全性的证明比较简单，只需要对着 $n$ 做数学归纳法就好了，可以发现每次都没法伪造的Adversary对于整体的tag束手无策