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.
Acknowledgements: Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
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.
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.
(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?
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.
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.
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.
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.
The CVE identifier of CVE-2011-4815 has been assigned to this issue in Ruby, CRuby and JRuby languages.
CVE split for Ruby(C) and JRuby: CVE-2011-4815 Ruby (CRuby) CVE-2011-4838 JRuby
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
Created attachment 549355 [details] RHEL-4.9 patch I have backported the patch for RHEL-4. Its bit trickier, however it seems it works.
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.
Created ruby tracking bugs for this issue Affects: fedora-all [bug 770818]
Additional mitigation in Ruby Rack that limits total length of keys (parameter names) parsed from the HTTP request: https://gist.github.com/52bbc6b9cc19ce330829
(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.
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.
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.
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.
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
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
Updated upstream advisory link: http://www.ruby-lang.org/en/news/2011/12/28/denial-of-service-attack-was-found-for-rubys-hash-algorithm-cve-2011-4815/