月份：2012年1月

上一篇文章, 我介绍了一个利用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, ' 秒', "
";
    
 
    
$startTime = microtime(true);
    
$array = array();
    
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
    
    $array[$key] = 0;
    
}
    
$endTime = microtime(true);
    
echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "
";

上面的例子, 在我的机器上的执行结果如下:

    
插入 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算法是开源的, 已知的, 所以有心人也可以做到

上周的时候Dmitry突然在5.4发布在即的时候, 引入了一个新的配置项:

Added max_input_vars directive to prevent attacks based on hash collision

这个预防的攻击, 就是”通过调用Hash冲突实现各种语言的拒绝服务攻击漏洞”(multiple implementations denial-of-service via hash algorithm collision).

攻击的原理很简单, 目前很多语言, 使用hash来存储k-v数据, 包括常用的来自用户的POST数据, 攻击者可以通过构造请求头, 并伴随POST大量的特殊的”k”值(根据每个语言的Hash算法不同而定制), 使得语言底层保存POST数据的Hash表因为”冲突”(碰撞)而退化成链表.

这样一来, 如果数据量足够大, 那么就可以使得语言在计算, 查找, 插入的时候, 造成大量的CPU占用, 从而实现拒绝服务攻击.

PHP5.4是通过增加一个限制来尽量避免被此类攻击影响:

    
  - max_input_vars - specifies how many GET/POST/COOKIE input variables may be
    accepted. default value 1000

 

目前已知的受影响的语言以及版本有::

Java, 所有版本

JRuby <= 1.6.5

PHP <= 5.3.8, <= 5.4.0RC3

Python, 所有版本

Rubinius, 所有版本

Ruby <= 1.8.7-p356

Apache Geronimo, 所有版本

Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22

Oracle Glassfish <= 3.1.1

Jetty, 所有版本

Plone, 所有版本

Rack, 所有版本

V8 Javascript Engine, 所有版本

不受此影响的语言或者修复版本的语言有::

PHP >= 5.3.9, >= 5.4.0RC4

JRuby >= 1.6.5.1

Ruby >= 1.8.7-p357, 1.9.x

Apache Tomcat >= 5.5.35, >= 6.0.35, >= 7.0.23

Oracle Glassfish, N/A (Oracle reports that the issue is fixed in the main codeline and scheduled for a future CPU)

CVE: CVE-2011-4885 (PHP), CVE-2011-4461 (Jetty), CVE-2011-4838 (JRuby), CVE-2011-4462 (Plone), CVE-2011-4815 (Ruby)

原文: http://www.ocert.org/advisories/ocert-2011-003.html