Bug 770929 (hashdos, oCERT-2011-003)

Summary:	Hash table collisions CPU usage DoS (oCERT-2011-003)
Product:	[Other] Security Response	Reporter:	Tomas Hoger <thoger>
Component:	vulnerability	Assignee:	Red Hat Product Security <security-response-team>
Status:	CLOSED ERRATA	QA Contact:
Severity:	medium	Docs Contact:
Priority:	medium
Version:	unspecified	CC:	mjc, vdanen
Target Milestone:	---	Keywords:	Security
Target Release:	---
Hardware:	All
OS:	Linux
Whiteboard:
Fixed In Version:		Doc Type:	Bug Fix
Doc Text:		Story Points:	---
Clone Of:		Environment:
Last Closed:	2021-10-19 21:50:35 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:	750521, 750533, 750547, 750555, 750564, 750575, 770820, 771149, 771283, 771428, 772720, 781606, 781677, 781683, 782163, 786617, 787067, 787103, 787104, 787109, 787888, 787890, 787915, 788183, 788606, 796015, 800531, 1032311
Bug Blocks:

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 1 Tomas Hoger 2011-12-30 10:16:00 UTC

http://www.kb.cert.org/vuls/id/903934
http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx

Comment 2 Tomas Hoger 2011-12-30 13:36:47 UTC

http://arstechnica.com/business/news/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack.ars

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.