通过构造Hash冲突实现PHP/Java等语言的拒绝服务攻击

前几天看到公司php群谈到这篇博文通过构造Hash冲突实现各种语言的拒绝服务攻击,说的是在PHP中，使用hash来存储k-v数据, 包括常用的来自用户的POST数据, 攻击者可以通过构造请求头, 并伴随POST大量的特殊的”k”值(根据每个语言的Hash算法不同而定制), 使得语言底层保存POST数据的Hash表因为”冲突”(碰撞)而退化成链表. 这样一来, 如果数据量足够大, 那么就可以使得语言在计算, 查找, 插入的时候, 造成大量的CPU占用, 从而实现拒绝服务攻击. 举个例子：如下代码中：

$size = pow(2, 16); // 16 is just an example, could also be 15 or 17
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size &#8211; 1) * $size; $key <= $maxKey; $key += $size) {
    $array[$key] = 0; 
} 
$endTime = microtime(true); 
echo 'Inserting ', $size, ' evil elements took ', $endTime - $startTime, ' seconds', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) { 
    $array[$key] = 0;
} 
$endTime = microtime(true);
echo 'Inserting ', $size, ' good elements took ', $endTime - $startTime, ' seconds', "\n";
//http://www.laruence.com/2011/12/30/2435.html

运行结果如下：

这招太厉害了，拼接一个POST请求，用很小的成本就能搞垮服务器。因为当hashtable退化成线性的链表了，每插入一个元素就需要遍历全部元素。

有同事构造了一个400K的攻击文件试了一下国内某网站XX，XX的邮箱登录CGI多用了一分钟来处理构造的请求，可以认为攻击有效。前者是对照组，plain.txt是同样尺寸的正常数据，后者是构造的攻击数据，400K，3.2W个键值.如图示

当然，发现这个漏洞后，PHP5.4是通过增加一个限制来尽量避免被此类攻击影响: – max_input_vars – specifies how many GET/POST/COOKIE input variables may be accepted. default value 1000.设置一个允许最大的的k-v个数。

Laruence说其他语言的比如java也中招了。有待达人给例子解释下。不过我试了试，java的数组本身大小支持不了多大，况且在用数组时已经先知道了array的size了。另外，java中servlet接受post等请求是用hashmap来保存的。我自己测试了下，通过类似的方法put(K,V);一个K是普通的，另一个K就是按照以上类似方法产生的。结果K的个数在Math.pow(2D, 19D);以及Math.pow(2D, 20D);时，乱序的K时间更少，Math.pow(2D, 18D)时，乱序的会用时多。(这两种情况每跑一遍结果都是这样)。更大的值就报OutOfMemoryError了。更小的值就差不多了(实测时用时多少两种方法不定)。求解释……

测试代码如下：

public static void testHashmap() {
    HashMap<Long, String> map = new HashMap<Long,String>();
    HashMap<Long, String> map2 = new HashMap<Long,String>();
    double size = Math.pow(2D, 20D);
    long startTime = Calendar.getInstance().getTimeInMillis();
    long index = 0L ;
    for(long i = 0L ; i < size; i++) {
       map.put(i, "0");
       index++;
    } 
    long endTime = Calendar.getInstance().getTimeInMillis();
    System.out.println(index + " values, test 1 : " + (endTime-startTime));
    System.out.println("\---\---\---\---\---\---\---\---\---\---\---\---\----");
    startTime = Calendar.getInstance().getTimeInMillis();
    index = 0L ;
    for(Long i = 0L ; i < (size-1)*size; i+=size) { 
        map2.put(i, "0");
        index++;
    } 
    endTime = Calendar.getInstance().getTimeInMillis();
    System.out.println(index + " values ,test 2 : " + (endTime-startTime));
}