A PHP Array Hash-Collision Example中文EN

In my previous article, I described the possibility of using hash collisions to mount denial-of-service attacks against various languages (including PHP, Java, Ruby, and so on), but I didn't give a concrete example. After the article went out, @Ferrari pointed me to another article, Supercolliding a PHP array, in which the author describes a PHP-based collision example along with a comparison of the resulting performance degradation. I'll borrow someone else's flowers to offer to the Buddha and translate it for everyone here.
Did you know that inserting 65536 elements with specially constructed keys into a PHP array can take more than 30 seconds? Whereas the same process normally takes just 0.1 seconds..
Take a look at the following example:

<?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 'Inserting ', $size, ' malicious elements takes ', $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, ' ordinary elements takes ', $endTime - $startTime, ' seconds', "\n";

The result of running the example above on my machine is as follows:

Inserting 65536 malicious elements takes 43.1438360214 seconds
Inserting 65536 ordinary elements takes 0.0210378170013 seconds

Isn't that difference pretty dramatic?!
As I explained in my previous article, with specially constructed keys every single insertion in PHP causes a hash collision, which degenerates the underlying hash table of a PHP array into a linked list:

This way, every insertion forces PHP to traverse the whole linked list. As you can imagine: the first insertion requires traversing 0 elements, the second 1 element, the third 3, and the 65536th requires 65535 — so in total you need 65534*65535/2 = 2147385345 traversals....
So how is such a key constructed?
In PHP, if the key is a number, then the hash is just the number itself — usually index & tableMask. The tableMask exists to ensure that a numeric index never exceeds the number of elements the array can hold, i.e. the element count minus 1.
The size of a PHP hashtable is always a power of two. For example, if you store an array of 10 elements, the array's actual size is 16; if you store 20, the actual size is 32; and for 63, the actual size is 64. When the number of elements you store exceeds the array's current maximum element count, PHP resizes the array and re-hashes it.
Now, suppose we want to store 64 elements (resizing may happen along the way, but we only need to know that the final array size is 64, with a corresponding tableMask of 63: 0111111). Then if the first element we store has key 0, its hash is 0; the second time we store 64, and hash(1000000 & 0111111) is also 0; the third time we use 128, the fourth 192... This way the underlying PHP array hashes every element into bucket 0, degenerating the hash table into a linked list.
Of course, if the key is a string it gets a bit more complicated. But PHP's hash algorithm is open source and known, so a determined person can still pull it off...