Message Auth. Codes
MAC
MAC（消息验证码）是一对算法，包含一个签名算法和一个验证算法 I=(S,V)，定义在一个密钥空间、一个信息空间、一个标签空间上 (K,M,T)，签名算法 S(k,m) 会输出标签空间 T 中的一个标签 tag，验证算法 V(k,m,tag) 取密钥 k ，信息 m ，标签 tag，输出 yes 或 no。
标准的一致性要求
每一个密钥空间中的密钥 K 和每一个信息空间中的信息 M 都正好满足，如果使用密钥对信息进行签名，使用同样的密钥验证这个签名应该获得 yes 作为回应，V(k,m,S(k,m)) = yes。
CRC
CRC（循环冗余检验）是一个经典的校验和算法，为监测信息中的随机发生的错误而设计，并非针对恶意错误。如果利用 CRC 进行检验，没有密钥，攻击者可以随意更改信息重新计算输出 tag 并得到 yes 的反馈，Alice与攻击者无区别。
存在性伪造
安全的MAC，如果对它进行选择信息攻击，是不可能被存在性伪造的。
存在性伪造：攻击者产生新的信息标签对。
MAC安全模型
有两个算法 S 和 V ，有一个攻击者A ，游戏如下：挑战者通常为 MAC 选择一个随机密钥，攻击者进行他的选择信息攻击，他提交 $m_1$ 给挑战者，获得 $m_1$ 的标签，然后提交 $m_2$ 给挑战者，获得 $m_2$ 的标签，直到他提交了 q 个信息给挑战者，获得了 q 个这些信息的标签，这是选择信息攻击的部分，然后攻击者继续试图进行存在性伪造，他输出一个新的信息标签对我们就说他赢下这场游戏，换句话说，b=1 表示他赢下这场游戏。通常，我们定义攻击者的优势等于挑战者在本游戏中输出 1 的概率。安全的MAC系统，对所有有效的攻击者，优势都是可忽略的，换句话说，没有有效的攻击者能够以不可忽视的概率赢得这个游戏。
MACs based on PRFs
构建安全的MAC
安全的 PRF 可以构建安全的 MAC。
假设我们有一个伪随机函数 PRF，这个 PRF 取输入 X，输出 Y，F：K×X→Y，定义如下 MAC 为信息 M 签名，S(k,m):= F(k,m)，即计算函数在 M 处的值，信息 M 的标签就是在点 M 处的函数值，然后通过这一对验证信息，方法就是重新计算在信息 M 处的函数值检查结果是否等于给我们的标签，如果一样，我们说“是”，否则我们拒绝。
在如下例题中的 MAC 是不安全的，因为标签太短（当且仅当函数输出太小，才会有问题，如果PRF的输出很大，就可以获得一个安全的 MAC），攻击者有 1/2^(10) 的机会猜中 MAC。对这个MAC 的优势如下：
安全性定理
要想获得安全的 MAC，我们需要输出空间很大，例如：取一个 PRF，输出 80 位就很好了，它会产生 80 位 MAC，因此任意攻击者的优势最多是 1/2^(80)。
安全性定理证明
假设有一个从信息空间到标签空间的真随机函数，f:X→Y，这是一个从 X 到 Y 的真随机函数，它是从所有函数集中随机选择的。攻击者获得了信息 $m_1$ 的标签，即在点 $m_1$ 处的函数值，然后攻击者重新选择信息 $m_2$ ，获得了 $m_2$ 的标签，直到 $m_q$ ，他获得了所有对应的标签，它的目标是产生一个新的信息标签对就赢了，也就是存在性伪造，t=f(m)，意味着 t 是 m 的一个有效标签，并且 m 必须是新的，不能是 $m_1$ 到 $m_q$ 中的任何一个，然后它以 1/Y 的概率猜中函数值。
简单引理
如果 N 位 PRF 是安全的，那么 T<N 位的PRF（截断PRF，1/2^T可忽略）也是安全的。
CBC-MAC and NMAC
CBC-MAC
CBC-MAC（ECBC，常与AES一起使用）：取针对短信息的 PRF 为输入，输出一个 PRF ，可以处理长信息作为输出。在银行业广为应用，确保支票的完整性。
取信息 m ，将它分割成一个个的分组，每个分组和底层函数 f 的分组一样长，然后沿着 CBC 链接运行，但不输出中间值。
CBC-MAC 可以取最多长 L 个分组的信息，L 可以是百万或十亿的大小。它还可以是变化的输入信息的长度，换句话说，|X|不大于 L，意思是允许输入的信息包含的分组数可以是 0 到 L 的任一数，每个 CBC 可以处理一个分组长的信息、两个分组长的信息、… 、L 个分组长的信息。
不经历最后一步 $k_1$ 加密的函数，叫做原 CBC 函数。不是一个安全的 MAC。
一个特殊的攻击
不经历最后一步 $k_1$ 加密的函数，在这个攻击里，攻击者先请求一个特定信息 m 的标签，信息 m 只有一个分组长，对一个单分组信息应用 CBC 意味着，只需要直接应用函数 f ，就获得了这个标签（即直接应用 f 在单分组信息 m 处的结果），现在攻击者有了t=F(k,m)，现在我们声称他可以定义这个信息 m’ ，包含两个分组，第一个是 m ，第二个是 t⊕m ，我们声称刚刚收到的 t 是这两个分组的信息 m’ 的标签，t 是这个两分组信息m'=(m,t⊕m)的有效 MAC ，攻击者可以产生这个有效的标签 t ，而这个两份组的信息是从未被询问过的，因此，他可以破解这个 MAC 。
HMAC
HMAC 取处理短输入的 PRF ，产生能处理长输入的 PRF，在因特网上 SSL、IPesc、SSH 等协议使用 HMAC 来保护完整性。
NMAC
NMAC 同上，取处理短输入的 PRF ，产生能处理长输入的 PRF。NMAC 不常与分组密码配合使用，主要原因是在 NMAC 机制里各个分组的密钥会变化，这意味着整个 AES 密钥扩展对每个分组都必须重新计算，而当密钥快速变化时 AES 并不是能表现很好，因此，使用 NMAC 时，可以使用更善于处理各个分支上变化密钥的分组密码，因此， NMAC 一般不用 AES 。事实上，NMAC 是 HMAC 的基础。
NMAC 用到的 PRF 的分组长度 |X| 远远大于密钥长度，把固定的补齐附在信息后面，fpad 是固定的补齐。
不经历最后一步 $k_1$ 加密的函数，为级联函数。不是安全的 MAC。最后一步的加密阻止了扩展攻击，扩展攻击是针对级联的唯一一种攻击。
针对 CBC-MAC 的安全性定理
q 是询问的信息数，并用一个特定密钥计算 MAC ，假设我们想确保所有的攻击者区分 PRF 和真随机函数的优势都小于 1/2^32 ，根据安全性定理，这意味着我们需要确保 (q^2)/|X| < 1/2^32，超过了 32 这个安全长度就必须更换密钥。
Attack
在签名了 |X| 或 |K| 的平方根 个信息后，MAC 就不再安全。
针对 PRF ，同时也是针对 ECBC 和 NMAC 的攻击：假设底层函数是 PRP ，是类似 AES 的分组密码，记为 F ，F 可以是 F_ECBC 或 F_NMAC ，F 意味着这是一个针对长信息的 PRF 。现在，实际上两种机制都有如下的扩展性质，如果给我一个碰撞，发生在信息 X 和 Y 上，那么事实上，这也意味着有一个碰撞发生在 X 和 Y 的扩展上，换句话说，如果我把 W 各附在 X 和 Y 的后面，我也会在这些信息上获得一个碰撞，那么很难说服自己这个扩展性质是成立的。
观察下面这张图，正好在 tag 那里发生膨胀，记得我假设 F 是 PRP ，那么一旦固定 $k_1$ ，它就是一一映射的函数，于是，如果两个信息正好被映射到输出的同一个值，这就意味着它们正好被映射到同样的值作为 原CBC 的输出。但如果它们在 原CBC 的输出中被映射到同样的值，这意味着如果我加上另外一个分组，我们记为 W ，我获得了这个输出，然后计算这两个信息的共同的函数值，对两个信息，我都会在点得到同样的值，当用 $k_1$ 加密时，会获得同样的输出，即最终输出。在我附上分组 W 后，如果两个不同信息的两个值正好是一样的，依然能获得同样的输出值，便容易说服自己。
MAC padding
一个糟糕的补齐
当 ECBC 信息长度不是分组长度的整数倍时，需要对最后一个分组补齐信息。取最后一个分组，在后面补 0 至其长度和一个满分组的长度一样，这样的 MAC 是不安全的。因为这样可以计算出新的信息 m ，信息 m 联结上 0 ，正好也有同样的补齐，一旦带入 m 和 m∥0 到 ECBC 中，我们会得到同样的标签输出，这意味着 m 和 m∥0 有着相同的标签，因此攻击者可以实施存在性伪造，他会问信息 m 的标签，然后他会输出伪造的标签和信息 m∥0 。
补齐函数
补齐函数本身必须是一一映射的函数，换句话说，它应当是将两个不同的信息映射到不同的两个补齐的信息，不应该在补齐函数上有碰撞，必须是可逆的。$m_0$ ≠ $m_1$ => pad($m_0$) ≠ pad($m_1$)
完美的补齐方法
ISO 建议把字符串 “1000…00” 附在信息后面，使得信息长度是分组长度的倍数，这个补齐是可逆的，我们只需描述求逆的算法，就是简单的从右往左扫描信息，直到遇见第一个 1 ，然后移除所有在 1 右边的位，包括 1 本身，就可以获得原来的信息。
如果原信息长度已经是分组长度的整数倍，在这种情况下，加一个假的分组非常重要，假设我们不加假的分组去计算这个信息的 MAC ，结果是，如果你看到这个信息的长度是分组长度的整数倍，还有一个信息的长度不是分组长度的倍数，但它被补齐到分组大小了，想象这个信息以 100 结尾，如下图，与第二个根本没补齐的信息是一样的，因此，如果我问第一个信息的标签，同时我也获得了第二个以 100 结尾的信息的标签。如果我们不加假的补齐分组，补齐将是不可逆的，因为两个不同的信息正好被映射到了同样的补齐结果，因此 MAC 将不安全。
CMAC
如果你看确定的补齐函数，容易证明所有情况下我们都需要补齐，原因是 长度为分组倍数的信息数目 比 长度不是分组倍数的信息数目 少得多（约为 1:2 ），因此我们无法获得一个从 大的所有信息的集合 到 小的分组倍数长的信息集合 的一一映射，总会有我们必须扩展原信息的情况，这种情况就对应于我们加假的补齐分组。但是，有一种非常聪明的方法 CMAC ，可以使用一个随机的补齐函数，不需要加假分组。
CMAC（常与AES一起使用）可以使用一个随机的补齐函数，不用加假分组。使用三密钥机制，第一个密钥 k 用于 CBC 计算标准的 CBC-MAC 算法，密钥 $k_1$ 和 $k_2$ 仅用于最后一个分组的补齐。 $k_1$ 和 $k_2$ 是使用伪随机数发生器由 k 推出的。如果信息长度正好是分组长度的整数倍，采用 ISO 补齐，并把最后一个分组和密钥 $k_1$ 异或；如果信息长度不是分组长度的整数倍，不做扩展，把最后一个分组和密钥 $k_2$ 异或。
攻击者不知道 $k_1$ 和 $k_2$ ，因此攻击者不知道随后分组运行了哪个函数，不可能实施对级联函数、原CBC 所适用的扩展攻击。
CMAC 机制是一个伪随机函数，具有与 CBC-MAC 同样的安全性。
使用 CMAC 的好处：①不需要做 原CBC 函数后面的最终加密步骤；②通过两个密钥来区分信息长度是否是分组长度的倍数问题，解决了“是否发生了补齐”所带来的歧义。
A Parallel MAC
PMAC
PMAC 可并行，使用了一个底层的 PRF 来构建一个 PRF去处理长得多的信息。密钥是一对密钥，一个给 PRF，另一个给掩码函数 P。采用与 CMAC 类似的补齐函数，不需要加假的分组。
这个机制如下工作：我们取信息，把它分成若干分组，然后我们独立的处理各个分组。首先，我们计算某个函数 P ，并将结果与第一个分组异或，然后我们运用函数 F ，使用密钥 $k_1$ 。我们对每个分组都做同样的事情，我们可以并行地处理，所有分组都被独立地处理，我们收集来所有的结果，然后异或起来，然后再加密一次，就得到了最后的标签。由于技术原因，在最后一个分组上，我们不需要使用 PRF F 了。
函数 P 的作用：在运行过程中，如果不与函数 P 进行异或，得到的 MAC 是完全不安全的，因为各个分组之间没有加入先后顺序。特别地，如果随意交换两个分组，将不会改变最后标签的值，因为异或是可交换的，无论我们是否交换分组，标签值都是一样的，因此攻击者可以请求一个特定信息的标签，然后他将获得 其中两分组交换后的信息的标签，这也算存在性伪造。这个函数 P 试图为这些分组加入顺序，首先注意到，这个函数 P 是个带密钥的函数，它取密钥为输入；其次，更为重要的，它取分组序数为输入。换句话说，函数的这个输入每个分组都不相同，这就是用来阻止分组交换攻击的，函数 P 其实是一个非常容易计算的函数，给定密钥和分组序数，只是进行了某个有限域上的乘法，对于 PMAC 的运行时间开销很小。
PMAC的安全性定理
如果给我一个攻击 PMAC 的攻击者，我可以构建另一个攻击底层 PRF 的攻击者，加上另一个误差项。由于这个 PRF 是安全的，我们知道这一项是可忽略的，如果我们希望左侧优势可忽略，需要误差项也是可忽略的。其中，q 是使用一个密钥计算 MAC 的信息数，L 是所有这些信息的最大长度。
对于 AES ，分组长度是 2^128，其平方根是 2^64，只要 qL < 2^64，这个 MAC 将是安全的。每次当它接近这个值时，为了计算更多信息的 MAC ，我们必须更换密钥。
PMAC 的数学是增长的
假设用来构建 PMAC 的函数 F 不仅是 PRF ，而且是 PRP，那么我们能在需要时求 F 的逆，现在假设我们已计算长信息 m 的 MAC，假设这个长信息的一个分组发生了变化，m[1] 变成了 m’[1]，但其他分组不变，对于其它 MAC 机制，比如 CBC-MAC ，即使只有一个分组变化了，我们还是需要重新计算整个信息的标签，重新计算标签需要的时间与信息长度成正比。实际上用 PMAC ，如果我们只变化一个分组或是很少的分组，我们可以很快就完成标签的重新计算。由于使用的是 PRP ，取改变前原信息的标签，我们可以求函数 F 的逆，确定应用函数 F 之前的值，现在我们有了所有分组的异或值，我们可以抵消掉来自原分组的异或部分，将 所有分组的异或值 与 原信息分组传到异或加法器的值 进行异或，再异或 来自新分组传到异或加法器的值，然后再应用函数 F ，就得到新信息的标签。
一次性MAC
一次性 MAC 构建的 MAC 只用于单个信息的完整性，换句话说，每次计算特定信息的完整性，我们也要改变密钥，任何密钥只能用于一条信息的完整性。
一次性MAC安全模型
我们定义安全性游戏，只允许攻击者做一次选择信息攻击，那么，他只提交一个信息的询问，然后得到了这个询问信息对应的标签。现在攻击者的目标是伪造一对信息-标签。当我们只想使用一个密钥，为单条信息提供加密或完整性，通常，我们说一次性 MAC 是安全的，因为没有攻击者可以赢得这场游戏。
一次性 MAC 对无限强力的攻击者都是安全的，由于只为一次性设计，它可以比基于 PRF 的 MAC 更快。
一次性MAC的经典机制
工作过程：首先，选取一个比分组大小略大的质数，当我们使用 128 位分组时，我们选的第一个质数大于 2^128 ，质数选为 2^128+51 ，现在这个密钥是一对随机数，它们的取值范围从 1 到我们选的质数 q ，现在我们有一个信息，把它分成若干分组，每个分组 128 位，我们把每个分组里的数视为整数，范围从 0 到 2^128 - 1。现在 MAC 如下定义：首先，我们去我们的分组信息构建它们的多项式，如果信息中有 L 个 分组，我们构建一个 L 次多项式，注意多项式的常数项设为 0 ，我们去信息对应的多项式，计算它在点 K 的值，K 是我们密钥的一半，然后加上 A ，A 是我们密钥的另一半，最后结果取模。这个 MAC 是安全的，如果我告诉你一个特定信息的 MAC 值，并不会告诉你任何关于另一信息的 MAC 的任何信息，因此，即使你已经看过一条信息的 MAC ，你也无法伪造其他信息的 MAC ，但如果你看到了两条信息的 MAC ，那将完全暴露了密钥，MAC 就是可伪造的了。
Many-time MAC
现在有一个通用的方法可以把一次性 MAC 转变成多次 MAC。假设我们有一次性 MAC ，签名和验证算法分别为 S 和 V ，我们假设签名本身是 n 位 字符串，另外，我们看一个安全的 PRF ，它也正好输出 n 位字符串，但也取 n 位字符串，现在定义一个通用的 MAC 构建，这些 MAC 叫做 Carter-Wegman MAC ，它如下工作：我们对信息 M 应用一次性 MAC ，然后我们用 PRF 加密结果，我们选择一个随机数 r ，根据 r 计算一个一次性密码本，通过对 r 应用 PRF ，然后我们把结果与一次性 MAC 异或，在这个机制里，快速的一次性 MAC 被用到了可能有几个 G 的长信息上，而费时的 PRF 只被应用在新鲜值 r 上，r 接着被用来加密 MAC 的最后结果。
可以证明如果我们的 MAC 作为构建分组，是个安全的 MAC ，而 PRF 也是安全的，那么事实上，我们可以获得一个多次的安全 MAC ，其输出 2n 位标签。
Carter-Wegman MAC 是一个随机的 MAC 的好例子，这个新鲜值 r 每次重新计算标签时，都被重新选取，如果你试图两次计算同一信息的标签，你会选择一个不同的 r ，因此两次你会得到不同的标签。
Carter-Wegman MAC ，不基于 PRF ，因为单个信息可以被映射到许多不同的有效标签。
Carter-Wegman MAC 取大量的信息，计算哈希值，得到一个小标签，计算是用了快速的一次性 MAC ，然后用 PRF 加密。好处是 大量信息的哈希值计算使用了一个快速的一次性 MAC 。
