Bug 750564 - (CVE-2011-4815) CVE-2011-4815 ruby: hash table collisions CPU usage DoS (oCERT-2011-003)
CVE-2011-4815 ruby: hash table collisions CPU usage DoS (oCERT-2011-003)
Status: CLOSED ERRATA
Product: Security Response
Classification: Other
Component: vulnerability (Show other bugs)
unspecified
All Linux
medium Severity medium
: ---
: ---
Assigned To: Red Hat Product Security
impact=moderate,public=20111228,repor...
: Security
Depends On: 768828 768829 768830 768831 768833 770818 771529 771535 802932 844296
Blocks: hashdos/oCERT-2011-003 750567
  Show dependency treegraph
 
Reported: 2011-11-01 11:21 EDT by Jan Lieskovsky
Modified: 2015-11-24 09:43 EST (History)
9 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2012-02-13 08:45:14 EST
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)
Proposed patch by ruby security team. (6.44 KB, patch)
2011-11-30 12:49 EST, KOSAKI Motohiro
no flags Details | Diff
patch Dec 11 (6.21 KB, patch)
2011-12-11 13:49 EST, KOSAKI Motohiro
no flags Details | Diff
patch provided by oCERT (official upstream patch) (6.21 KB, patch)
2011-12-12 14:31 EST, Vincent Danen
no flags Details | Diff
RHEL-5.8 patch (5.63 KB, patch)
2011-12-21 11:29 EST, Vít Ondruch
no flags Details | Diff
RHEL-4.9 patch (7.19 KB, patch)
2011-12-23 09:24 EST, Vít Ondruch
no flags Details | Diff
RHEL-4.9 patch (3.95 KB, patch)
2012-01-17 08:49 EST, Vít Ondruch
no flags Details | Diff

  None (edit)
Description Jan Lieskovsky 2011-11-01 11:21:30 EDT
Julian Wälde and Alexander Klink reported a flaw in the hash function used in the implementation of the Ruby arrays implemented using the hash table.

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.

As various web application frameworks for Ruby automatically pre-fill certain arrays with data from the HTTP request (such as GET or POST parameters) for Ruby web application, a remote attacker could use this flaw to make Ruby interpreter use excessive amount of CPU time by sending a POST request with large amount of parameters which hash to the same value.

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

Note: This issue did not affect Ruby 1.9, which already randomizes hash function in a similar way perl does.
Comment 2 Jan Lieskovsky 2011-11-01 11:23:49 EDT
Acknowledgements:

Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
Comment 11 KOSAKI Motohiro 2011-11-30 12:49:38 EST
Created attachment 538673 [details]
Proposed patch by ruby security team.

Caution: This is still under reviewing and ruby security team may change it later. This code should be used for that an assigned engineer understand the issue.
Comment 12 KOSAKI Motohiro 2011-12-11 13:49:48 EST
Created attachment 545391 [details]
patch Dec 11

We ruby security team agreed a way of hash implementation with Julian Wälde who is the original reporter and changed a patch slightly. I've attached it. I suspect it is final patch.

Also, we agreed ruby core team release new patch level release at the same day with the unembargo date (i.e Dec 27), it is called ruby-1.8.7p357.
Comment 15 Vít Ondruch 2011-12-12 09:49:01 EST
(In reply to comment #12)

Hi Motohiro,

Thank you for the patch and the information abour Ruby release schedule. However, could you please elaborate what is the fix actually fixing? What is the actual cause of the slowness?

If I read the patch correctly, it seems, that you are going to significantly decrease the possibility of the DOS, because you added the random seed, therefore it is now statistically low chance that attacker would be successful, but the chances are not 0. Am I right?
Comment 16 KOSAKI Motohiro 2011-12-12 10:50:04 EST
Hi Vit,

following is my draft paper of the security announce. I hope this help you understand.

The problem are
- If there are hash collisioned string, string performance may decrease a lot.
  So an attacker may try to make billion collisioned string intentionally.
- Current hash function is too simple and attacker can easily make reverse hash
  function. IOW, to make collision is very easy.
- More unfortunately, ruby 1.8 use the same hash seed every time. Then, an
  attacker can make collisioned string on their local machine.
- An attacker can send lots string at ones by using HTTP POST parameter into
  the target host.

OK?

If an attacker needs enough a lot of time to make hash collision strings, admin can prevent the attack by simply restarting the server.  To clarify, you have good point.  We had two ways to fix 1) fix too simple ruby hash 2) fix Rails that don't have enough DoS detection.  We chose 1) because it can fix all ruby application framework by one fix.


Ruby upstream advisory draft:

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

Impact:

This is  something related  to computational complexity.   A specially
crafted  series  of strings  that  intentionally  collides their  hash
values each other was found.   With the sequence an attacker can issue
a denial  of service  attack by, for  instance, giving the  strings as
POST parameters of HTTP requests for your Rails application.

This is  a DoS  threat.  We  have not yet  been successful  to execute
arbitrary codes by exploiting this vulnerability.

<"続きを読む" tag here>

Detailed description:

The situation is similar to the one  found for Perl in 2003.  We use a
deterministic hash  function to  hash a string,  where "deterministic"
means no  other bits  of information than  the input string  itself is
involved to generate a hash  code.  So you can precalculate a string's
hash   code  beforehand  (given   ruby's  open-sourced   nature).   By
collecting a series of strings  that have the identical hash value, an
attacker  can let  ruby process  collide  bins of  hash tables.   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 hash this case).

Affected versions:

- - Ruby 1.8.7-p352 and all prior versions.

All  Ruby 1.9  series are  not affected.   They are  relatively modern
implementations, already prepared to this kind of attack.

Solution:

Our  solution  is  to  scramble  the  string  hash  function  by  some
PRNG-generated random bits.  By doing  so a string's hashed code 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, which is
believed to be quite difficult.

Please upgrade to the latest version of ruby via <修正版へのリンク>.

Notes:

* Bear in  mind that our  hash algorithm is  still _cryptographically_
 _insecure_.  To put it simple, we fixed the hash table but we didn't
 fix  `String#hash` weakness.   An attacker  coudld 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.

* In fact,  we have traditionally been providing  two alternative hash
 algorithms, apart  from the default  one.  They are  only accessible
 via recompiling a  ruby binary with magical C  compiler flags.  Most
 of you don't  even know it.  I have never seen  their used in actual
 situations.  If you  know about them and you do use  one of them, do
 so at  your own risk please.   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.
Comment 17 Vít Ondruch 2011-12-12 11:58:54 EST
Hi Motohiro,

Thank you for the announcement draft. It is very well written and it confirms my suspicion. However I am still interested in one point:

(In reply to comment #16)
>  - If there are hash collisioned string, string performance may decrease a lot.
> So an attacker
>     may try to make billion collisioned string intentionally.

Do you have some example code or reference what is the reason for this performance decrease? I can imagine there are other ways how to feed Ruby with such data, e.g. files, web input forms, etc.
Comment 18 KOSAKI Motohiro 2011-12-12 12:46:34 EST
I don't have. Original reporter plan to publish it at Dec 27th. But he telled us it use very long http post data and string hash collision.
Comment 19 Vincent Danen 2011-12-12 14:31:09 EST
Created attachment 545892 [details]
patch provided by oCERT (official upstream patch)

The official upstream patch, as provided by oCERT, which will be in ruby 1.8.7-p357.
Comment 20 Jan Lieskovsky 2011-12-15 05:30:22 EST
The CVE identifier of CVE-2011-4815 has been assigned to this issue in Ruby, CRuby and JRuby languages.
Comment 21 Huzaifa S. Sidhpurwala 2011-12-16 01:48:57 EST
CVE split for Ruby(C) and JRuby:

CVE-2011-4815  Ruby (CRuby)
CVE-2011-4838  JRuby
Comment 23 Vít Ondruch 2011-12-21 11:29:43 EST
Created attachment 549056 [details]
RHEL-5.8 patch

I have backported the patch for Ruby 1.8.5 for RHEL-5. Motohiro, could you please review the patch? I had to replace rb_genrand_int32 with genrand_int32 and remove the static. Not sure if I should not rather backport the rb_genrand_int32 patch [1].

However, I don't know how to test it :/ Rails 3 are not compatible with Ruby 1.8.5 and older Rails 2.3 fails probably sooner than the POST content is parsed. Any thoughts?

[1] https://github.com/ruby/ruby/commit/e926ef5233cc9f1035d3d51068abe9df8b5429da
Comment 30 Vít Ondruch 2011-12-23 09:24:14 EST
Created attachment 549355 [details]
RHEL-4.9 patch

I have backported the patch for RHEL-4. Its bit trickier, however it seems it works.
Comment 32 Tomas Hoger 2011-12-29 05:20:13 EST
This issue was presented on 28C3:
http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html

Details were posted to full-disclosure:
http://seclists.org/fulldisclosure/2011/Dec/477

oCERT advisory:
http://www.ocert.org/advisories/ocert-2011-003.html

n.runs advisory (copy of the full-disclosure post):
http://www.nruns.com/_downloads/advisory28122011.pdf

28C3 slides and recording:
http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf
http://www.youtube.com/28c3#p/u/22/R2Cq3CLI6H8

Another good write-up of the issue:
http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/


Upstream has released an advisory for this issue:
http://www.ruby-lang.org/en/news/2011/12/28/denial-of-service-attack-was-found-for-rubys-hash-algorithm/

The issue was fixed in Ruby 1.8.7-p357:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/391606

Upstream commit:
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=34151

Ruby upstream fix add hash function randomization to Ruby 1.8.  Hash seed is initialized on ruby interpreter start up and hence differs in between executions.
Comment 33 Huzaifa S. Sidhpurwala 2011-12-29 05:36:52 EST
Created ruby tracking bugs for this issue

Affects: fedora-all [bug 770818]
Comment 34 Tomas Hoger 2011-12-29 05:38:04 EST
Additional mitigation in Ruby Rack that limits total length of keys (parameter names) parsed from the HTTP request:
https://gist.github.com/52bbc6b9cc19ce330829
Comment 35 Tomas Hoger 2012-01-02 03:03:37 EST
(In reply to comment #34)
> Additional mitigation in Ruby Rack that limits total length of keys (parameter
> names) parsed from the HTTP request:
> https://gist.github.com/52bbc6b9cc19ce330829

Tracked also via separate bug #771149.
Comment 40 Fedora Update System 2012-01-11 01:06:47 EST
ruby-1.8.7.357-1.fc16 has been pushed to the Fedora 16 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 41 Fedora Update System 2012-01-11 01:14:47 EST
ruby-1.8.7.357-1.fc15 has been pushed to the Fedora 15 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 42 Vít Ondruch 2012-01-17 08:49:14 EST
Created attachment 555782 [details]
RHEL-4.9 patch

The original patch was too complex and needed far more backporting. This was demonstrated by issues with fixing CVE-2011-3009. So I took simpler approach.
Comment 43 errata-xmlrpc 2012-01-30 13:33:39 EST
This issue has been addressed in following products:

  Red Hat Enterprise Linux 4
  Red Hat Enterprise Linux 5

Via RHSA-2012:0070 https://rhn.redhat.com/errata/RHSA-2012-0070.html
Comment 44 errata-xmlrpc 2012-01-30 13:33:52 EST
This issue has been addressed in following products:

  Red Hat Enterprise Linux 6

Via RHSA-2012:0069 https://rhn.redhat.com/errata/RHSA-2012-0069.html

Note You need to log in before you can comment on or make changes to this bug.