跳到主要内容

6. 安全考虑事项

本文档不声明 FNV hash 算法适合用于密码学应用.

当主动对手是一个因素时, 应该考虑使用密码学哈希函数 (见第 1.2 节).

6.1. 诱导碰撞​

攻击者可能试图诱导碰撞, 以导致拒绝服务或服务降级. 请考虑以下简化示例: 维护一个包含 n 个 bucket 的哈希表, 某个条目 i 使用的 bucket 由以下内容确定:

hash(i) mod n

并且每个 bucket 都有一个链表, 包含所有哈希到该 bucket 的条目. 这样的安排可用于编译器中的符号表, 或用于路由器中的某些路由信息 (即 RIB (Routing Information Base)). 如果大量条目哈希到同一个 bucket, 则从表中检索或更新其中某个条目所存储信息的时间很可能显著变慢. 通常, 攻击者可以安排被哈希的不同条目数量比 n 大几个数量级, 即使 n 达到数万或数十万也是如此. 因此, 在该示例中, 无论哈希函数性质如何, 碰撞都必然会发生.

围绕该示例可能存在多种不同情况, 以下三种具有说明性:

  • 如果在上述场景中哈希函数的使用方式完全已知, 包括已知的 offset_basis, 例如本文档指定的标准 offset_basis, 则对手可以离线测试条目, 并生成任意一组哈希表索引会碰撞的条目. 在这些情况下, 对手无需实际提交条目进行任何试验, 也无需测量性能来发现碰撞. 随后提交这样一组条目会造成服务降级或拒绝服务. 对于 FNV, 使用对手不知道的 offset_basis 足以击败这种情况.

  • 如果对手无法检测何时发生碰撞或何时服务降级, 则只要对手无法预测哈希结果就足够了. 对于 FNV, 使用对手不知道的 offset_basis 可能足以防御这种情况.

  • 如果对手能够检测上述示例中碰撞导致的服务降级, 并能向进程提供大量可变条目, 则他们可以收集看似发生碰撞的条目集合. 即使可提交条目数量存在限制, 只要可以进行多次试验, 对手就可以收集多个集合, 每个集合内部的条目相互碰撞, 或者收集一个不断增长且所有条目都碰撞的集合. 然后, 通过提交这些条目, 对手可以造成服务降级或拒绝服务. 无论使用的哈希函数是 FNV 这样的非密码学哈希函数, 还是 [FIPS202] 或 [RFC6234] 中指定的密码学哈希函数, 这一点都成立. 在这种情况下的一种防御方式是检测是否正在发生大量碰撞 (这可能偶然发生, 但概率很低), 并在检测到时通过某种方式改变哈希算法后重新哈希这些条目, 并对后续条目使用改变后的哈希算法. 例如, 如果正在使用 FNV, 可以使用不同的 offset_basis 重新哈希, 然后继续使用该新的 offset_basis. 已有商业部署的路由器使用这种技术来缓解内部表中过多的哈希碰撞.

最后于 更新