[ANN] CVE-2011-4815: Denial of service attack was found for Ruby's Hash algorithm

Subject:

Denial of service attack was found for Ruby's Hash algorithm

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 the latest version of ruby via my previous post.

http://mla.n-z.jp/?ruby-talk=391606

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  <[e-mail]>  and  Julian
Waelde  <[e-mail]>  for  reporting  this
issue.