Bug 771149 (CVE-2011-5036)

Summary: CVE-2011-5036 rubygem-rack: hash table collisions DoS (oCERT-2011-003)
Product: [Other] Security Response Reporter: Huzaifa S. Sidhpurwala <huzaifas>
Component: vulnerabilityAssignee: Red Hat Product Security <security-response-team>
Status: CLOSED ERRATA QA Contact:
Severity: medium Docs Contact:
Priority: medium    
Version: unspecifiedCC: jrusnack, kseifried, mmorsi, vanmeeuwen+fedora, vondruch
Target Milestone: ---Keywords: Security
Target Release: ---   
Hardware: All   
OS: Linux   
Whiteboard:
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 05:32:07 UTC Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: --- Target Upstream Version:
Bug Depends On: 771150, 771151, 771152, 771531, 771537, 773333, 995686, 1165366    
Bug Blocks: 770929, 782452, 1000138    

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>
  * Limit the size of parameter keys
    Signed-off-by: James Tucker <jftucker>

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.