Denial of service attack was found for Ruby's Hash algorithm (CVE-2011-4815)

Posted by Urabe Shyouhei on 28 Dec 2011

Impact

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.

Detailed description

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).

Affected versions

  • 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.

Solution

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.

Notes

  • 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#hash weakness. 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#hash outputs. 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

Credit to Alexander Klink alexander.klink@nruns.com and Julian Waelde jwaelde@cdc.informatik.tu-darmstadt.de 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 1.6.5.1 to fix the identical issue. Other ruby alternatives might also suffer.
  • Twitter account @hashDoS collects informations about hash colliision attacks.