Bug 771149 - (CVE-2011-5036) CVE-2011-5036 rubygem-rack: hash table collisions DoS (oCERT-2011-003)
CVE-2011-5036 rubygem-rack: hash table collisions 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: 771151 771152 771150 771531 771537 773333 995686 1165366
Blocks: hashdos/oCERT-2011-003 782452 1000138
  Show dependency treegraph
 
Reported: 2012-01-02 00:55 EST by Huzaifa S. Sidhpurwala
Modified: 2015-07-31 02:47 EDT (History)
5 users (show)

See Also:
Fixed In Version: rubygem-rack 1.1.3, rubygem-rack 1.2.5, rubygem-rack 1.3.6, rubygem-rack 1.4.0
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2015-01-17 00:32:07 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)

  None (edit)
Description Huzaifa S. Sidhpurwala 2012-01-02 00:55:51 EST
Julian Wälde and Alexander Klink reported a flaw in the hash function used in the implementation of the Ruby-rack arrays.  Ruby-rack arrays are implemented using the hash table that maps keys to values:

http://rack.rubyforge.org/doc/classes/Rack/Request.html

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.

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

Patch: https://gist.github.com/52bbc6b9cc19ce330829
Comment 1 Huzaifa S. Sidhpurwala 2012-01-02 01:01:03 EST
Created rubygem-rack tracking bugs for this issue

Affects: fedora-all [bug 771150]
Comment 2 Huzaifa S. Sidhpurwala 2012-01-02 01:07:17 EST
Created rubygem-rack tracking bugs for this issue

Affects: epel-5 [bug 771151]
Affects: epel-6 [bug 771152]
Comment 6 Kurt Seifried 2012-01-14 01:14:07 EST
This appears to have been fixed in rubygems-rack 1.4.0:

Tue Dec 13 10:18:48 2011 -0800  Evan Phoenix <evan@fallingsnow.net>
  * Limit the size of parameter keys
    Signed-off-by: James Tucker <jftucker@gmail.com>

With this commit that limits parameters sent via GET or POST to 64k in total.

https://github.com/rack/rack/commit/5b9d09a81a9fdc9475f0ab0095cb2a33bf2a8f91

It can be downloaded from 

https://github.com/rack/rack/downloads
Comment 7 Vít Ondruch 2012-01-17 03:06:59 EST
(In reply to comment #6)
This is already fixed in all Fedoras, either by update of Rack or backporting patch.

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