哈希洪水攻击

哈希洪水攻击的原理

在各种常用的数据结构里,有些数据结构的“平均运行时间”和“最差运行时间”会差很远,比如哈希表(Hash Table)

  • 如果这些元素的键(Key)极少出现相同哈希值,这项任务就只需 O(n)的时间。
  • 如果这些键频繁出现相同的哈希值(频繁发生碰撞),这项任务就需要 O(n*n)的时间。

哈希洪水攻击就是利用哈希函数的特点,构造一些数据,使他们经过哈希函数处理后的值与原来的值产生冲突(相同),增加整个系统的时间开销。

如何攻击

这里是一例实验

没有实践过,个人理解的一种利用方法是,构建符合接口的、能够产生冲突的 json 串,经过 jsondecode 以后,json 内部的数据会产生冲突,带来额外的开销。

(如果理解错误,欢迎更正)

如何防御

不能通过设置哈希函数的方式进行防御。如果知道哈希函数的实现时,只需要一点功夫就能够构造出一组频繁碰撞的键。

但是,你可以:

所以,我们应当

  1. 限制参数个数 ,检查用户上传数据。
  2. 添加一个哈希种子,使得攻击者需要花费 2^n/2^次碰撞方可找到一组冲突

顺带一提的是,有些语言在设计之初就考虑了哈希洪水攻击的防御,比如Python、Rust等,你可以选择使用它们来规避风险。