Bug 771149 (CVE-2011-5036) - CVE-2011-5036 rubygem-rack: hash table collisions DoS (oCERT-2011-003)
Summary: CVE-2011-5036 rubygem-rack: hash table collisions DoS (oCERT-2011-003)
Keywords:
Status: CLOSED ERRATA
Alias: CVE-2011-5036
Product: Security Response
Classification: Other
Component: vulnerability
Version: unspecified
Hardware: All
OS: Linux
medium
medium
Target Milestone: ---
Assignee: Red Hat Product Security
QA Contact:
URL:
Whiteboard:
Depends On: 771152 771150 771151 771531 771537 773333 995686 1165366
Blocks: hashdos, oCERT-2011-003 782452 1000138
TreeView+ depends on / blocked
 
Reported: 2012-01-02 05:55 UTC by Huzaifa S. Sidhpurwala
Modified: 2019-09-29 12:49 UTC (History)
5 users (show)

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:
Clone Of:
Environment:
Last Closed: 2015-01-17 05:32:07 UTC


Attachments (Terms of Use)

Description Huzaifa S. Sidhpurwala 2012-01-02 05:55:51 UTC
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 06:01:03 UTC
Created rubygem-rack tracking bugs for this issue

Affects: fedora-all [bug 771150]

Comment 2 Huzaifa S. Sidhpurwala 2012-01-02 06:07:17 UTC
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 06:14:07 UTC
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 08:06:59 UTC
(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.