InfoQ:哈希表之殇

2月 7th, 2013 Categories: 后端, 技术

简单来说,当php生成一个数组时,便根据数组的大小生成一个hash表,当数组的key值为数值时,就把key当作hash表的key值,所以我们可以通过构造这个key值来使hash表退化成一条链表,没存放一个数组的值都要去遍历这个链表,导致效率无比低下,废话不多说看看下面代码 同样是存放6万多个数字的数组,没有经过构造key的数组只要0.02秒,经过构造退化的数组需要67秒。

注意第一个步长为1,会平均放到hash表中,元素进来基本不用遍历链表,第二个步长为数组的长度,每次元素进来都是同一个key值,所以都会去遍历相应的链表再存放,导致效率低下,下面是执行时间对照

看到没有,通过这样简单的处理key值,可以通过一般的pc就可以占用牛逼的服务器的Cpu 也就是让你服务器宕机。通过上面的例子差不多也可以看出,php给数组分配给一个数组大小的空间。

 

在成功构造好一个可以使哈希表完全退化成链表的键值集合后,攻击者需要来解决第二个问题:如何使用该集合在服务器端建立一个哈希表数据结构。

这个问题事实上已经再简单不过了:在所有的web应用中,为了方便程序对web请求的各项参数进行快速读操作,HTTP Request中的Header, Form以及QueryString,都使用了哈希表进行存储。那么剩下的工作很简单:就是以我们精心构造好的键值列表作为一次HTTP请求的Header,Form或者QueryString就可以了。实际攻击中,由于大量Form表单的Post构造更加简单,甚至可以使用浏览器完成,所以也会通常成为进行攻击的首选突破口。通过在单机上重复构造大量的HTTP Post请求,向Web服务器发送大量表单数据,会使得目标服务器的CPU迅速被占满而失去服务能力,达到攻击目的。

如果对方的服务器数量比较多,或者防火墙敏锐地发现了攻击者短时间内向服务器Post大量数据的行为,并进行了阻截,那么有可能还是达不到让对方“拒绝服务”的目的。这种情况下,攻击者会倾向于使用一定数量的“僵尸网络”对目标发起攻击。由于这个攻击非常简单,只需要构造一个HTTP请求即可实现,那么你可以去自己创建一个内容非常吸引人的页面,或者利用一个访问量较大但是存在跨站脚本漏洞(XSS)的页面,在页面中加入一小段对最终用户不可见,但是会自动发送一个Post请求到目标站点的JavaScript脚本,你的拒绝服务攻击(DoS)就成功升级为分布式拒绝服务攻击(DDoS)了。而访问这些页面的普通用户,则会在不知情的情况下成为帮助你继续攻击的“僵尸”群。

文章的最后,还是想补充一下关于针对这类攻击的防护工作。目前绝大部分的补丁都是针对HTTP请求中表单项的数量加以限制。这个方法确实有效。测试数据显示,1000个元素的链表操作对性能的影响还是可以接受的。但是如果你的Web应用在服务端需要接收某个表单项,并通过字符处理(不管是XML还是JSON)将用户输入的表单值转换成哈希表的话,那么很遗憾,目前这些补丁都帮不了你,你的应用将依然存在被拒绝服务攻击的可能。只不过攻击的方式从构造HTTP Request中的哈希表,变成了构造实际业务处理代码中的哈希表。对这一问题的完美解决方案,应该是如Perl在n年前做的那样:在哈希算法中引入随机盐使得构造哈希冲突变为不可能。

参考文章

关于作者

殷钧钧(Joey Yin),Web开发者,某外企企业架构师。业余时间,他是一名白帽子,独立安全组织OWASP成员。主要关注的技术领域有应用安全、分布式系统架构、以及程序员的敏捷实践。个人博客:http://unclejoey.com

http://www.infoq.com/cn/articles/hash-table

 

Tags: ,
尚无评论.

留言回复