Bug 770929 (hashdos, oCERT-2011-003) - Hash table collisions CPU usage DoS (oCERT-2011-003)
Summary: Hash table collisions CPU usage DoS (oCERT-2011-003)
Keywords:
Status: NEW
Alias: hashdos, oCERT-2011-003
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: impact=moderate,public=20111228,repor...
Depends On: CVE-2011-4838 CVE-2012-0039 CVE-2012-0840 800531 CVE-2011-4084, CVE-2011-4858 CVE-2012-2739 CVE-2011-4885 CVE-2012-1150 CVE-2011-4815 CVE-2011-5037 CVE-2011-5036 CVE-2011-5035 CVE-2011-5056, CVE-2012-0024 CVE-2011-4461 CVE-2011-4462 782163 CVE-2012-0876 CVE-2012-0841 CVE-2012-0880 CVE-2012-0881 CVE-2012-0877 CVE-2012-0839 CVE-2012-3514 787915 788183 788606 CVE-2011-4967 CVE-2013-6371
Blocks:
TreeView+ depends on / blocked
 
Reported: 2011-12-30 10:06 UTC by Tomas Hoger
Modified: 2019-06-08 18:59 UTC (History)
2 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed:


Attachments (Terms of Use)


Links
System ID Priority Status Summary Last Updated
Gentoo 396397 None None None Never

Description Tomas Hoger 2011-12-30 10:06:46 UTC
Julian Wälde and Alexander Klink presented on 28th Chaos Communication Congress (28C3) ways to trigger high CPU use in various programming languages and frameworks used for web application programming by generating collisions in hash functions used in implementations of associative arrays in the language.  This is a tracker bug that links other language / component specific bugs.

References:
http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html
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
http://www.nruns.com/_downloads/advisory28122011.pdf
http://seclists.org/fulldisclosure/2011/Dec/477
http://www.ocert.org/advisories/ocert-2011-003.html
http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/

Comment 6 Vincent Danen 2012-01-09 19:10:34 UTC
I've added a bug for glib2 (bug #772720).  Unfortunately, it looks like glib2 may be embedded and/or have had the vulnerable function copied to other programs; see the bug for the details (some may be false hits though, especially for the Fedora packages listed).

Comment 7 Tomas Hoger 2012-01-12 13:21:56 UTC
Note for posterity - perl got randomized hashes to protect against this class of attacks back in 2003.  References:

https://rt.perl.org/rt3/Public/Bug/Display.html?id=22371
http://perl5.git.perl.org/perl.git/commitdiff/504f80c1f3625809f472c1ce21089fdae860d9fd
http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks

Comment 8 Vincent Danen 2012-01-13 20:36:38 UTC
Bug #781606 has been filed for apr, where apr_hash() may be vulnerable to the same thing.


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