Synopsis
Hour long presentation from the C3 security conference, on hash collision based attacks against web apps. The idea being that most web stacks automatically grab the query params and stick them into a hash of key-value pairs and by exploiting hash collisions an attacker can waste huge amounts of CPU time by a simple HTTP POST. In languages that don't randomly perturb their hashing functions (mostly DJBX33A or DJBX33X), collisions can be easily found and exploited.This affects node.js/v8, php, python, ASP, ruby, java and etc. Only perl (5.8.1 ~2003) and cruby (1.9 ~2008) are patched for randomized hashing functions. The v8 devs are unconcerned "because v8 is a client side language," which caused a bit of alarm for the node.js folks.
The presenters started their investigation after reading a mention in the perl security faq (perldoc perlsec), in the section Algorithmic Complexity Attacks, that before 5.8.1 perl had a security flaw where hash collisions could be exploited. 5.8.1 was released in 2003.
In Perls before 5.8.1 one could rather easily generate data that as
hash keys would cause Perl to consume large amounts of time because
internal structure of hashes would badly degenerate. In Perl 5.8.1
the hash function is randomly perturbed by a pseudorandom seed
which makes generating such naughty hash keys harder. See
"PERL_HASH_SEED" in perlrun for more information.
Thread from the node.js mailing list: "HOLY CRAP. nearly all nodejs http servers are vulnerable to DoS and apparently, the V8 guys seem to not care much"
Related Node.js followup:
