Hash 碰撞和解决策略

[scriptB0y]

• 恶意构造的元素插入到 hash 表可能比普通哈希表的速度慢几千倍！用 hash 碰撞攻击可能一台机器就能让网站趴下，所以尽量避免 hash 碰撞和防御 hash 碰撞攻击是必要的。
• 总结了 hash 碰撞的几种解决策略
• hash 表是如何工作的
• 贴了一些有意思的参考链接

https://www.kawabangga.com/posts/2493

[unique]

好文，get 了

[jadec0der]

Hash 碰撞攻击以前真没听说过，有意思

[rim99]

讲的挺好，就适合我这种小白

[holyghost]

你们四个是一个组的吧？

[scriptB0y]

@holyghost 商业胡吹

[wisej]

@holyghost 哈哈

[glasslion]

@jadec0der 前几年各大语言被集中报过一次， 现在基本被修复了

[iyangyuan]

啊？这叫哈希冲突吧老哥？！

[scriptB0y]

@iyangyuan 其实都一样！散列冲突，散列碰撞啥的 都是 collision

[linuxchild]

说真的，你推广博客就推广吧，没必要还互相吹，说难听都算是浪费后来人的时间了。

我读完了内容和链接内容，都有标题党都感觉了。

另外，博文逻辑感觉不清晰，我找了半天怎么解决哈希冲突，现在都不确定你有没有写。

最后，还不如之前数据结构书上讲的明白

[linuxchild]

再补充一下，看帖子第一感觉还以为是某种攻击方式

[scriptB0y]

@linuxchild 我不认识前面三个

[jimzhong]

健壮的 hash 表都有一个随机生成的 seed。

[zhicheng]

Hash 冲突攻击是利用开源编程语言公开的 hash 算法，提前计算出能够产生相同 hash 的字符串，让语言自带的 dict 类型性能从哈希表 O(1) 降到链表 O(n) 的攻击手段。

比如 HTTP 框架会用字典存储参数，这样我在 URL 里构造数千个能够产生相同 hash 的参数名 ，当你读这个字典的时候就会非常消耗 CPU。

解决办法很简单，编程语言在启动的时候生成一个随机数，以后每次计算 hash 都用这个随机数做 seed，因为别人几乎无法猜到这个随机数，所以也就没办法利用提前计算冲突 hash 进行攻击。

我在 Lemon 里就是这样实现的，以下为参考代码

https://github.com/lemon-lang/lemon/blob/master/src/lemon.c#L283
https://github.com/lemon-lang/lemon/blob/master/src/hash.c#L25

[trulyshelton]

讲的没啥错，就是，这不是最基本的 data structure 常识吗？

[scriptB0y]

@trulyshelton 是的