消息认证码

介绍

我们之前讨论过如何确保 Alice 和 Bob 之间消息的保密性。我们看到我们可以使用对称密钥密码，例如 AES 或 ChaCha20，来加密 Alice 和 Bob 之间的消息，以便只有他们才能阅读。然而，当 Bob 收到来自 Alice 的消息时，他如何知道它确实来自 Alice，或者恶意方没有更改它？这就是真实性发挥作用的地方。例如，中间人 (MIM) 可能会在 Diffie-Hellman 协议中的密钥交换期间尝试冒充 Alice 和 Bob。该方案的工作方式如下：

1. Alice 选择一个随机数 aa 并计算 gaga 并发送它。
2. MIM 获取 gaga，选择 a′a′ 并将 ga′ga′ 发送给 Bob。
3. Bob 选择一个随机数 bb 并计算 gbgb 并发送它。
4. MIM 获取 gbgb，选择 b′b′ 并将 gb′gb′ 发送给 Bob。
5. Alice 获得共享密钥 gab′gab′，而 Bob 获得 ga′bga′b；他们的消息被 MIM 解密，MIM 可以读取它们，然后使用相应的密钥将它们重新加密给 Alice 或 Bob。

在不需要保密性的环境中，真实性也至关重要。例如，我们可以有一个身份验证标签，提供硬盘驱动器上文件完整性的证明。如果攻击者访问我们的硬盘驱动器，他可能会尝试更改我们操作系统中的文件。身份验证标签会告诉我们文件是否被修改过。

消息认证码 (MAC) 是一种原语，允许我们确保给定消息的完整性。可以使用几种构造，具体取决于上下文。两种常用的构造是 CBC-MAC 和 HMAC。MAC 在互联网协议安全 (IPsec)、安全外壳 (ssh) 和传输层安全 (TLS) 中发挥着重要作用，为每个传输的数据包生成身份验证码。

我们稍后将讨论如何将身份验证码与加密相结合以获得经过身份验证的加密，这可以保证语义安全性（即，攻击者无法从给定的密文中了解任何信息）和密文完整性，从而实现针对篡改的安全加密。

什么是 MAC？

消息认证码是一对高效算法，签名和验证，S,VS,V，它们在一组消息和标签上工作并使用密钥。密钥空间由一个 n 位字符串 0,1n0,1n 给出。如果我们知道密钥，我们可以添加身份验证标签并验证它们。签名算法采用消息 mm 和密钥 kk 并输出标签 tt：

S(k,m)=tS(k,m)=t

验证算法获取标签 tt、密钥 kk 和消息 mm 并输出一个布尔变量 bb，该变量告诉我们标签是否对应于给定的消息：

V(k,t,m)=bV(k,t,m)=b

MAC 构造必须是安全的，才能发挥作用；否则，攻击者可能会伪造消息。如果攻击者可以在不知道密钥的情况下找到有效的 m,tm,t 对，我们就说他制作了伪造品。

针对 MAC 的攻击

为了了解 MAC 是否安全，我们需要确定攻击者的能力以及什么是成功的攻击。

我们假设攻击者可以执行选择消息攻击 (CMA)。简单来说，攻击者可以自由选择任何消息 mimi，并且可以通过让 Alice 或 Bob 计算标签来访问相应的标签 ti=S(k,mi)ti=S(k,mi)。但他无权访问密钥。虽然这可能被视为一种笨拙的能力（因为他可以获取任何消息的标签），但这是可能在现实世界中发生的事情。攻击者的目标是，给定 i=1,2,...ji=1,2,...j 的 (ti,mi)(ti,mi) 对，找到一个新的有效对 t,mt,m，其中 m≠mim≠mi。此对称为存在性伪造。如果 MAC 在 CMA 下是存在性不可伪造的，我们就说它是安全的。

MAC 也可能因重放攻击而变得不安全。在这种情况下，攻击者可能会捕获从 Alice 到 Bob 的消息及其标签，然后稍后通过发送相同消息给 Bob 来冒充 Alice。为了避免这种情况，MAC 包括消息编号（随着每个新消息而增加）或时间戳，该时间戳与 MAC 中的原始消息一起进行身份验证。

通过伪随机函数 (PRF) 构造 MAC

当我们谈论分组密码时，我们看到了伪随机函数的示例。我们提到这些函数的行为类似于伪随机排列，其中我们采用消息 mm 并将其映射到所有可能的输出消息之一。例如，AES 分组密码是一个函数 f:K×{0,1}128→{0,1}128f:K×{0,1}128→{0,1}128，它采用 16 字节的消息并输出一个 16 字节的随机字符串。

我们可以从给定的 PRF 构造一个 MAC，该 PRF 采用空间 XX 中的消息（例如，最长为 GB 的消息），并在 YY 中输出一个标签（例如，一个 128 位字符串），g:K×X→Yg:K×X→Y 通过执行

t=g(k,m)t=g(k,m)

只要 PFR g 是安全的，并且输出集足够大，即元素数量 |Y||Y| 大于 280280，则此 MAC 是安全的。

如果标签空间很小，则攻击者有很高的概率输出正确的标签。

分组密码和加密哈希函数的行为类似于伪随机函数；因此，它们在构造 MAC 中的使用是合理的。在第一种情况下，我们得到 CBC-MAC，而在第二种情况下，我们得到 HMAC。

CBC-MAC

我们需要一个伪随机排列 (PRP) 来构建 CBC-MAC，例如分组密码。我们可以将 MAC 函数描述为 f:K2×M→0,1nf:K2×M→0,1n。它采用两个不同的密钥 k1,k2k1,k2、一条消息并输出一个标签。在使用 AES 作为 PRP 的情况下，n=128n=128。鉴于 AES 使用 16 字节的字，因此消息被分成相等的 16 字节块。如果消息不是 16 的倍数，我们总是可以方便地填充消息。我们称 m0,m1,...mNm0,m1,...mN 为组成消息的块，E(k,m)=CE(k,m)=C 为 AES 加密函数，其中第一个参数是密钥，第二个参数是消息块。该算法的步骤如下：

1. 计算 t1=E(k1,m0)t1=E(k1,m0)。
2. 对于 j=2,...,Nj=2,...,N 执行

t′j−1=tj−1⊕mjtj−1′=tj−1⊕mj

tj=E(k1,t′j−1)tj=E(k1,tj−1′)

3. 计算 t=E(k2,tN)t=E(k2,tN)

最后一步对于使 MAC 安全地抵御存在性伪造至关重要。如果省略步骤 3，那么我们可以执行以下选择消息攻击：

• 选择 mm
• 请求 t=E(k,m)t=E(k,m)
• 获取伪造消息 m,t⊕mm,t⊕m 的标签。

我们可以看到，通过执行计算，我们获得了一个有效的配对：

f(k,m||t⊕m)=E(k,E(k,m)⊕t⊕m)=E(k,t⊕t⊕m)=E(k,m)=tf(k,m||t⊕m)=E(k,E(k,m)⊕t⊕m)=E(k,t⊕t⊕m)=E(k,m)=t

其中我们使用了以下事实：a⊕a⊕b=ba⊕a⊕b=b (将 bb 与相同的位串进行两次异或运算返回 bb)。

NMAC

NMAC 结构基于级联图。在这种情况下，NMAC 函数是 g:K2×M→Kg:K2×M→K。与 CBC-MAC 中一样，我们将消息分成 N+1N+1 个相等的块，m0,m1,...mNm0,m1,...mN。为了获得标签，

1. 设置 t0=k1t0=k1。
2. 对于 i=1,...Ni=1,...N 执行 F(ti−1,mi−1)=tiF(ti−1,mi−1)=ti
3. 使用固定填充元素 fpadfpad 填充 tNtN，以便其长度对应于 MM 中元素的大小，tN+1tN+1。
4. 计算 t=F(k2,tN+1)t=F(k2,tN+1)

步骤 2 对应于级联。再次需要步骤 4 来防止长度扩展攻击。我们可以看到，如果我们知道级联 cascade(k,m)cascade(k,m) 的结果，那么我们可以附加任何字符串 ww 并获得级联 cascade(k,m||w)cascade(k,m||w) 的出口。

即使我们可以将 NMAC 与 AES 一起使用，但这在实践中证明是不方便的，因为密钥调度会发生快速变化。该策略最适用于加密哈希函数。

PMAC

NMAC 和 CBC-MAC 的问题在于它们是按顺序执行的。如果消息非常长，这可能会带来不便，因为我们无法利用多个处理器来加速计算。并行 MAC 通过采用不同的方案解决了这个问题。要构建 PMAC，我们需要两个函数：伪随机函数 F:K×M→MF:K×M→M 和一个采用密钥和计数器的函数 P:K×Z0+→KP:K×Z0+→K。要计算标签：

1. 对于 i=0,1,...Ni=0,1,...N，计算 mi′=mi⊕P(k1,i)mi′=mi⊕P(k1,i) 且 ti=F(k2,mi′)ti=F(k2,mi′)。
2. 计算 m′=m′0⊕m′1⊕...⊕m′Nm′=m0′⊕m1′⊕...⊕mN′。
3. 获得 t=F(k2,m′)t=F(k2,m′)。

通用哈希和一次性 MAC

比基于 PFR 函数的 MAC 更快的版本是一次性 MAC；这可以安全地防御所有对手。它们基于通用哈希函数，这些函数比加密哈希函数弱（它们不需要具有抗冲突性），但运行速度更快。通用哈希函数 (UHF) 采用密钥 kk 和消息 mm，并给出哈希 hm=UHF(k,m)hm=UHF(k,m)。唯一的安全要求是，对于任何两条消息 m1,m2m1,m2，对于随机密钥，它们哈希到相同值的概率可以忽略不计：

Pr(UHF(k,m1)=UHF(k,m2),k←K)=neg∀m1,m2Pr(UHF(k,m1)=UHF(k,m1)=UHF(k,m2),k←K)=neg∀m1,m2

首先，我们像之前一样将消息分成 NN 块。然后，我们将每个块解释为大有限域上的一个数字（即，每个块都是 0,1,2,..,q−10,1,2,..,q−1 中的一个元素）。我们可以将它们中的每一个作为多项式的系数。要构建 MAC，我们修复一个大素数 qq 并在 1,2,...q−11,2,...q−1 中取两个随机整数 a,ba,b。签名算法是

S(a,b,m)=aN+1+mNaN+mN−1aN−1+...a1m1+bmodqS(a,b,m)=aN+1+mNaN+mN−1aN−1+...a1m1+bmodq

该算法在点 aa 处评估其系数由 mimi 给出的多项式，加上 bb，并将结果模 qq 减少，以便标签也是有限域 FqFq 中的一个元素。

Poly1305 就是这样一种构造的示例，并与 AES 或 ChaCha20 结合使用（我们很快就会明白为什么我们需要将它们结合起来）以提供快速 MAC，例如，Google 使用它来保护 HTTPS 连接的安全。特别是，Poly1305 将消息分成 16 字节的块，通过向每个块附加一个额外的位，将每个块解释为以小端形式表示的 129 位数字。模数为 q=2130−5q=2130−5，最终结果通过取 21282128 的余数来减少。

一次性 MAC 的问题在于我们只能验证一条消息。攻击者可以轻松破坏该方案以获得 aa 和 bb。请注意，如果攻击者提交一条每条 mi=0mi=0 的消息，则 S(a,b,m)=bS(a,b,m)=b。然后，他可以发送消息 m1=1,mi=0∀i>1m1=1,mi=0∀i>1 并获取 S(a,b,m)=b+amodqS(a,b,m)=b+amodq 并恢复 aa。我们可以通过改进构造并结合伪随机函数来解决这个问题。

Carter-Wegman MAC

Carter-Wegman MAC 将 PRF 与一次性 MAC 相结合。如果 F:KF×0,1n→0,1nF:KF×0,1n→0,1n 是伪随机函数，S(kS,m)S(kS,m) 是安全的一次性 MAC，则 Carter-Wegman MAC 的计算方式如下：在 0,1n0,1n 中随机选择 rr 并计算

CW(kF,kS,m)=(r,F(kF,r)⊕S(kS,m))CW(kF,kS,m)=(r,F(kF,r)⊕S(kS,m))

伪随机函数的输入很小，即使 FF 比 SS 慢，它也会计算得非常快。我们将消息留给一次性 MAC，即使对于大型消息，它也可以有效地处理。

HMAC

要构造 HMAC，我们需要一个密钥 kk、内部和外部填充 ipad,opadipad,opad 和一个安全加密哈希函数 H:0,1⋆→0,1nH:0,1⋆→0,1n。签名算法是

S(k,m)=H(k⊕opad,H(k⊕ipad,m))S(k,m)=H(k⊕opad,H(k⊕ipad,m))

伪随机函数通过将 UHF 的结果与来自 PFR 的强随机输出进行异或运算来掩盖 UHF 的唯一弱点。

标签验证的时间攻击

如果 MAC 验证未正确完成，则可能会受到错误或攻击。针对实施不当的 MAC 验证方案的一种标准攻击是时间攻击。在验证中，验证者采用密钥 kk 和消息 mm，计算身份验证标签 t′t′，并比较接收到的标签 tt。一种简单的方法是执行逐字节比较，

t′[i]==t[i]t′[i]==t[i]

这种检查方式的问题在于，一旦两个字节不同，例如字节数 3，攻击者就可以确定前两个字节是正确的。攻击者可以尝试第三个字节的不同值并测量验证所需的时间。如果它增加了，他知道他至少找到了另一个正确的字节。该过程可以继续，直到他耗尽标签中的字节数，从而获得消息 mm 的有效标签 tt，从而能够生成存在性伪造。因此，教训是确保以恒定时间执行验证，以便不会从标签中泄露任何信息。

需要更改密钥

为了安全起见，MAC 需要足够长。如果不是，它们可能会受到暴力攻击。我们可以在更改密钥之前找到可以 MAC 的消息数量的界限。例如，在 CBC-MAC 中，它输出 {0,1}n{0,1}n 中的标签，如果对手可以查询长度为 ℓℓ 的 qq 消息，那么我们需要

q2ℓ22n≪1q2ℓ22n≪1

这意味着 qℓ≪2nqℓ≪2n。如果我们使用 AES，其中 n=128n=128，并且我们认为 2−32≈2×10−102−32≈2×10−10 足够小，那么 qℓ≤248qℓ≤248。鉴于 1 GB 的数据是 230230 字节，我们可以在更改密钥之前加密包含高达几 GB 的多条消息。

在使用 SHA-256 的 HMAC 的情况下，我们有 n=256n=256，并且在达到限制之前我们可以标记的消息量是 q≪2256/2q≪2256/2，对于我们的情况，这可能类似于 2100≈10302100≈1030

总结

诸如 AES 或 ChaCha20 之类的加密方案提供保密性，但不能确保消息的真实性，也不能确保攻击者没有修改它们。缺乏真实性可能导致破坏性攻击并破坏加密方案。消息认证码 (MAC) 提供了一种确保消息完整性的方法，我们可以将它们与加密方案结合使用以提供经过身份验证的加密。为了安全起见，MAC 需要满足在选择消息攻击下的存在性不可伪造性；给定一条新消息 mm，即使攻击者可以访问其他有效对 mi,timi,ti，他也不应该能够生成有效的身份验证标签 tt。可以从伪随机函数（例如哈希函数或分组密码（如 AES））或通用哈希函数获得 MAC，每种函数在速度、大小、并行处理等方面都提供优势和劣势。

• 原文链接： blog.lambdaclass.com/mes...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～