Hash Collision DoS 问题

Hash Collision DoS 问题

最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比。这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%)。目前,这个问题出现于Java, JRuby, PHP, Python, Rubinius, Ruby这些语言中,主要:

  • Java, 所有版本
  • JRuby <= 1.6.5 (目前fix在 1.6.5.1)
  • PHP <= 5.3.8, <= 5.4.0RC3 (目前fix在 5.3.9,  5.4.0RC4)
  • Python, all versions
  • Rubinius, all versions
  • Ruby <= 1.8.7-p356 (目前fix在 1.8.7-p357, 1.9.x)
  • Apache Geronimo, 所有版本
  • Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 (目前fix在 5.5.35,  6.0.35,  7.0.23)
  • Oracle Glassfish <= 3.1.1 (目前fix在mainline)
  • Jetty, 所有版本
  • Plone, 所有版本
  • Rack <= 1.3.5, <= 1.2.4, <= 1.1.2 (目前fix 在 1.4.0, 1.3.6, 1.2.5, 1.1.3)
  • V8 JavaScript Engine, 所有版本
  • ASP.NET 没有打MS11-100补丁

注意,Perl没有这个问题,因为Perl在N年前就fix了这个问题了。关于这个列表的更新,请参看 oCERT的2011-003报告,比较坑爹的是,这个问题早在2003 年就在论文《通过算法复杂性进行拒绝式服务攻击》中被报告了,但是好像没有引起注意,尤其是Java。

弱点攻击解释

你可以会觉得这个问题没有什么大不了的,因为黑客是看不到hash算法的,如果你这么认为,那么你就错了,这说明对Web编程的了解还不足够底层。

无论你用JSP,PHP,Python,Ruby来写后台网页的时候,在处理HTTP POST数据的时候,你的后台程序可以很容易地以访问表单字段名来访问表单值,就像下面这段程序一样:


$usrname = $_POST['username'];
$passwd = $_POST['password'];

这是怎么实现的呢?这后面的东西就是Hash Map啊,所以,我可以给你后台提交一个有10K字段的表单,这些字段名都被我精心地设计过,他们全是Hash Collision ,于是你的Web Server或语言处理这个表单的时候,就会建造这个hash map,于是在每插入一个表单字段的时候,都会先遍历一遍你所有已插入的字段,于是你的服务器的CPU一下就100%了,你会觉得这10K没什么,那么我就发很多个的请求,你的服务器一下就不行了。

举个例子,你可能更容易理解:

如果你有n个值—— v1, v2, v3, … vn,把他们放到hash表中应该是足够散列的,这样性能才高:

0 -> v2
1 -> v4
2 -> v1


n -> v(x)

但是,这个攻击可以让我造出N个值——  dos1, dos2, …., dosn,他们的hash key都是一样的(也就是Hash Collision),导致你的hash表成了下面这个样子:

0 – > dos1 -> dos2 -> dos3 -> …. ->dosn
1 -> null
2 -> null


n -> null

于是,单向链接就这样出现了。这样一来,O(1)的搜索算法复杂度就成了O(n),而插入N个数据的算法复杂度就成了O(n^2),你想想这是什么样的性能。

(关于Hash表的实现,如果你忘了,那就把大学时的《数据结构》一书拿出来看看)

  Hash Collision DoS 详解

StackOverflow.com是个好网站, 合格的程序员都应该知道这个网站。上去一查,就看到了这个贴子“Application vulnerability due to Non Random Hash Functions”。我把这个贴子里的东西摘一些过来。

首先,这些语言使用的Hash算法都是“非随机的”,如下所示,这个是Java和Oracle使用的Hash函数:

static int hash(int h)
{
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

所谓“非随机的” Hash算法,就可以猜。比如:

1)在Java里, Aa和BB这两个字符串的hash code(或hash key) 是一样的,也就是Collision 。

2)于是,我们就可以通过这两个种子生成更多的拥有同一个hash key的字符串。如:”AaAa”, “AaBB”, “BBAa”, “BBBB”。这是第一次迭代。其实就是一个排列组合,写个程序就搞定了。

3)然后,我们可以用这4个长度的字符串,构造8个长度的字符串,如下所示:

"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa", 
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa", 
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa", 
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

4)同理,我们就可以生成16个长度的,以及256个长度的字符串,总之,很容易生成N多的这样的值。

在攻击时,我只需要把这些数据做成一个HTTP POST 表单,然后写一个无限循环的程序,不停地提交这个表单。你用你的浏览器就可以了。当然,如果做得更精妙一点的话,把你的这个表单做成一个跨站脚本,然后找一些网站的跨站漏洞,放上去,于是能过SNS的力量就可以找到N多个用户来帮你从不同的IP来攻击某服务器。

 

防守

要防守这样的攻击,有下面几个招:

  • 打补丁,把hash算法改了。
  • 限制POST的参数个数,限制POST的请求长度。
  • 最好还有防火墙检测异常的请求。

不过,对于更底层的或是其它形式的攻击,可能就有点麻烦了。

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (33 人打了分,平均分: 3.85 )
Loading...

Hash Collision DoS 问题》的相关评论

  1. 计算hash时附加一个随机的字符串参与计算hash值,然后存储这个随机字串和最终hash值,就不会有这种问题啦,再说这样子也不怕123456这种弱密码轻松通过常见hash查回来

  2. 没有微软的asp.net?是漏了,还是它的hash map方式是可以较好地抵御hash冲突攻击?

  3. 求真实遇到这个攻击的人分享症状!
    我的一台机器,目前不明确是否是这个原因:
    cpu瞬间从20%->400%,并且持续一直保持400%
    磁盘io瞬间大量爆发(猜想可能是链表使用频繁,linux做swap和物理内存的切换?),然后后面就迅速掉下来
    网络io略有增大,但是没有前面两项那么大幅度的增长

    重启机器后,tomcat没有oom的dump,说明当时tomcat还在跑;

    昨晚来不及细看,直接升级tomcat;

    诡异的是难道我一个完全不知名的小站也tmd有人来搞么?
    这真不好混啊

  4. @核桃博客
    我在我们产品(用的apache)已验证,轻轻发几十个包(每个post请求带10w个参数),就把我们至强8核的cpu跑满了。。。
    赶紧打补丁吧

  5. @smf
    谢谢
    补丁已经打了,
    请问你们cpu跑满的时候会不会出现io瞬间爆发的情况?

    具体我当时也不知道是啥原因,就在监控上看到cpu/磁盘io爆发,网络io略有增大不明显,

    其他的话ssh都登陆不了-_-

  6. @beyondme37
    原理大概就是:
    问题是出在计算key的hash函数。
    比如我们的存入一个哈希表的数据为整数,我们计算key的hash函数如下
    int hash(int x)
    {
    return (x % 5);
    }
    那我x输入6, 11, 16, 21, 26 … 返回的计算出的key都是1,都会存在哈希表1位置,即1位置冲突,而一般解决哈希表冲突的方法为拉链法,即数据全部存在1位置成单链表了,所以查找速度会下降为O(n)级别。

  7. 这个问题可以通过初始化HashMap/HashTable时设置特殊的参数来重现。但我的疑惑的是,这种问题在当前的JDK主流版本中会出现么?

  8. @wenbo
    不是服务器端处理所有字段,而是提交时,所有的字段要被装进$POST这个变量中。过程中如果hash冲突太多,就退化成单向链表。

  9. @tanglei
    我对web服务器如何处理post知之甚少。是不是说web server要把所有字段都插入hash table里,上层的应用不能对此决策?

  10. 很好奇都是怎么修复漏洞的?

    改算法?根本就没有不冲突的hash函数,抵抗了Ab BB,未必能抵抗其它……

    想来想去,好像只有随机为每次请求选择不同的hash函数/参数比较好?

    至于限制请求长度,偶觉得不太符合偶的完美主义精神……病……

  11. @wenbo
    可以简单理解为,tomcat 之类给你做了一个基础框架,这个框架会事先把提交的请求解析并装载在某个hash_map里——那些会冲突的KEY可以理解为参数名,KEY=后面的值则是该参数的取值。

    然后,你的脚本不再需要解析http请求,而是直接从容器中用参数名取出各个参数的实际值即可。

    这个攻击针对的是第一步,即底层架构”预先解析请求并将解析出的内容存储在某个容器内”这个步骤。

    底层架构并不知道上层应用要如何解释这些参数,所以它只能把所有参数缓存起来等待处理;至于上层应用,此时并未被唤起,所以也无法对此决策。

    至多可以在部署时通过配置声明“在我的所有网页里,最多会用到1000个参数”,或者“在我的应用里,参数及其内容加起来最多10K字节”。

  12. 明白了~,拉链的hash表。。。貌似只要换一个让hacker难以构造相同key的hash算法就解决问题了~

  13. 陈皓, 我准女朋友 是 美国加州大学尔湾分校的计算机网络博士生, 她把我网络控制住了, 我找了几个计算机高手都制不住她 ,你有什么好办法吗?1

  14. @invalid
    因为那些hashtable的hash函数都是用的开源标准库里的。攻击者就是根据开源代码来产生生成那么多的哈希碰撞。改下代码,原来的攻击方法就无效了

  15. 所有的hash算法都会有碰撞,我的建议是有一个像rsa公钥对一样的算法,能够用自己的公钥来对算法过程“独特化”,通过一个模板算法,利用密钥进行hash算法’实例化‘,比如你上面提到的:

    static int hash(int h)
    {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
    }

    可以修改为:
    static int hash(int h)
    {
    h ^= (h >>> v1) ^ (h >>> v2);
    return h ^ (h >>> v3) ^ (h >>> v4);
    }

    而通过密钥可以设置v1,v2,v3,v4的值,从而生成‘独特化’的算法,这个思路也不违背”算法是否加密悖论“,因为生成模板是一个通用机制。

    我想用这样带有一定定制化的算法过程,可以预防哈希冲突甚至很多地方的哈希应用问题。

  16. @intijk
    想法不错。

    不过,具体针对这个算法来说,它的关键应该是V1~V4之间的距离(Vm-Vn的差,不知道用啥词儿表述了,冏)。

    如果V1~V4距离不变的话,至多尝试int的bit数次,就可以再次找到冲突,这和不改没什么区别;但如果V1~V4距离改变了,传入值可能就无法充分散列。此时不需攻击,性能就很难看了;即便选择了不错的V1-V4,可选范围也太窄了,对int来说,可能几十或几百次尝试就能再次构造出攻击数据来……

    我觉得还是根据时间异或一个随机数比较好(这个随机数可存于hash表头某处):
    static int randHash(int h, int rand)
    {
    return hash(h ^ rand);
    }

    这样,原来不是Aa BB冲突吗?异或个随机数,它就可能冲突也可能不冲突了;大概估计,冲突概率会低到接近1/max_int数量级;再攻击就划不来了。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注