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

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

这些需求通常通过所谓的“YOLO”构造来满足：即临时设计的函数，以明显、直接且通常错误的方式“解决”眼前问题。

事实上，这些问题比看起来要难。对我们来说，反复在客户带来的产品中看到自制的解决方案令人沮丧，因为这些问题早已有解。因此，让我们讨论几种常见的YOLO构造、它们的问题以及正确的替代方案。

YoloMultiHash

这是我们在Trail of Bits最常见到的YOLO构造。当客户有复杂的数据结构或值数组，并需要将其转换为Fiat-Shamir记录时，他们经常使用这种方法。

YOLO构造

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

问题

这里遇到的问题是编码歧义。

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

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

更好的选择

不要使用YoloMultiHash，而是使用专为将多个独立值哈希为单个结果而设计的函数。最著名的例子是SP800-185中定义的TupleHash。其他几种哈希函数支持或易于支持类似功能；例如，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)，攻击者可以计算攻击者选择的任何X的H(M‖X)。这意味着，给定YoloMAC(K,M) = H(K‖M)，攻击者可以在不知道K甚至M的情况下计算YoloMAC(K,M‖X)。

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

第二个问题

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

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

现在定义M′ = K2‖M，并使用K1作为我们的密钥计算MAC：C2 = YoloMAC(K1,M′) = H(K1‖M′)=H(K1‖K2‖M) = C1。我们刚刚找到了两个不同的消息/密钥对产生相同的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等），你需要使用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)。这个密钥现在适用于密码学上下文。简单易行！

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

问题

此时，你可能在想，“哦，我抓住了模式！是编码歧义！”

也许这是个问题，但在这个案例中甚至算不上问题。

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

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

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

在Alice方面，她阻止Mallory的能力只是线性的：如果她从YoloPBKDFt(S,P)切换到YoloPBKDF10t(S,P)，那么Mallory只需花费大约10倍的成本以相同速率攻击Alice的密码。如果Alice想将Mallory攻击她密码的能力减少一百万倍，那么派生她的密钥需要一百万倍的时间，这可能对Alice造成显著延迟——尤其是如果她输错了密码。

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

这种内存要求对Alice有利。现代计算机有千兆字节的内存，但即使小的内存要求也可能对Mallory进行并行密钥派生的能力施加重大限制，要求她比计算机更快地读写内存，或限制她一次可以测试的密码数量。

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

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

更好的选择

使用现代密码KDF。Argon2函数家族很棒，scrypt也是。它们中的任何一个都能很好地完成工作，并且两者的库广泛可用于多种语言。对于在FIPS世界操作的人来说，做这件事可能很困难。NIST SP800-63-3规定：

合适的密钥派生函数示例包括基于密码的密钥派生函数2（PBKDF2）和Balloon。应使用内存困难函数，因为它增加了攻击成本。

Balloon尚未被NIST批准，尽管PBKDF2（不是内存困难的）已被批准。如果你想确保可以指向NIST批准的函数，你可以使用内存困难密码KDF如Balloon或Argon2从密码和盐生成密钥K1，使用PBKDF2从密码和盐生成密钥K2，最后使用FIPS批准的函数如HKDF将它们组合成最终密钥K = HKDF(K1‖K2)。

总结

如果你还没有锁定哈希函数，花时间考虑你将使用哈希函数的所有方式，并让那指导你。较新的哈希设计考虑了多哈希和MAC等酷想法，如果不需要重新发明轮子，就不要。BLAKE2和BLAKE3原生支持键控哈希和MAC，KMAC在许多SHA3库中得到支持。TupleHash通常与KMAC一起实现，BLAKE2可以容易地适应多哈希。

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

如果你喜欢这篇文章，分享它： Twitter LinkedIn GitHub Mastodon Hacker News