Posted by Urabe Shyouhei on 28 Dec 2011
This is something related to computational complexity. Specially crafted series of strings that intentionally collide their hash values each other was found. With such sequences an attacker can issue a denial of service attack by, for instance, giving them as POST parameters of HTTP requests for your Rails application.
The situation is similar to the one found for Perl in 2003. In 1.8
series of Ruby, we use a deterministic hash function to hash a string.
Here the "deterministic" means no other bits of information than the
input string itself is involved to generate a hash value. So you can
precalculate a string's hash value beforehand. By collecting a series
of strings that have the identical hash value, an attacker can let ruby
process collide bins of hash tables (including
Hash class instances).
Hash tables' amortized O(1) attribute depends on uniformity of
distribution of hash values. By giving such crafted input, an attacker
can let hash tables work much slower than expected (namely
O(n2) to construct a n-elements table this case).
- Ruby 1.8.7-p352 and all prior versions.
All Ruby 1.9 series are not affected by this kind of attack. They do not share hash implementations with Ruby 1.8 series.
Our solution is to scramble the string hash function by some
PRNG-generated random bits. By doing so a string's hashed value is no
longer deterministic. That is, a
String#hash result is consistent only
for current process lifetime and will generate a different number for
the next boot. To break this situation an attacker must create a set of
strings which are robust to this kind of scrambling. This is believed to
be quite difficult.
Please upgrade to ruby 1.8.7-p357.
Bear in mind that the solution does not mean our hash algorithm is cryptographically secure. To put it simple, we fixed the hash table but we didn't fix
String#hashweakness. An attacker could still exploit it once he / she got a pair of a string and its hash value returned from
String#hash. You must not disclose
String#hashoutputs. If you need to do such things, consider using secure hash algorithms instead. Some of them (such as SHA256) are provided in Ruby's standard library.
For those who knows alternative hash algorithms inside our code base: we do not support them (they are disabled by default). By choosing them we consider you can read C, and you can understand what was wrong with the default one. Make sure that your choice is safe at your own risk.
Credit to Alexander Klink firstname.lastname@example.org and Julian Waelde email@example.com for reporting this issue.
EDIT some related links:
- CVE-2011-4815 is assigned to this issue.
- oCERT.org published an advisory about it.
- JRuby released version 22.214.171.124 to fix the identical issue. Other ruby alternatives might also suffer.
- Twitter account @hashDoS collects informations about hash colliision attacks.