hash攻击的几点想法
最近关于hash的攻击很火,这个问题存在的时间很久了。有几点想法,写出来和大家分享一下。
hash的好处是查找速度快,但是通过特殊的输入,会造成冲突链过长,查找会退化成一个链表遍历操作。对于hash来说,有几个重要的参数
1)hash table size,也就是hash的映射空间,很显然,hash表越大,映射的冲突几率就越小。
2)hash function,冲突取决于几个因素,一是输入源,二是hash function。好的hash function可以把非随机的输入源映射成随机的,比如MD5或者SHA这样的哈希函数,不同的输入,映射值肯定是不同的。但是MD5或者SHA的映射空间太大了,没法用做查找,而且映射速度也比较慢。所以一般用于校验而非查找。
3)冲突解决方法。链表法,相同哈希值的项,组成一个链表;开放地址法,有冲突,用另一个函数重新映射,这个方法对于冲突很多的情况是没办法解决的,只能覆盖或者丢弃冲突项。
对于完全随机的输入源,简单的哈希函数就可以保证映射也是随机的。好的哈希函数应该把输入的每个bit都考虑进来,并增加一个随机因子(系统初始化是设定,这样对相同的输入,每次系统重启后,映射值不同,对不同的系统,映射值也不同)。由于哈希表项是一个资源,每一个输入会占用一个资源,哈希表项并不是无限的,所以只要有足够多的无效输入就能耗尽哈希表项。所以这里的问题并不在于特殊构造的输入,而是如何能够识别哪些输入是无效的输入;再就是哈希表项的超时时间可以短一点。当冲突链退化到一定程度,应该启动攻击检测机制,限制来自同一源的输入。所以问题的核心是如何检测攻击,基于统计的方法应该是适用的。
在资源有限的情况下,对攻击源的识别就是重点,这也是DDoS检测和预防的重点。
http://en.wikipedia.org/wiki/Hash_table
建议继续学习:
- HashMap解决hash冲突的方法 (阅读:11226)
- 关于memcache分布式一致性hash (阅读:10685)
- MinHash原理与应用 (阅读:5839)
- LVS hash size解决4096个并发的问题 (阅读:5418)
- 无锁HashMap的原理与实现 (阅读:5324)
- 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (阅读:4862)
- Ubuntu 下Hash校验和不符问题的解决 (阅读:4468)
- 分布式系统hash策略 (阅读:3744)
- redis源代码分析 - hash table (阅读:3530)
- 一致性hash算法 (阅读:3393)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:droplet 来源: kernelchina blogs
- 标签: hash
- 发布时间:2012-01-03 23:23:10
- [68] 如何拿下简短的域名
- [68] Go Reflect 性能
- [64] Oracle MTS模式下 进程地址与会话信
- [61] IOS安全–浅谈关于IOS加固的几种方法
- [61] 图书馆的世界纪录
- [60] 【社会化设计】自我(self)部分――欢迎区
- [59] android 开发入门
- [54] 视觉调整-设计师 vs. 逻辑
- [49] 读书笔记-壹百度:百度十年千倍的29条法则
- [47] 界面设计速成