I think the key thing to realize here is that when PHP says "array", they apparently mean "ordered map": if you are allowed to have 'foo' as a key, it is somewhat bothersome to call it an "array". Then, once you realize that it is actually a hashtable, it is fairly obvious that there will be a worst-case input set.

> PHP already landed a change (which will ship with PHP 5.3.9) which will add a max_input_vars ini setting which defaults to 1000. This setting determines the maximum number of POST/GET variables that are accepted, so now only a maximum of 1000 collisions can be created.

Wait, where did we establish that less user input = less array insertions?

If you're running a version of PHP which is patched with Suhosin (http://www.hardened-php.net/suhosin/) you'll already be protected from the DoS vector outlined in the article. By default Suhosin limits the max number of $_GET/$_POST/$_COOKIE parameters to 200.

> So if we insert a total of 64 elements, the first one 0, the second one 64, the third one 128, the fourth one 192, etc., all of those elements will have the same hash (namely 0) and all will be put into the same linked list.

This doesn't seem correct, or I'm missing something.

Upon the first insertion, PHP doesn't know that you intend to insert 63 more elements. It shouldn't allocate a 2^6-element underlying array until it exceeds 2^5 elements, right? So the first 2^5 insertions would be constant time, and only the next 2^5 would be linear.

I'm not sure how PHP performs the reallocation to increase an array's capacity. Maybe it allocates a blank array, and then inserts the existing elements using the standard insertion algorithm. In that case 2^6 linear-time insertions would occur -- half during the reallocation, and half afterwords. But it still bears mentioning that performance wouldn't tank until you inserted half+1 of the values.

Wait, what? Didn't we fix this in Perl forever (8 years) ago? Didn't everyone else fix it at the same time?

http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec...

How is any modern programming language still vulnerable to this?!

I could see lookup becoming slow but why is insertion affected? Isn't insertion into a linked list a O(1) operation?

I just ran this (using the PHP CLI) on my Lion MacBook Air and it took far, far longer than 30 seconds - 172, to be exact.

Not being at all familiar with the underlying mechanisms, does anybody understand why it would take so much longer on {PHP 5.3.6, Lion, my MacBook Air, the PHP CLI}?

From the article:

  But there is hope! PHP already landed a change (which 
  will ship with PHP 5.3.9) ...

This is going to be bad. I've never had the privilege of using PHP 5.3 during work hours; everything has always been stuck on 5.1.6 and 5.2.x.

Predictions:

a) People are going to jump to 5.3 in a hurry, or

b) RedHat will release a backport for RHEL (and Centos will release the patch in six months).

Either way, I think this will go unpatched in a large number of systems until DoS attacks become so common that a) and b) will need to happen.

Haven't tested it yet, but I believe that if you use suhosin patch you can limit the number of variables with suhosin.get.max_vars and suhosin.post.max_vars so you do not have to wait for php to the release the version with the patch (I guess most of the people do not compile PHP from Subversion trunk for production usage).

Using string keys: https://github.com/koto/blog-kotowicz-net-examples/blob/mast... (base 5?)

Didn't check in details yet but it might be interesting for the curious kind.

This is cool, can someone do the same for Python? (And other languages?)

undefined

Making a simple change of $size = pow(2, 16); to $size = 65535 removes the issue entirely.

Inserting 65535 evil elements took 0.030333042144775 seconds Inserting 65535 good elements took 0.020994901657104 seconds