Hash Collision DoS 问题

标签: 业界新闻 网络安全 Hash Java 安全 | 发表时间:2012-01-06 00:36 | 作者:陈皓 mazhechao
出处:http://coolshell.cn

最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 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的请求长度。
  • 最好还有防火墙检测异常的请求。

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

(全文完)

您可能也喜欢:

JAVA的字符串拼接与性能

由一个问题到 Resin ClassLoader 的学习

Java书籍Top 10

C++和JAVA传统中积极的一面

20非常有用的Java程序片段
无觅

相关文章

相关 [hash collision dos] 推荐:

Hash Collision DoS 问题

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

关于Hash Collision DoS漏洞:解析与解决方案

- - ITeye资讯频道
最近一个Hash Collision DoS(Hash碰撞的拒绝式服务攻击)漏洞影响颇大,有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比,本文试图对这一漏洞的原理及可采取措施做一解析,供大家参考. 一言蔽之, 该安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松地让你的CPU升到100%).

DOS的历史

- andi - 阮一峰的网络日志
昨日(7月27日),微软公司的DOS操作系统迎来了30岁生日. DOS是历史上一个划时代的产品,标识着PC(个人电脑)的崛起和普及,对计算机行业影响深远. 只有了解DOS的历史,才能理解今天的计算机工业从何而来. 1974年4月,Intel推出8位芯片8080. 这块芯片的体积和性能,已经能够满足开发微型电脑的需要,标志微机时代即将来临.

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类:  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法( consistent hashing ).

DOS命令管理

- - CSDN博客推荐文章
DOS远程桌面连接命令 mstsc /v: 192.168.1.250 /console. cmd          运行        command. 删除文件        rd        文件名/S. 创建文件        MD        文件名 . 1.        net user admin godmour /add 新建一个用户名为 admin 密码为 godmour 默认为user组成员.

局部敏感Hash

- - xiaobaoqiu Blog
之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东. LSH可以理解为一种衡量文本相似度的算法,特点是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证. 其有坚实的理论依据(98年左右理论就提出来了,99年有第一版实现)并且在高维数据空间中表现优异.

HTTP DoS 攻击工具 Slowhttptest

- Le - 开源中国社区最新软件
Slowhttptest是一个依赖于实际HTTP协议的Slow HTTP DoS 攻击工具,它的设计原理是要求服务器所有请求被完全接收后再进行处理.

Hash算法的使用

- khsing - Glider&#39;s home
在对语料文本进行2,3元切分时,需要借助hash表来获得切分内容在内存中的位置,以便能够记录语料库中出现的次数. 以前知道有很多hash算法,但没认真研究过,今天才知道hash算法差距还是很明显的. 首先我选择的是暴雪在魔兽里的hash算法,这个算法很高级,是time33类型的一个变种(有关time33的介绍,可以参考:http://www.cnblogs.com/napoleon_liu/articles/1911571.html),而且很巧妙的借助3次hash避免字符串比较这种费时的操作,并且不用链表来存储冲突,3次hash冲突值能相等的可能行只有1/10的23次方,应该说不可能冲突了.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

一致性HASH算法

- - 企业架构 - ITeye博客
一致性 hash 算法( consistent hashing ). consistent hashing 算法早在 1997 年就在论文 . Consistent hashing and random trees 中被提出,目前在cache 系统中应用越来越广泛;. 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;.