技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 安全 --> hash攻击的几点想法

hash攻击的几点想法

浏览:2809次  出处信息

    最近关于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

建议继续学习:

  1. HashMap解决hash冲突的方法    (阅读:11226)
  2. 关于memcache分布式一致性hash    (阅读:10685)
  3. MinHash原理与应用    (阅读:5839)
  4. LVS hash size解决4096个并发的问题    (阅读:5418)
  5. 无锁HashMap的原理与实现    (阅读:5324)
  6. 如果用户在5分钟内重复上线,就给他发警告,问如何设计?    (阅读:4862)
  7. Ubuntu 下Hash校验和不符问题的解决    (阅读:4468)
  8. 分布式系统hash策略    (阅读:3744)
  9. redis源代码分析 - hash table    (阅读:3530)
  10. 一致性hash算法    (阅读:3393)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1