首页 > 业界新闻, 网络安全 > Hash Collision DoS 问题

Hash Collision DoS 问题

2012年1月6日 发表评论 阅读评论 23,397 人阅读    

最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 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微信公众账号可以在手机端搜索文章

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

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——


本广告收入已由广告主捐给Wikipedia

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 4.65 )
Loading...
  1. 2012年1月31日14:17 | #1

    作为一个即将毕业的学生,无意中看到了你的酷壳程序员练级攻略,真的不敢想象那么多的技术在学校90%都没有接触过,我跟你差不多,目前大四在一家做系统集成的国企做Java开发,很迷茫,不知道自己未来的路到底该怎么走,看了你的升级攻略,感觉求知若渴,马上去图书馆借书学习,我每天都会来这里看技术文章,祝你博客越来越好。

  2. invalid
    2012年1月31日15:45 | #2

    @invalid
    其实也不一定要在hash函数上下功夫。

    hashmap 遇到冲突可以有几种处理策略。其中最简单常用的是开链表法,这就会被攻击;如果改用再散列法,那么攻击者就得找到能同时让两个不同散列算法冲突的数据,而这就近乎不可能了。

  3. invalid
    2012年1月31日16:09 | #3

    另外想起一点,java这个散列函数不好,对扰动不敏感,这才使得hash(AaBB)=hash(BBAa)了。

    更好的散列函数应该使得任意位置的扰动都会“雪崩”式扩散,使得结果面目全非。这样就无法简单的以不同次序拼接几个冲突字串的方式来构造大量不同冲突字符串了。

    当然,这样攻击者仍然可以“硬”算出几千个冲突串来攻击。此时可以结合前面提到的随机扰动和再散列技术,应该能够彻底解决hash冲突攻击问题。

    其中随机扰动可以放在再散列那步去做,因为正常数据本来就很少冲突,这样就可以避免在平时付出额外cpu时间(虽然不过是异或一个常数);而一旦发现冲突,先随机扰动然后再散列的模式就可以以极小的代价使得这种攻击无功而返。

    当然,这个方法可能有点过度设计了。

  4. null
    2012年2月23日14:56 | #4

    请问一下:Java未修复,Tomcat已修复,怎么理解?如果在Tomcat最新版本上开发jsp,是否有此问题?谢谢。

  5. 2012年2月27日10:19 | #5

    陈皓你好,
    你的文章写的太好了,
    不过,关于java里面的hash函数,你文章中的例子其实是HashMap里面的二次hash,
    而不是String本身的hash,而只有从String本身的hash函数才可以构造出Aa和BB的hash值是一样的
    我在http:/www.hetaoblog.com最近有一系列文章是说java里面的hash的,
    具体String的这篇在这里,
    http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode-string-hashcode/

    希望和你有交流:)

  6. 2012年2月27日10:23 | #6

    invalid :
    另外想起一点,java这个散列函数不好,对扰动不敏感,这才使得hash(AaBB)=hash(BBAa)了。
    更好的散列函数应该使得任意位置的扰动都会“雪崩”式扩散,使得结果面目全非。这样就无法简单的以不同次序拼接几个冲突字串的方式来构造大量不同冲突字符串了。
    当然,这样攻击者仍然可以“硬”算出几千个冲突串来攻击。此时可以结合前面提到的随机扰动和再散列技术,应该能够彻底解决hash冲突攻击问题。
    其中随机扰动可以放在再散列那步去做,因为正常数据本来就很少冲突,这样就可以避免在平时付出额外cpu时间(虽然不过是异或一个常数);而一旦发现冲突,先随机扰动然后再散列的模式就可以以极小的代价使得这种攻击无功而返。
    当然,这个方法可能有点过度设计了。

    比如md5算法可以认为是你说的一种hash算法,但是这类算法会带来巨大的时间成本;
    java目前的算法取了一个比较快的,并且也是相对还合理的算法;

    java的HashMap已经有二次hash,主要是对低位做处理,
    你说的取随机值作异或,我猜想,未必一定比现在的做法好; // 这个仅仅是猜想

  7. invalid
    2012年3月7日11:41 | #7

    @核桃博客
    比如md5算法可以认为是你说的一种hash算法,但是这类算法会带来巨大的时间成本;
    ————————————
    md5的确是满足要求的hash算法,但满足要求的hash算法并非仅md5一个。
    再者,md5等各种摘要算法也未必非要算出64位;想得到雪崩效应,也未必非md5/sha1不可。

    比如这个算法:
    http://stackoverflow.com/questions/114085/what-is-a-performant-string-hashing-function-that-results-in-a-32-bit-integer-wi
    很显然,每一位的改变都被扩散了,虽然扩散程度未必很大,但这个雪崩效应已经足以避免被人轻易构造出冲突。

    而且,这个算法仅用到了移位、加法和异或操作,这些对应的CPU指令都是单时钟周期的,效率非常高。至少比java里的“乘以31”操作高效太多。恐怕java里面那个乘以31的操作还没执行完,这个算法已经处理过2~3个字符了。

    可见,符合要求的优秀的hash算法,未必必然会和性能过不去。

    —————————-
    java的HashMap已经有二次hash,主要是对低位做处理,
    —————————————————————————
    二次hash 和 再散列 连一毛钱关系都没有。

    前面你说过了,java是把字符串变换成31进制;二次hash是为了把这个取值范围没边没沿的31进制数字散列进可访问的存储空间。

    也就是说,java中,直到所谓的“二次散列”执行之后,才能和前面贴的那个c算法等同。

    再散列和以上一筐一筐的东西,连半点关系都没有。

    我们知道,hash不可能没有冲突;那么如果有了冲突怎么办?

    显然,这篇文章提到的所有语言都用了“开链表法”——也就是说,发现冲突了,就在hash表后面再附加一个链表,把冲突的数据丢里面。

    而再散列法是怎么做的呢?
    它发现用java那个算法有冲突后,不是把这个字符串往垃圾桶(链表)一丢了之;而是用我贴那个c算法重新为这个字符串计算一次hash,根据第二次算出的hash值决定它将要存入的位置;这次仍然冲突的话,可以移位后再次hash,也可以回退到开链表法。

    很显然,想攻击再散列法处理冲突的hash表,就必须找到同时让java算法和c算法冲突的字符串,这是极其困难的。

    ———————-
    你说的取随机值作异或,我猜想,未必一定比现在的做法好; // 这个仅仅是猜想
    ————————
    我讨厌猜想。知道就是知道,不懂就是不懂。猜个什么劲。

    我把前面提到的那个c算法改造成随机扰动版的:
    uint32_t hash_string(const char * s, const char rand)
    {
    uint32_t hash = 0;

    for(; *s; ++s)
    {
    hash += *s ^ rand; //这里加扰,代价是一个时钟周期。在现在的低端cpu上大概会消耗20亿分之一秒
    hash += (hash <> 6);
    }

    hash += (hash <> 11);
    hash += (hash << 15);

    return hash;
    }

    现在,假设这个算法有java一样的漏洞,那么除非某次生成的hash_map对象刚好rand=0,否则攻击就不可能成功;而这个概率是1/256

    换句话说,如果过去他发一千个包就能搞挂服务器,那么现在平均得发二十五万个。

    ——————————————————————————
    至于java现在的做法,实在差劲之极。事实上,简单的把它现在的实现替换成我贴那个c版的,就能同时提高性能并在很大程度上避免hash冲突攻击。

    请看这里的一大坨hash算法。显然java只是恰好选择了其中比较平庸的一种而已:
    http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

  8. invalid
    2012年7月17日16:39 | #8

    刚看到云风的blog,lua 5.2.1的字符串hash调整了算法,就是为了对付这个hash dos攻击;处理办法和我的想法相同:
    1、算法中加了一个随机量
    2、改用了再散列法

    http://blog.codingnow.com/2012/07/lua_521.html
    http://lua-users.org/wiki/HashDos

  9. 2013年4月24日00:52 | #9

    说反了吧,应该是key不一样,value一样吧

  10. 2013年4月24日01:13 | #10

    另外Hash Collision导致的另一个问题是加密安全,2004年MD5和SHA1两大顶级加密算法被攻破,来自山东大学数学教授王小云:http://news.xinhuanet.com/newscenter/2005-03/25/content_2741030.htm
    对我国计算机领域顶级科学家还是要赞一个!

  11. lastspring
    2013年6月19日15:58 | #11

    没说反吧。hash表的建立就是基于key的,如果key值不一样的话那就是非常棒的hash表,但是如果hash的键值冲突的话,就需要别的处理方法,这里应该是书上所说的链接法。然后在相同的键值后面产生一个链。所以如果提交相同的key值的数据,就会使得hash表变成一个链表@Leo

  12. 2014年1月14日20:10 | #12

    在我业余时间自己写的网站中,采用两种不同的算法各计算出32位值(共64位值)来做的,很难构造出两种算法都同时发生碰撞的多个字串。就算发生碰撞时,我的解决方案不是传统上的链,而是二叉树,并对树各结点的创建和删除做统一的管理,减少内存的频繁分配和释放。经测试性能还是不错的。

  13. 江南烟雨
    2015年6月30日17:44 | #13

    @Leo
    没说反吧…

评论分页
1 2 6424
  1. 2012年1月31日12:57 | #1
  2. 2012年2月23日20:34 | #2
  3. 2012年4月11日13:15 | #3
  4. 2012年6月20日09:24 | #4
  5. 2012年6月20日12:04 | #5
  6. 2012年6月21日13:54 | #6
  7. 2012年6月22日05:41 | #7
  8. 2012年6月23日17:12 | #8
  9. 2012年9月3日22:08 | #9
  10. 2012年11月12日18:08 | #10
  11. 2012年12月4日00:57 | #11
  12. 2012年12月10日04:44 | #12
  13. 2013年2月24日11:02 | #13
  14. 2013年5月10日08:12 | #14
  15. 2013年5月10日09:39 | #15
  16. 2013年5月10日18:20 | #16
  17. 2013年5月11日01:07 | #17
  18. 2013年6月1日21:14 | #18
  19. 2013年6月3日09:26 | #19
  20. 2013年8月12日17:24 | #20
  21. 2013年8月31日12:41 | #21
  22. 2013年9月20日09:29 | #22
  23. 2013年11月10日16:46 | #23
  24. 2013年12月31日14:59 | #24
  25. 2014年6月9日23:37 | #25
  26. 2014年8月22日22:49 | #26
  27. 2014年8月23日02:31 | #27
  28. 2014年11月1日07:34 | #28
  29. 2014年11月1日08:52 | #29
  30. 2014年11月3日11:26 | #30
  31. 2014年11月19日09:47 | #31
  32. 2014年11月20日09:26 | #32
  33. 2014年11月27日11:32 | #33
  34. 2015年3月24日16:00 | #34
  35. 2015年7月19日16:21 | #35
  36. 2015年8月9日00:28 | #36