4 ms·
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 somewh
by saurik 15y ago
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.
- subwindow 15y agoYes that is just one way in which PHP is annoying. I think they actually refer to it as an "associative array", which as far as I can tell is exactly a hash, but they never refer to it as one. 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.
- nikic 15y agoActually this is not specific to PHP at all. Ruby just uses a different hashing algorithm so you need to set different keys to get these results. This is a problem that hashtables have in general (unless they are randomized).
- mdwrigh2 15y agoRuby 1.9's hash function has been randomized for awhile now, and I believe that 1.8.7 got a patch fixing this yesterday.
- dangrossman 15y agoRuby's not immune to this... http://www.ocert.org/advisories/ocert-2011-003.html http://www.ocert.org/advisories/ocert-2011-003.html
- alinajaf 15y agoWell hold up a second... quote from that link: _ 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.
- damncabbage 15y agoI 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. Except that, like with PHP, the worrying part is that someone can stuff rack.request.form_hash or rack.request.query_hash (a la PHP's $_POST and $_GET). (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.)
- subwindow 15y agoYes it is, and it has been for at least a year.
- mechanical_fish 15y agoHaving just done this research... Ruby 1.9 has apparently had randomized hash functions for years. Ruby 1.8.7 and JRuby were apparently vulnerable until yesterday, but both released fixed versions yesterday. 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.
- tiles 15y agoPHP uses the parlance "associative array" most often, to be fair. The confusion is really that PHP has few types that cover a lot of features. PHP combines its numerically-indexed array type with its ordered maps, and if you start by using numbers as keys, there's no conversion once you introduce a String key that makes it associative. Array functions (pop/push) will continue to work, as will dictionary key sorting, etc. 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.
- sapphirecat 15y ago> 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 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 ?> The "property starts '\0'" case is specially checked by the standard property handler, with no explanation...
- nikic 15y agoA leading null byte is PHP's way to mark protected and private properties. See this: http://codepad.viper-7.com/TXMSbw http://codepad.viper-7.com/TXMSbw