msgbartop
PHP语言, PHP扩展, Zend引擎相关的研究,技术,新闻分享 – 左手代码 右手诗
msgbarbottom

30 Dec 11 PHP数组的Hash冲突实例

上一篇文章, 我介绍了一个利用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表退化成链表:

Hash collision


这样在每次插入的时候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算法是开源的, 已知的, 所以有心人也可以做到…


分享到:



Related Posts:

Tags: , , ,

19 Responses to “PHP数组的Hash冲突实例”

  1. PHP递归和循环的速度测试 | 忆之 |

    [...] 吓了我一跳!该函数的递归实现比循环快!仔细想了想代码,应该是PHP数组($stack)的操作效率不高导致的,PHP数组本质上是一个Hash表——但想想也奇怪,看过“鸟哥”的文章, 在PHP中,如果键值是数字, 那么Hash的时候就是数字本身 [...]

  2. 今日两坑 » CoderAladdin |

    [...] 参考1 [...]

  3. PHP每次升级都升级了什么? | 东方网升技术中心 |

    [...] 还有PHP的 HASH DDOS (CVE-2011-4885) 攻击也在 PHP 5.3.9 跟 PHP 5.4中修复了。 [...]

  4. PHP数组的Hash冲突实例【拿来主义】 | 麻婆笔记 |

    [...] 本文地址: http://www.laruence.com/2011/12/30/2435.html [...]

  5. 开发中遵循或自创标准所衍生的安全问题杂想 » HorseLuke@微碌 |

    [...] [7] http://www.laruence.com/2011/12/30/2435.html [...]

  6. 绝尘博客 » Hash冲突构造拒绝服务攻击例子(PHP5.3.10以下版本) |

    [...] PHP数组的Hash冲突实例 [...]

  7. 标记它!博客 » Blog Archive » PHP hashtable拒绝服务攻击 |

    [...] 主要参考这里,hashtable实现的时候,都有冲突检测和冲突解决的机制,攻击者利用这个机制来构造一个超大的POST GET参数,这个参数恰好造成hashtable 也即php array在存储值的时候产生冲突,造成性能低下,占用系统资源,造成服务宕机。解决的方式必须得深入到PHP 内核里面来解决,比如控制解析POST GET参数的数量,或者控制解析这些外部变量构造的时候需要解析时间来降低拖慢服务器的问题。 [...]

  8. jimmyyem |

    看了好久,为了一些人才看明白,很受教

  9. PHP哈希表碰撞攻击原理 - 博客 - 伯乐在线 |

    [...] [4] PHP数组的Hash冲突实例 [...]

  10. a |

    请问,怎么用这个BUG攻击你的blog?挺起来好象这BUG很厉害的样子。

  11. wow |

    [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自己统计的时间呢

  12. linvo |

    请教鸟哥,有一点我还是不太明白,$size=pow(2, n)中n取值的缘由?
    我把代码做了一些修改后测试发现,当n取值为14~18的时候,效果最好。大于或小于的话,速度都会明显变快。

  13. 关于最近PHP的Array爆出的冲突问题 | 东海博客 |

    [...] 详细内容:http://www.laruence.com/2011/12/30/2435.html [...]

  14. dk |

    控制一下GPC三个超全局变量的解析时间是否就解决了潜在的DDOS攻击呢?

  15. HJin_me |

    鸟哥,你的半官方补丁能发布出来么~~对很多人来说,非稳定版本的不敢用啊。

  16. PHP5.2.*防止Hash冲突拒绝服务攻击的Patch | 风雪之隅 |

    [...] PHP数组的Hash冲突实例 ), 这个攻击方法危害很高, 攻击成本也很小. [...]

  17. mahone |

    刚测试了下,发现个问题,请教下
    在我本地虚拟机(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位的关系?

  18. mahone |

    灰常不错,受教了。。。

  19. kim |

    沙发!
    简单地说就是,通过构造一个 url ,或者一个 form ,参数的 key 就按这么 $key += $size 计算,那么就能拖慢所有使用存在此缺陷的 server ~,oh my god.

Leave a Reply

*