Jump to content
  • Hello visitors, welcome to the Hacker World Forum!

    Red Team 1949  (formerly CHT Attack and Defense Team) In this rapidly changing Internet era, we maintain our original intention and create the best community to jointly exchange network technologies. You can obtain hacker attack and defense skills and knowledge in the forum, or you can join our Telegram communication group to discuss and communicate in real time. All kinds of advertisements are prohibited in the forum. Please register as a registered user to check our usage and privacy policy. Thank you for your cooperation.

    TheHackerWorld Official

Recommended Posts

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

Link to post
Link to comment
Share on other sites

 Share

discussion group

discussion group

    You don't have permission to chat.
    • Recently Browsing   0 members

      • No registered users viewing this page.
    ×
    ×
    • Create New...