Bug 771149 (CVE-2011-5036)

Julian Wälde and Alexander Klink reported a flaw in the hash function used in the implementation of the Ruby-rack arrays.  Ruby-rack arrays are implemented using the hash table that maps keys to values:

http://rack.rubyforge.org/doc/classes/Rack/Request.html

A specially-crafted set of keys could trigger hash function collisions, which
degrade hash table performance by changing hash table operations complexity
from an expected/average O(1) to the worst case O(n).  Reporters were able to
find colliding strings efficiently using equivalent substrings or meet in the
middle techniques.

This problem is similar to the issue that was previously reported for and fixed
in e.g. perl:
  http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf

Patch: https://gist.github.com/52bbc6b9cc19ce330829