“YOLO”不是一种有效的哈希构造

在 Trail of Bits，我们经常看到一些密码学上的失误，其中最常见的就是“让我们用哈希函数构建自己的工具”。客户端遇到类似于“我们需要将一堆不同的值哈希在一起”或“我们需要一个 MAC”或“我们需要一个用于密码的密钥派生函数”的问题，而手头最接近的工具就是哈希函数。

这些需求通常通过所谓的 “YOLO” 构造来满足：临时的函数以一种显而易见、直接且通常是错误的方式 “解决” 当前的问题。

事实是，这些问题比看起来更难。对于我们来说，一遍又一遍地在客户带给我们的产品中看到自制的解决方案令人沮丧，因为这些问题已经被解决了。因此，让我们讨论一些我们经常看到的 YOLO 构造，它们的问题是什么，以及应该怎么做。

YoloMultiHash

这是我们在 Trail of Bits 看到的最常见的 YOLO 构造。当客户端有复杂的数据结构或值数组，需要将它们转换为 Fiat-Shamir transcript 时，他们通常会使用它。

YOLO 构造

给定一个哈希函数 H 和一组消息 M̂ = {M 1 ,M 2 ,…,Mn}，选择一个分隔符字符串 S，并计算 YoloMultiHash(M̂) = H(M 1‖ S‖ M 2‖ S‖ …‖ S‖ Mn).

问题

我们在这里遇到的问题是歧义编码（ambiguous encoding）。

如果消息可以包含分隔符 S 作为子字符串会发生什么？假设消息 Mi 包含 S 作为子字符串。将 Mi 分割成 Mi = M′ i‖ S‖ M′′i，并定义 M̃ = {M 1 ,…,M′i,M′′i,…,Mn}。那么我们就有了 YoloMultiHash(M̂) = YoloMultiHash(M̃). 这是两个语义上不同的输入，它们导致相同的哈希值。这类似于破坏了一个好的哈希函数的抗碰撞性要求，这是一个 非常糟糕的事情 (tm)。

这也不是一个假设性的问题：它已被用于破坏广泛使用的库的安全性。

更好的选择

不要使用 YoloMultiHash，而应该使用一个设计用于将多个独立值哈希成一个单一结果的函数。这方面最著名的例子是 TupleHash，它定义在 SP800-185 中。其他一些哈希函数也支持或使其易于支持类似的功能；例如，BLAKE3 规范描述了创建可以这样使用的“有状态哈希对象”的过程。

或者，更好地序列化你的数据。如果你想序列化一个数据结构，有很多很好的选择，比如 Protocol Buffers，CBOR 和 BCS。这些都会生成你的数据的无歧义编码，这意味着具有不同值的结构不会导致相同的哈希输入。根据经验，如果你要将结构化数据输入哈希函数，它应该是一种可以无损地转换回原始数据结构的格式。

(请注意，虽然许多序列化方法会创建 无歧义的 编码，但它们并不一定都生成 唯一的 编码。例如，JSON 在很大程度上对空格和元素顺序的变化不敏感，因此使用由不同库生成的 JSON 序列化可能会导致不同的哈希值。请小心！)

YoloMAC

YOLO 构造

给定一个密钥 K 和一条消息 M，计算 YoloMAC(K,M) = H(K‖ M). 有时人们会抛入一个盐值或自定义字符串 S，让他们进行域分离——类似于 YoloMAC(K,M,S) = H(K‖ S‖ M). 它实际上并没有改变下面攻击的本质，所以我们在这里只使用简化的版本。

第一个问题

YoloMAC 的第一个问题是众所周知的：长度扩展攻击。如果 H 是一个 Merkle-Damgård 哈希算法，就像 SHA256 一样，那么给定 H(M)，攻击者可以计算 H(M‖ X)，而不需要知道 K 甚至 M。

这听起来可能很傻，但是如果你有一个使用 encrypt-then-MAC 构造保护的消息，那么使用 YoloMAC 确实是一个问题。攻击者可以将垃圾数据附加到明文，更新 MAC 以匹配。根据底层格式，一些解析器会尝试处理垃圾数据。这可能会导致消息无法正确加载、解析器崩溃，或者可能泄漏时序信息，从而允许攻击者了解消息是如何被处理的。

第二个问题

第二个问题类似于 YoloMultiHash 的问题：歧义编码。无论哈希函数是否容易受到长度扩展攻击，此问题都适用，因此使用 SHA3、Skein 或 BLAKE3 也无法挽救你。

假设你有一条消息 M 和一个 256 位密钥 K = K1‖ K2，其中 K1 和 K2 各为 128 位。假设我们计算 C1 = YoloMAC(K,M) = H(K1‖ K2‖ M).

现在让我们定义 M′ = K 2‖ M 并使用 K1 作为我们的密钥来计算我们的 MAC：C 2 = YoloMAC(K 1 ,M′) = H(K 1‖ M′)=H(K 1‖ K 2‖ M) = C 1. 我们刚刚找到了两个不同的消息/密钥对，它们产生相同的 MAC。

根据底层文件格式的灵活性，这种灵活性可能允许 Alice 生成一个“根”消息 M̃ 和一个 128 位的可否认密钥 K̃，这样 M̃ 可以解析为一个有效的 PDF 文件，该文件指控 Bob 参与了与 Alice 的某种阴谋，但是 K̃‖M̃ 可以解析为一个无害的 JPG 文件。Alice 可以与 Bob 协商一个 128 位的 MAC 密钥 K，计算 V = YoloMAC(K,K̃‖ M̃)，然后将 V 和 K̃‖ M̃ 发送给 Bob。Bob 验证 V 并恢复无害的 JPG 文件。

Alice 联系当局并向他们提供令人信服的记录，证明她向 Bob 发送了一条带有 MAC V 的消息，然后向他们提供密钥 K′ = K‖ K̃ 和消息 M̃。当当局检查有罪 PDF 文件的真实性时，他们看到，实际上，YoloMAC(K‖ K̃,M̃) 与 Alice 提供的 V 匹配。

这并非遥不可及：已经通过使用 AES-GCM 标签 的类似问题演示了实际攻击。

这个问题在 Keccak 的情况下尤其常见，因为 Keccak 网站说：

与 SHA-1 和 SHA-2 不同，Keccak 没有长度扩展的弱点，因此不需要 HMAC 嵌套结构。相反，MAC 计算可以通过简单地在消息前面加上密钥来执行。

虽然 Keccak 不会受到 HMAC 旨在解决的长度扩展攻击的影响，但 “简单地在消息前面加上密钥” 这句话带有很多关于密钥长度和密钥格式的假设。

更好的选择

使用 HMAC、KMAC 或内置工具，具体取决于你的哈希函数。

如果你使用的是 SHA2 类的哈希（SHA256/384/512/etc.），你 需要 使用 HMAC；它的设计专门规避了长度扩展攻击。HMAC 自 1990 年代后期就已经出现了；这个问题已经解决了四分之一个世纪了。每个主要的密码学库都支持它。Python 甚至将它包含在他们的 标准库 中。没有理由自己滚动解决这个问题。

如果你使用的是 SHA3，请使用 KMAC。KMAC 在 2016 年被正式确定，并且许多 SHA3 库已经支持它。KMAC 也有几个有用的功能：

• 它可以用于 XOF 模式，这在某些情况下很有用，在这些情况下，MAC 也被用作敏感值的掩码。
• 当不作为 XOF 使用时，输出长度 集成到 MAC 的计算中，因此 192 位的 MAC 不仅仅是截断的 256 位的 MAC。
• 它包括用于轻松域分离的自定义字符串。

SHA3 是与 HMAC 一起使用的有效哈希函数，但 KMAC 比 HMAC-SHA3 更快且更灵活。

如果你使用的是 BLAKE2 或 BLAKE3，那么该算法中已经内置了密钥哈希模式，你应该使用它。与 SHA3 一样，你可以将 BLAKE2/BLAKE3 与 HMAC 一起使用，但密钥哈希方法将提供更好的性能。

YoloPBKDF

YOLO 构造

给定一个密码 P 和一个盐值 S，计算 K = YoloPBKDF(S,P) = H(S‖ P). 或者如果这符合你的要求，也可以使用 H(P‖ S). 此密钥现在适合在密码学上下文中使用。非常简单！

如果你想让它 真正 安全，只需迭代多次：设置 K 0 = P 并计算 YoloPBKDFi(S,P) = Ki，其中 Ki = H(S‖ Ki- 1 ).

问题

在这一点上，你可能会想，“哦，我明白了！这是一个歧义编码！”

也许这确实是一个问题，但这不是这种情况下的问题。

找到从密码派生密码学密钥的好方法是很难的。真的很难。就像 “多年的国际标准化工作” 一样难。这是因为将密码转换为密钥对于知道密码的人来说需要很容易，但对于任何不知道密码的人来说绝对是一场噩梦。讨论如何破解 YoloPBKDF 生成的密钥的密码学论文实际上是它们自己的类型：如何优化哈希软件以完成这项工作，如何构建定制硬件来进行密码破解，如何在表中缓存数据以进行时间-内存权衡，如何使用显卡加速破解工作，如何对密码选择进行建模等等。YoloPBKDF 不仅仅是众所周知的不安全；密码学家在这方面已经贬低了它几十年了。

……但它仍然出现在我们的安全审查中。

只需几个小时，Mallory 就可以租用使用 GPU 的 AWS 实例，以每秒测试数千亿个 YoloPBKDF 密码候选者。内存开销可以忽略不计：对于每个被攻击的密码，只有盐值、哈希状态和当前正在检查的密码。攻击的规模与处理器速度和可用处理器数量成线性关系：如果 Mallory 想加快她的计算速度，她可以添加额外的实例，或者在更高性能的 CPU 和 GPU 可用时切换到它们。

在 Alice 方面，她阻止 Mallory 的能力只是线性的：如果她从 YoloPBKDFt(S,P) 切换到 YoloPBKDF 10 t(S,P)，那么 Mallory 只需要花费大约 10 倍的代价才能以相同的速度攻击 Alice 的密码。如果 Alice 想将 Mallory 攻击她的密码的能力降低一百万倍，那么派生她的密钥将花费一百万倍的时间，这可能会给 Alice 带来明显的延迟——尤其是在她输入错误的密码时。

为了给 Alice 更多的优势，现代密码 KDF 不仅施加了处理要求，还施加了 内存 要求。如果你想从密码派生密钥，你需要在内存中生成一个大的值数组，然后对这些值执行特定的计算才能生成最终值。

这种内存要求使天平向 Alice 倾斜。一台现代计算机有千兆字节的内存，但即使是很小的内存要求也可能对 Mallory 并行执行密钥派生的能力施加重大限制，要求她以比她的计算机可以处理的更快的速度读取和写入内存，或者对她可以一次测试的密码数量施加限制。

例如，Argon2d RFC 包括一个推荐的参数集，该参数集施加 64 兆字节的内存要求。假设 Alice 在这些参数下派生密钥。如果 Alice 在一台具有 8 GiB 内存的典型笔记本电脑上派生她的密钥，则 64 MiB 仅占她内存的 0.8%。Alice 在她的资源方面使用非常少。另一方面，如果 Mallory 想通过每秒检查一百万个密码来攻击 Alice 的密钥，她将需要每秒生成和处理 64 兆兆字节 的数据。

Alice 甚至不会注意到使用内存硬函数从她的密码生成密钥所需的额外资源，但 Mallory 现在必须调集难以置信的资源才能获得她在使用 YoloPBKDF 时所能获得的 一小部分 速度。

更好的选择

使用现代密码 KDF。Argon2 函数家族 很棒，scrypt 也很棒。它们中的任何一个都可以很好地完成这项工作，并且两者的库都可以广泛用于多种语言。对于在 FIPS 世界中运营的人来说，这样做可能很困难。NISTSP800-63-3 声明如下：

合适的密钥派生函数的示例包括基于密码的密钥派生函数 2 (PBKDF2) 和 Balloon。应该使用内存硬函数，因为它会增加攻击的成本。

Balloon 尚未获得 NIST 的批准，但未经内存强化的 PBKDF2 已获得批准。如果你想确保你可以指向 NIST 批准的函数，你可以使用内存硬密码 KDF（如 Balloon 或 Argon2）从密码和盐值生成密钥 K 1，使用 PBKDF2 从密码和盐值生成密钥 K 2，最后使用 FIPS 批准的函数（如 HKDF）将它们组合成最终密钥 K = HKDF(K 1‖ K 2 ).

总结

如果你还没有锁定到某个哈希函数，请花一些时间考虑 所有 你将使用哈希函数的方式，并让它指导你。较新的哈希设计是在考虑了多哈希和 MAC 等很酷的想法的基础上构建的，如果没有必要重新发明轮子，不要 这样做。BLAKE2 和 BLAKE3 本身支持密钥哈希和 MAC，并且 KMAC 在许多 SHA3 库中都受支持。TupleHash 通常与 KMAC 一起实现，并且 BLAKE2 可以很容易地适应多哈希。

无论你需要对哈希函数做什么，你可能都不是第一个需要它的人。在这个领域已经进行了 大量 的研究，值得投入时间和精力来找到经过审查、经过充分研究的解决方案来解决你的问题，而不是发明你自己的解决方案。

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