I would like to know if PHP's object implementation, which was introduced after their associative arrays, suffers from the same hash collision issues. I've read CPython's hash algorithm (it's quite beautiful) and I wonder if PHP internally represents objects as glorified hash maps also.
I was curious myself, so I went digging. Most of this stuff appears in `Zend/zend_object_handlers.c`. For objects with std_object_handlers set up on them (which I assume is most of them), zend_std_read_property can do quite a bit of work: it tries a search of the property info hash zobj->ce, then the zobj->properties hash, and then calling `__get()` with protection against __get loops, then giving up and returning null. zend_hash_quick_find(), as used for these lookups, takes a HashTable* as its first argument, which is also the type of a hash table in zvalue_value.
Thus, object properties are associative arrays, though I don't think there's an equivalent severity of attack compared to causing collisions with crafted GET/POST data, as the latter is automatically parsed. You'd have to be able to upload code to make evil objects.
Going through this exercise was fun, though:
<?php $x=new stdClass();
$x->{"b\0ar"} = 12;
$x->{"b\0"} = 14;
$x->{"\0bar"} = 18; // fatal error ?>
On a side note, Ruby does not appear to have that same problem as similar code executes in .02 seconds. I think it is probably because Ruby's hash function is superior.
This is a problem that hashtables have in general (unless they are randomized).
_ In the case of the Ruby language, the 1.9.x branch is not affected by the predictable collision condition since this version includes a randomization of the hashing function._
So there is some merit to what the commenter is saying, though I doubt he knew the above.
Actual ruby arrays (which are arrays and not hashes) will obviously not exhibit this problem though.
I think for all practical purposes, unless you're doing something really weird, the likelyhood of hash function collisions is rare enough that we don't need to think too much about it.
I think for all practical purposes, unless you're doing
something really weird, the likelyhood of hash function
collisions is rare enough that we don't need to think too
much about it.
(Unlike PHP, though, the Ruby community can head off these particular attacks by releasing a new version of Rack, while waiting for a new 1.8.x release containing a security patch.)
Meanwhile PHP will presumably do a similar set of fixes, though I haven't seen the announcement yet. There are workarounds for web apps that involve using extensions to limit the size of POST requests and/or the acceptable number of parameters in a POST request.