“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对空格和元素顺序的变化 largely 不敏感，因此使用不同库生成的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)（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