密码学05 MAC

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束手无策

上一篇:CSDN之C技能树学习:05 - 数据类型之变量


下一篇:05 数组