之前那个散列表漏洞

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4553 天前的主题，其中的信息可能已经有所发展或是发生改变。

看数据结构
处理散列表冲突的时候用了链表的方法
会想到之前那个漏洞，构造大规模的冲突key让散列表变成一张列表来让服务器运行缓慢
这个缺陷各种语言是怎么解决的？

9 条回复 • 1970-01-01 08:00:00 +08:00

mckelvin

2012-06-09 14:02:15 +08:00

fanzeyi

2012-06-09 14:31:21 +08:00

研究了下 Python 的解决方案：

http://bugs.python.org/issue13703

增加了 -R 选项.. 可以使用 -R 来启用随机化散列

然后在语言内部有一个最大碰撞值（貌似是 1000）

碰撞超过 1000 次就会报错.. (这样太不负责了喂..

bhuztez

2012-06-09 15:05:21 +08:00

正解应该是红黑树

liwei

2012-06-09 15:16:09 +08:00

原理很简单，就是在哈希表初始化的时候生成一个随机数，之后在计算哈希值的时候将key和这个随机数进行某种运算来形成一个新的key，同时查找的时候也进行同样的运算。

由于攻击者并不知道这个随机数是多少所以就很难构造特殊化的序列将哈希表退化成链表。

caoyue

2012-06-09 15:57:49 +08:00

记得当时 php 和 asp.net 的临时解决方案都是限制请求参数，不知道现在是否有数据结构上的解决方案了
使用更复杂的算法导致的就是请求效率降低，这是一个两难

tioover

2012-06-09 21:20:05 +08:00

@fanzeyi 想起了用Python写递归的东西的时候……

也就是说python开启server的时候必须加上 R 参数？

treo

2012-06-09 21:50:00 +08:00

这个有实际案例么？一般攻击者会直接DDoS吧，简单方便粗暴，效果立竿见影

echuman

2012-06-09 22:02:06 +08:00

百度查下咯

fanzeyi

2012-06-09 22:02:25 +08:00

@treo 如果利用这个漏洞 DoS 就够了