- 本文地址: https://www.laruence.com/2011/12/30/2435.html
- 转载请注明出处
上一篇文章, 我介绍了一个利用Hash冲突(碰撞)来对各种语言(包括,PHP, Java, Ruby等等)实施拒绝服务攻击的可能, 但是没有给出实例, 文章发出后, @Ferrari同学给出了一个另外一篇文章Supercolliding a PHP array, 文章中作者介绍了一种基于PHP的冲突实例, 以及带来的性能恶化对比. 我就借花献佛, 翻译给大家看看.
你知道不知道, 插入65536个经过构造的键值的元素到PHP数组, 会需要耗时30秒以上? 而一般的这个过程仅仅需要0.1秒..
请看如下的例子:
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "\n";
上面的例子, 在我的机器上的执行结果如下:
插入 65536 个恶意的元素需要 43.1438360214 秒 插入 65536 个普通元素需要 0.0210378170013 秒
这个差别是不是很夸张?!
我在上一篇文章中介绍过, 经过特殊构造的键值, 使得PHP每一次插入都会造成Hash冲突, 从而使得PHP中array的底层Hash表退化成链表:
这样在每次插入的时候PHP都需要遍历一遍这个链表, 大家可以想象, 第一次插入, 需要遍历0个元素, 第二次是1个, 第三次是3个, 第65536个是65535个, 那么总共就需要65534*65535/2=2147385345次遍历....
那么, 这个键值是怎么构造的呢?
在PHP中,如果键值是数字, 那么Hash的时候就是数字本身, 一般的时候都是, index & tableMask. 而tableMask是用来保证数字索引不会超出数组可容纳的元素个数值, 也就是数组个数-1.
PHP的Hashtable的大小都是2的指数, 比如如果你存入10个元素的数组, 那么数组实际大小是16, 如果存入20个, 则实际大小为32, 而63个话, 实际大小为64. 当你的存入的元素个数大于了数组目前的最多元素个数的时候, PHP会对这个数组进行扩容, 并且从新Hash.
现在, 我们假设要存入64个元素(中间可能会经过扩容, 但是我们只需要知道, 最后的数组大小是64, 并且对应的tableMask为63:0111111), 那么如果第一次我们存入的元素的键值为0, 则hash后的值为0, 第二次我们存入64, hash(1000000 & 0111111)的值也为0, 第三次我们用128, 第四次用192... 就可以使得底层的PHP数组把所有的元素都Hash到0号bucket上, 从而使得Hash表退化成链表了.
当然, 如果键值是字符串的话, 就稍微比较麻烦一些了, 但是PHP的Hash算法是开源的, 已知的, 所以有心人也可以做到...
[…] PHP数组的Hash冲突实例 […]
I really like reading through a post that can make people think. Also, many thanks for permitting me to comment!
对于使用 json_decode 的程序，仍然会导致长时间卡住，因为 max_input_vars 只针对 form 表单，真正需要就加一个 strlen 判断吧。
非常喜歡這篇文章。非常期待閱讀更多。太棒了
Your article gives me another approach on this topic. I hope to read more articles from you.
The article is very useful for us, please update every day
停止从一个主题跳到另一个主题，该小组无法跟上您的步伐。
错误404，找不到幽默感，请继续滚动。
I really like reading through a post that can make people think. Also, many thanks for permitting me to comment!
I will carefully read the issues you just shared, I find there are some places that are not very clear
过去，霹雳舞流行得多，发生了什么事？ 如今人们对它的吸引力减少了。
The forum you shared is wonderful and very meaningful, I hope it will be implemented widely.
Your article is very useful, the content is great, I have read a lot of articles, but for your article, it left me a deep impression, thank you for sharing.
謝謝提供信息。你是最棒的。
congratulations! it’s a wonderful thing! I agree with your opinion!
[…] Hash-DOS 利用的 php Hash 冲突的问题。从 djb33 迁移到 Siphash，对于字符串输入，哈希输出的最高位设置为 1 […]
[…] Hash-DOS 利用的 php Hash 冲突的问题。从 djb33 迁移到 Siphash，对于字符串输入，哈希输出的最高位设置为 1 […]
[…] Hash-DOS 利用的 php Hash 冲突的问题。从 djb33 迁移到 Siphash，对于字符串输入，哈希输出的最高位设置为 1 […]
[…] PHP数组的Hash冲突实例 […]
[…] PHP数组的Hash冲突实例 […]
我的网站最近遭到攻击。 我希望这些攻击被彻底摧毁。
[…] 网上关于PHP Hash Collision的文章特别多，得益于很多年前鸟哥的一篇文章 PHP数组的Hash冲突实例，因为这篇文章让行业内的PHPer们都愿意花时间去了解。 […]
我已经了解了PHP，我什么都不知道。 谢谢！.
Hope that the site will be on top, to get more players and help people enjoy after the days tired.
[…] PHP数组的Hash冲突实例 标签c、linux、人工知能、哈希表 […]
[…] 網上關於PHP Hash Collision的文章特別多，得益於很多年前鳥哥的一篇文章 PHP陣列的Hash衝突例項，因為這篇文章讓行業內的PHPer們都願意花時間去了解。 […]
[…] 網上關於PHP Hash Collision的文章特別多，得益於很多年前鳥哥的一篇文章 PHP陣列的Hash衝突例項，因為這篇文章讓行業內的PHPer們都願意花時間去了解。 […]
[…] 这个问题其实很有意思，有一种web攻击叫做“Hash碰撞攻击”，简单而致命。一般的web服务器都用字典这种简单有效的数据结构来保存请求参数，如果我们发送一个请求，里面所有key都是相同的hash（所以如果想要使用这种攻击方式，必须知道目标服务器/编程语言的hash策略），服务器去保存你的参数时耗费的时间从Ο(1)变成Ο(n).这里有个例子，展示了PHP保存正常的65535个int值只需要0.021s，如果保存一个恶意构造的65535个int，需要42s！ […]
[…] 吓了我一跳！该函数的递归实现比循环快！仔细想了想代码，应该是PHP数组（$stack）的操作效率不高导致的，PHP数组本质上是一个Hash表——但想想也奇怪，看过“鸟哥”的文章， 在PHP中,如果键值是数字, 那么Hash的时候就是数字本身 […]
[…] 参考1 […]
[…] 还有PHP的 HASH DDOS (CVE-2011-4885) 攻击也在 PHP 5.3.9 跟 PHP 5.4中修复了。 […]
[…] 本文地址: http://www.laruence.com/2011/12/30/2435.html […]
[…] [7] http://www.laruence.com/2011/12/30/2435.html […]
[…] PHP数组的Hash冲突实例 […]
[…] 主要参考这里，hashtable实现的时候，都有冲突检测和冲突解决的机制，攻击者利用这个机制来构造一个超大的POST GET参数，这个参数恰好造成hashtable 也即php array在存储值的时候产生冲突，造成性能低下，占用系统资源，造成服务宕机。解决的方式必须得深入到PHP 内核里面来解决，比如控制解析POST GET参数的数量，或者控制解析这些外部变量构造的时候需要解析时间来降低拖慢服务器的问题。 […]
看了好久，为了一些人才看明白，很受教
[…] [4] PHP数组的Hash冲突实例 […]
请问，怎么用这个BUG攻击你的blog？挺起来好象这BUG很厉害的样子。
[root@WangXJ php_test]# time php f.php
插入 65536 个普通元素需要 0.053505897521973 sec
real 0m0.086s
user 0m0.080s
sys 0m0.004s
大神 我想请教下 为什么time 命令统计的时间real time会大于php自己统计的时间呢
请教鸟哥，有一点我还是不太明白，$size=pow(2, n)中n取值的缘由？
我把代码做了一些修改后测试发现，当n取值为14~18的时候，效果最好。大于或小于的话，速度都会明显变快。
[…] 详细内容：http://www.laruence.com/2011/12/30/2435.html […]
控制一下GPC三个超全局变量的解析时间是否就解决了潜在的DDOS攻击呢？
鸟哥，你的半官方补丁能发布出来么～～对很多人来说，非稳定版本的不敢用啊。
[…] PHP数组的Hash冲突实例 ), 这个攻击方法危害很高, 攻击成本也很小. […]
刚测试了下，发现个问题，请教下
在我本地虚拟机（32位ubuntu系统，512m内存，1核cpu，2.66GHz）上跑上面的程序：
插入 65536 个恶意的元素需要 90.800883054733 秒
插入 65536 个普通元素需要 0.026834011077881 秒
服务器（64位系统，2g内存，4核1.60GHz）上跑：
插入 65536 个恶意的元素需要 190.03647112846 秒
插入 65536 个普通元素需要 0.027021884918213 秒
这个差距是因为cpu频率的关系？php能利用多核的优势么？还是因为系统是32位或者64位的关系？
灰常不错，受教了。。。
沙发！
简单地说就是，通过构造一个 url ，或者一个 form ，参数的 key 就按这么 $key += $size 计算，那么就能拖慢所有使用存在此缺陷的 server ~，oh my god.