11.1 概述

MAC是一些用来进行检验消息身份和完整性的字节。这些码通常被称为“tags”。MAC算法将任意长度的消息和一个固定长度的密钥做输入，输出一个tag。MAC算法的验证过程是输入消息，密钥和tag，然后判断出tag是有效的还是无效的（通常仅仅重新计算tag然后监测与提供的tag是否一致是不够的，很多安全的MAC算法时随机的，每一次使用的时候都会产生不同的tag）

注意这里提到的消息，而不是明文或者密文。这个是有意为之。本书中提到MAC是的时候通常指一种获取身份认证加密的方法，所以这里的消息通常是指密文。但是将MAC运用到明文消息中也是完全可以的。事实上，一些安全的身份加密机制允许身份认证信息（没有加密）和加密之后的身份认证密文一起发送。

通常，当我们谈论一个特定消息的身份和完整性的时候，通常是使用签名算法（12章中会介绍）。现在需要知道的是签名算法是针对非对称密钥算法而言，而本章是针对对称密钥算法的。

安全的MAC算法

对于安全的MAC算法需要具备的特性尚未明确定义。

需要定义一个活跃的攻击者。该攻击者会挑选消息攻击。这意味着攻击者会想密码系统请求一些消息mi的tag，密码系统会诚实地返回正确的tagi。

一个攻击者将会尝试产生存在性伪造，一种说法是他们将要产生一个新的有效的组合（m,t）。攻击者的目标是对他们挑选的新的消息m‘可以产生一个有效的tag t'.如果攻击者可以计算一个新的不同的tag t'对于之前提供过有效tag的消息mi，那么这个MAC算法将被认为是不安全的。

为什么MAC算法需要密钥？

如果你之前曾经验证过消息的完整性，你肯能使用过例如校验位（如CRC32，活Adler32）或者是密码学hash（如SHA家族）来计算消息的校验码（依赖于你选择的算法，它可能被称为hash或者摘要）

比方说你要发布一个软件包。你可能会有几个源码的tar包也可能是当前比较著名的操作系统的二进制包。然后你将一些hash放在了它们后面，这样所有下载软件包的人可以验证hash，然后确认它们下载的版本是正确的。

当然，这个机制目前已被破坏。任何人都可以计算hash。并且上述的机制要让用户自己去验证他们的下载。这就意味着攻击者可以修改下载，然后重新计算hash，然后将修改后的下载和hash一起保存。用户下载到修改后的下载，计算它的hash然后与修改后的hash进行比对，然后得出他们下载正确的结论。这个机制对于防止攻击者修改下载，存储或者传输没有任何的帮助。

为了安全地完成这个操作，可以直接对整个二进制进行签名，或者签名它的摘要，只要使用的hash函数是防二次镜像攻击的即可。这里最重要的不同是产生签名（使用提前共享的key或者公钥签名算法），是攻击者做不到的事情。只有拥有密钥的人才可以进行签名。

11.2 将MAC和消息结合

正如之前所言，不身份认证的加密是不好的，这也是引入MACs的原因。当然想要使MAC有用，首先需要将它传输给接受放。由于现在谈论的是与身份认证加密相关的内容，本节不再使用消息，而是直接使用歧义性更小的明文和密文。

现在有3种将MAC和密文结合在一起的方法

1. 认证和加密。对原文分别进行认证和加密。这是SSH采用的方式。用符号表示如下。然后发送密文C和tag t。

2. 先身份认证再进行加密。先对明文进行身份认证，然后将明文和tag一起进行加密。这是TLS采用的方式。用符号表示如下。然后发送密文C。（不需要发送t，因为它已经被加密称为了C的一部分）

3. 先加密再进行身份认证。先加密明文，然后计算密文的MAC。这是IPSec所采用的方式。符号表示如下。然后发送密文C和tag t。

这三种方式都已经被深入地研究和比价哦过了。目前所知，加密然后认证毫无疑问是最佳选择。著名信息安全研究者Moxie Marlinspike，认为它无疑是最佳的选择，有一个对于不遵守这个模式的定律叫“The cryptographic Doom Principle”。Moxie表示任何在检验MAC之前做其他事情的系统都终会毁灭。认证和加密以及认证然后加密都需要你在验证消息身份之前先进行解密。

认证然后加密

认证然后加密是一个不好的选择，但是是一个比较微妙的坏选择。在一些特定条件下，它依然是安全的。

首先，这个机制会正常工作。当然在做别的事情之前需要首先解密，对于很多密码从业者，包括TLS的设计者，认为这个并不会有问题。

实际上，不同组合机制的严格的对比，都提到了这个启动项。在IPSec的一篇评论文章中，Schneier和Ferguson，两个越南密码学家，认为IPSec使用先加密再认证是一项瑕疵，应该使用TLS的先认证再加密。在过去很长时间那个更优秀都是个争论，但是目前已经证实了先加密后认证是可证的安全机制。

认证并加密

认证并加密存在严重的问题。因为tag 认证的是原文，并且tag是传输的消息的一部分，攻击者可以判断出两个原文消息相同因为他们的tag相同。这个机制导致的问题和ECB模式相同，在ECB模式中攻击者可以辨别出相同的块。这是一个严重的问题，尽管他们并不能直接对块进行解密。

11.3 使用hash函数进行初步尝试

很多构造MACs的方法都涉及到了hash函数。这通常是大家可以想到的最简单的方法，在消息的前端加上k做前缀，然后对整个消息做hash。

这个方法被称为前缀MAC，因为它是将密钥key作为前缀的。

密码学安全的hash函数H，保证了一些重要的事情：

• tag t是容易计算的；一般的hash函数都非常快。很多例子中可以讲key提前计算，然后仅仅花费时间来hash消息本身。

• 给任意数量的tag，对于攻击者来说都没有办法逆转hash函数恢复k，这一点允许攻击者构造任意的消息。

• 给任意数量的tag，对于攻击者来说都没有办法恢复H(k),这一点允许攻击者构造几乎所有消息。

一个小的警告：假设密钥k是有足够的熵的。否则就会有和使用hash函数做密码存储一样的问题：攻击者只要尝试所哟的k直到匹配上。一旦他们做到这点，他们就找到了真正的k。这不是MAC算法的错误：如果你使用的key只有一点点长度，这就使得攻击者很容易遍历他们，不论你选择什么MAC算法，在一开始你就输了。

打破前缀MAC算法

前缀MAC算法对于大多数hash函数来说（包括SHA-2）是完全不安全的。

在上一章hash函数中可以看到，很多函数函数，例如MD5，SHA-0，SHA-1和SHA-2，在产生摘要之前将消息使用可以预见的填充模式填充。摘要输出的和hash函数内部的状态相同。这是一个问题，攻击者可以使用这个特点构造消息。

首先，他们使用已知摘要作为hash函数的内部状态。这个状态和hash k||m||p的状态一致，其中k是密钥，m是消息，p是可以预见的填充。现在攻击者使用hash函数去生成一些新的字节：攻击者挑选消息m‘。hash函数的中间状态转变为k||m||p||m'. 然后攻击者让hash函数去产生摘要。这样状态转变为k||m||p||m'||p'。攻击者将这个值输出作为他给。这个和直接使用密钥k计算m||p||m'的tag是完全一致的。这样攻击者就成功地为一条新消息构造了一个tag，所以根据我们的定义，这个MAC算法是不安全的。

这个攻击被称作长度攻击，因为是在有效消息后面扩展新的内容的。中间的pad p，是原始信息的扩充，变味了一些数据的中间部分，被称作填充胶，因为它将原始消息m和攻击者新增的消息m‘连接到了一起。

这个攻击听起来比较学术，不太实用。我们可以通过这个攻击证明这个MAC算法是不安全的，但是攻击者可以成功构造的tag对真正消息的修改有限。特别的，攻击者只能够构造一个包含了原消息的新消息，新消息后面跟着一些二进制垃圾，再后面跟着攻击者挑选的信息。然而事实证明对于很多系统，这个已经足够产生很大问题。考虑下面的Python代码，其解析一系列类似于k1=v1&k2=v2&...的键值对。

<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="python" cid="n53" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;">def parse(s):
pairs = s.split("&")
parsed = {}
for pair in pairs:
key, value = pair.split("=")
parsed[key] = value
return parsed</pre>

这个解析函数仅仅记录了一个给定key的最后的值：字典中先前的值会被充血。作为结果，攻击者进行长度扩展攻击可以有效地控制整个解析出来的字典。

如果你认为这个代码有很多问题；是的，它确实是这样。举例，它没有正确处理字符编码。但是即便它处理了，也不能处理长度扩展攻击的问题。大多数解析函数可以很好地解析出中间有二进制垃圾的情况。攻击者可以产生一条有效tag的信息他就会有很大机会产生出和你想要实际表达的完全不同的东西。

前缀MAC构造算法对于一起比较新的hash函数（比方说SHA-3）来说是安全的。这些hash函数通常还使得前缀MAC称为安全而快速的MAC算法。他们通过实用很多中技术来规避长度扩展攻击：例如BLAKE会记录hash已经处理的位数，而BLAKE2会有一个结束标识符来标识特定的块是最后一个。

变种

前缀MAC算法的问题使得人们想出了一系列非常聪明的变种。例如，为什么不将key放在后面呢(t=H(m||k)),或者为什么前面放一下，后面放一下(t=H(k||m||k))

值得说明的是这些都至少和前缀MAC一样好，但是他们都同样拥有严重的问题。例如后缀MAC系统会更加暴漏hash函数的弱点，一个成功的碰撞攻击会打破MAC。三明治MAC也有其他复杂的问题。

密码学家已经发明了很多更加强壮的MACs，在下一节将会介绍。没有理由不使用这些优秀的MAC算法。

11.4 HMAC

HMAC是实用hash函数作为参数来产生MAC的一个标准。是由Bellare，Canetti和Krawczyk 1996在论文中提出的。那个时候有很多实用hash函数来产生验证信息的协议。大多数这些尝试都失败了。这篇论文的目标是仅使用一个密钥和一个hash函数来产生一个可以证明是安全的MAC。

HMAC一个非常棒的特性是它由很强的安全性证明。只要底层函数是一个伪随机函数，HMAC自身也是个随机函数。底层的hash函数甚至都不需要是抗碰撞攻击的HMAC都依然是一个安全的MAC。这个证明在HMAC之后提出，并且和真实世界的观察一致：即使使用MD5和SHA0这种有严重碰撞攻击的算法。以这些hash函数构造的HMAC依然是整体安全的。

HMAC和前缀MAC以及它的变种最大的不同是它对消息进行了两次hash，每一次都要将key传入。HMAC的过程如图：

image.png

比较令人惊讶的是这里的两个常量Pinner（hash函数block长度的0x36）和Pouter（hash函数block长度的0x5c）。他们是HMAC安全性证明中必要的一部分，但是他们的值并不重要，只要两个常量的值是不同的。

这两个值在使用前和key做异或。然后结果被用来给原始信息（对于pinner）或者中间hash结果（对于pouter）做前缀扩充。因为他们是被注入的，计算了前面值的hash函数的中间状态可以提前被计算，这样可以节省一些MAC计算的时间。

11.5 一次性MACs

目前我们假设对于不论多少消息，都使用一个key来产生安全的MACs。与之相对，一次性MACs是一次使用一个key的MAC函数。这听起来像是个愚蠢的想法，因为我们已经讨论过常规的安全的MACs了。一个算法只工作一次看起来很糟糕。然而他们也有很大的优势：

• 他们通常验证起来很快，即使是对非常大的消息。

• 他们产生的信息内容的tag拥有很强的安全证明。

• 存在构造可以把一次性MAC转化为安全的多次使用的MAC，解决了根本上的问题。

一个一次性MAC的典型例子包括了一个简单的乘法和加法模上一个大素数p。宰割场景下，密钥包含两个1到p之间的随机数a和b。

这个简单的例子仅为一个block信息m有效，素数p需要比最大的m大。然后它可以通过使用消息的多项式P，被扩展支持包含了块mi的更大的消息集M。

这看起来需要很多的计算，但是多项式计算可以通过共同的因子快速的迭代计算（Horner定理）：

可以通过计算每一个乘法之后模p，这样数字就会一直保持在合适的大小。

在很多方法中，一次性MAC用来对一个用来做加密的一次性密码进行认证。安全争议是相似的：只要这个key只使用一次，攻击者无法获取到任何关于key或者消息的信息，因为他们已经被不可逆地混合了。这也强调了这个MAC算法是安全的，是可以抵抗攻击者使用已有消息进行构造的，尽管攻击者可能有无尽的计算资源。

和一次性密码本一样，安全性依赖于连个重要的参数也就是密钥a，b

• 它们必须要完全随机

• 它们只能被最多使用一次。

重复使用a和b

如果在上例算法中，对两条不同的消息m1和m2使用相同的key（a,b）来做认证，就会是不安全的。

攻击者可以通过简单的代数运算来重构a和b

将a的值代入到t1或t2得到b:

可以看在在一次性密码本中，重用密钥会导致整个密码系统的私密性和完整性的失败。相似的一次性MAC直接也有一点危险。幸运地是这个弱点可以通过构造一种叫做Carter-Wegman MAC的算法来解决，该算法在下节介绍。

11.6 Carter-Wegman MAC

如前所述，一次性MAC最明显的问题是他们的实用限制。幸运地是，经证明有一种被称为Carter-Wegman MAC的构造方法，它可以将安全的一次性MAC算法转变为安全的多次使用的MAC同时保留了其性能的优势。

Cater-Wegman MAC背后的原理是，使用一次性MAC算法O来为一些数据产生tag，然后和一个nonce值n一起使用伪随机函数进行加密，例如块密码算法，用来保护一次性tag：

只要F是一个安全的伪随机函数，这个nonce值的加密就是完全不可预测的。在攻击者的严重，这就意味着将一次性MAC生成的tag，异或上了一完全随机的东西。这样就会掩盖了tag的真实值，攻击者就无法像上一节那样去恢复多次使用的一次性MAC的密钥。

记住Carter-Wegan MACs有两个不同的密钥，k1和k2，然后Carter-Wegman MAC是与一次性MAC算法相关联的，一次性MAC算法的密钥是两个不同的key a和b，它们是两个不同的值。Carter-WegmanMAC的k2是传递给快速一次性MAC唯一的值。如果一次性MAC是在一节中提到的那种两个密钥a和b的形式，那么k2就需要分成两个key。此时Carter-WegmanMAC的密钥就是(k1,k2)=(k1,(a,b))

可以发现Carter-WegmanMAC将MAC算法分成了两部分。在F(k1,n)中，F通常是一个伪随机算法，例如块密码算法。它与一次性MAC算法相比太慢了。然而它的输入，nonce值，是很小的。这个不可预测的块密码的输出可以对一次性MAC的结果进行掩盖。在第二项中，O（k2,M）这个大的输入数据M仅仅有非常块的一次性MAC算法O来操作。

这个构造，特别是Poly1305-AES已经在很多MAC函数中出现。论文[BHK+99]和以及更早的RFC[BHK+]，与MAC函数相关的被称为UMAC也是一个很好的参考信息，它们中很详细地解释了，实用Carter-WegmanMAC是如何操作，以及为什么要这么做的。

11.7 认证加密模式

目前，本书已经明确地对加密和认证做了区分，并解释了为什么两者都是必要的。人们每天创建的大多数安全连接也是这样的：他们将加密和身份认证作为不同步骤的基础。

可以将身份认证作为模式操作的基础部分。本书已经介绍了没有认证的加密并不是我们想要的。不仅要使用方法来保证任意信息流的私密性，也要保证其完整性。

如本章提到的，很多加密和认证的组合是不安全的。一个固定的安全的方法可以被设计为认证加密的模式，一些应用的开发者可以不用再做选择，而是直接使用某种模式，这样也减少了他们犯错误的机会。

AEAD（Authenticated Ecryption With Associated Data）

AEAD是一些加密认证模式的特点。这些模式被称为AEAD模式。它是基于一个假设：很多消息实际上是有两部分内容组成：

• 真实的内容本身

• Metadata：一些关于内容的信息

在很多例子中Metadata应该是明文，但是内容本身是密文。整个消息是进行了认证的。对于攻击者来说他不能修改了metadata然后这个修改后的消息依然被认为是有效的。

设想一下电子邮件这个密码学例子。metadata内容可能会包含收件者信息。将邮件内容进行加密和身份认证，这样就只有收件者可以读它。metadata，必须是明文，因为邮件服务器需要以此来判断应该将邮件投递给谁。

很多系统的metadata是不进行认证的，这就导致攻击者可以修改它们。在本节的例子里，这就会导致电子邮件可能会投敌到错误的信箱。这就意味着攻击者可以将邮件投递给错误的人，或者使得邮件不被投递。

AEAD模式通过提供一个特定的方法来强调了这个问题，方法是将metadata和加密的内容组合到一起，然后进行认证，而不是两者完全分开。

image.png

11.8 OCB模式

OCB模式是一种AEAD模式。它是AEAD发展的早期版本。

可以看出OCB模式类似于ECB模式，名字OCB也和（Electronic code book）电子密码本很像。但是它没有ECB那样的安全问题。在OCB中有一些很重要的不同，就是在每一个要块加密的过程中引入的增量Δi。

作为一个AEAD模式，OCB模式提供了密码安全的身份认证tag t，它是由X来构建的，X是一个简单的（自身不一定是密码安全的）明文的校验码。另外的单独的tag ta，用来对AEAD的关联的数据做身份认证tag。这个关联数据的tag是这么计算的：

image.png

image-20210428150950157.png

原图有误，这里进行了修改。

这个设计由很多有趣的地方。例如，它很快：只需要简单地每个块进行加密对与加密的信息或者关联信息，最后进行一个额外的块加密操作用来生成最后的tag。增量Δi是很容易计算的。校验码X是所有明文块Pi进行疑惑。最后OCB模式是很容易并行计算的；只有最后的tag与前面的信息有关。

OCB模式同样也需要面临填充的问题：如果明文和相关联数据信息不是整好块的倍数。它和pkcs#5/pkcs#7填充有所不同，如果明文恰巧是块的整数倍，这里不会有整个的被浪费的填充块。

尽管OCB有很多有趣的特性，OCB模式并没有能收到更多的关注。这里有一个很大的原因是专利的阻碍。尽管很多专利协议是可用的，包括针对开源软件不需要付费的，依然对OCB模式的使用没有产生很大的影响。

11.9 GCM模式

GCM模式是一个AEAD模式,它是“Galois Counter Mode”的缩写。它在NIST的的gcm07中被正式提出，是一种将典型的CTR模式和Carter-Wegman MAC的结合。