“YOLO”不是有效的哈希构造 - Trail of Bits博客
作者：Opal Wright | 2024年8月21日 | 密码学
在Trail of Bits常见的密码学失误中，“用哈希函数自建工具”是最普遍的案例之一。客户常面临类似这些问题：“需要将多个不同值一起哈希”、“需要MAC功能”或“需要密码密钥派生函数”，而他们手边最现成的工具就是哈希函数。
这些需求通常通过所谓的“YOLO”构造来实现：即用直观、直接但通常错误的方式“解决”即时需求的临时函数。
事实上，这些问题比表面看起来更复杂。我们反复在客户产品中看到自研解决方案时感到沮丧，因为这些问题早已有成熟解决方案。下面我们将讨论几种常见的YOLO构造、其问题所在以及正确替代方案。
YoloMultiHash
这是我们在Trail of Bits最常见到的YOLO构造。当客户拥有复杂数据结构或值数组，并需要将其转换为Fiat-Shamir转录本时经常使用此方法。
YOLO构造
给定哈希函数H和消息集合M̂ = {M₁,M₂,…,Mₙ}，选择分隔符字符串S，计算YoloMultiHash(M̂) = H(M₁‖S‖M₂‖S‖…‖S‖Mₙ)。
问题
核心问题在于编码歧义性。如果消息可能包含分隔符S作为子字符串会发生什么？假设消息Mᵢ包含S作为子字符串，将Mᵢ拆分为M′ᵢ‖S‖M′′ᵢ并定义M̃ = {M₁,…,M′ᵢ,M′′ᵢ,…,Mₙ}，则会出现YoloMultiHash(M̂) = YoloMultiHash(M̃)。这意味着两个语义不同的输入产生了相同的哈希值，这相当于破坏了良好哈希函数所需的抗碰撞性——这是非常严重的问题（商标提示）。
这并非假设性问题：它已被用于破坏广泛使用库的安全性。
更好选择
不要使用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 = K₁‖K₂（K₁和K₂各128位）。计算C₁ = YoloMAC(K,M) = H(K₁‖K₂‖M)。现在定义M′ = K₂‖M并使用K₁作为密钥计算MAC：C₂ = YoloMAC(K₁,M′) = H(K₁‖M′)=H(K₁‖K₂‖M) = C₁。我们刚刚找到了两个产生相同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)。现在该密钥适用于密码学场景。简单容易！
如果想更安全，只需多次迭代：设置K₀ = P，计算YoloPBKDFi(S,P) = Kᵢ，其中Kᵢ = H(S‖Kᵢ₋₁)。
问题
此时你可能想：“哦，我看出模式了！是编码歧义性！”这可能是个问题，但在此案例中甚至算不上主要问题。
从密码派生密码学密钥的良好方法非常困难。真正困难——相当于“多年国际标准化努力”的难度。这是因为将密码转换为密钥需要对知密者容易，但对不知密者绝对噩梦。关于如何破解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倾斜。现代计算机有GB级内存，但即使小内存要求也可能严重限制Mallory并行密钥派生能力，要求她读写内存的速度超过计算机处理能力，或限制她一次可测试的密码数量。
例如，Argon2d RFC包含推荐参数集，施加64MB内存要求。假设Alice在此参数下派生密钥。如果Alice在典型笔记本（8GiB RAM）上派生密钥，64MiB仅占其内存的0.8%。Alice使用的资源非常少。另一方面，如果Mallory想通过每秒检查百万个密码攻击Alice密钥，她需要每秒生成和处理64TB数据。
使用内存困难函数从密码生成密钥所需的额外资源甚至不会引起Alice注意，但Mallory现在必须调度惊人资源才能获得Alice使用YoloPBKDF时的一小部分速度。
更好选择
使用现代密码KDF。Argon2函数族和scrypt都很优秀，两者都能很好完成任务，且多种语言的库广泛可用。对于在FIPS领域操作的人员，这可能很困难。NIST SP800-63-3声明：
“合适的密钥派生函数示例包括基于密码的密钥派生函数2（PBKDF2）和Balloon。应使用内存困难函数，因为它增加了攻击成本。”
Balloon未获NIST批准，而非内存困难的PBKDF2已获批准。如果需要指向NIST批准函数，可使用Balloon或Argon2等内存困难密码KDF从密码和盐生成密钥K₁，使用PBKDF2从密码和盐生成密钥K₂，最后使用HKDF等FIPS批准函数将它们组合成最终密钥K = HKDF(K₁‖K₂)。
总结
如果尚未锁定哈希函数，请花时间考虑使用哈希函数的所有方式，并以此指导选择。较新的哈希设计考虑了多哈希和MAC等酷炫想法，如果没有必要，不要重新发明轮子。BLAKE2和BLAKE3原生支持密钥哈希和MAC，许多SHA3库支持KMAC。TupleHash通常与KMAC一起实现，BLAKE2可轻松适配多哈希。
无论需要用哈希函数做什么，你可能不是第一个需要它的人。该领域已进行大量研究，值得投入时间精力找到经过审查、充分研究的解决方案，而不是发明自己的方案。
更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）
公众号二维码
