Bug 786617 - (CVE-2012-0876) CVE-2012-0876 expat: hash table collisions CPU usage DoS
CVE-2012-0876 expat: hash table collisions CPU usage DoS
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=20120303,repor...
: Security
: 787080 (view as bug list)
Depends On: 1200326 811830 811831 811832 811833 811834 811835 811836 811837 982563 982566 1200324 1238184
Blocks: hashdos/oCERT-2011-003 801654 782164 1286624
  Show dependency treegraph
 
Reported: 2012-02-01 17:33 EST by Vincent Danen
Modified: 2016-11-08 10:57 EST (History)
65 users (show)

See Also:
Fixed In Version: expat 2.1.0
Doc Type: Bug Fix
Doc Text:
A denial of service flaw was found in the implementation of hash arrays in Expat. An attacker could use this flaw to make an application using Expat consume an excessive amount of CPU time by providing a specially crafted XML file that triggers multiple hash function collisions. To mitigate this issue, randomization has been added to the hash function to reduce the chance of an attacker successfully causing intentional collisions.
Story Points: ---
Clone Of:
Environment:
Last Closed: 2015-01-16 23:42:21 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)
potential patch to correct the flaw against upstream CVS version (21.62 KB, patch)
2012-02-01 17:38 EST, Vincent Danen
no flags Details | Diff
proposed upstream patch (25.03 KB, patch)
2012-02-21 17:21 EST, Vincent Danen
no flags Details | Diff
trimmed version of patch (20.00 KB, patch)
2012-02-22 06:20 EST, Joe Orton
no flags Details | Diff
XML file generator (687 bytes, text/plain)
2012-02-22 17:16 EST, Joe Orton
no flags Details


External Trackers
Tracker ID Priority Status Summary Last Updated
Mozilla Foundation 741713 None None None Never

  None (edit)
Description Vincent Danen 2012-02-01 17:33:08 EST
Similar to the denial of service flaw present in various programming languages' hash function usage, a flaw was found in expat:

A specially-crafted set of keys could trigger hash function collisions, which
degrade dictionary 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 meet in the middle attack.

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
Comment 1 Vincent Danen 2012-02-01 17:36:22 EST
This is sort of public due to discussion on the embedded expat in python:

http://bugs.python.org/issue13703#msg151870
Comment 3 Vincent Danen 2012-02-01 17:38:23 EST
Created attachment 558928 [details]
potential patch to correct the flaw against upstream CVS version

Patch provided by David Malcolm to possibly correct the flaw.
Comment 4 Vincent Danen 2012-02-21 17:21:53 EST
Created attachment 564791 [details]
proposed upstream patch

Upstream has provided this patch to solve the issue, and would be part of expat 2.1.0.  Unfortunately, it has an extra bit that we probably don't need ((it allows extracting of attribute position info), and is also against CVS HEAD so would need some massaging.
Comment 5 Kurt Seifried 2012-02-21 18:55:52 EST
Packages that require expat:

apr-util-1.3.9-3.el6_0.1
avahi-0.6.25-11.el6
cmake-2.6.4-5.el6
compat-expat1-1.95.8-8.el6
dbus-1.2.24-5.el6_1
dbus-c++-0.5.0-0.10.20090203git13281b3.1.el6
dbus-glib-0.86-5.el6
dbus-glib-devel-0.86-5.el6
elinks-0.12-0.20.pre5.el6
exempi-2.1.0-5.el6
exiv2-libs-0.18.2-2.1.el6
expat-2.0.1-9.1.el6
expat-devel-2.0.1-9.1.el6
fontconfig-2.8.0-3.el6
gdb-7.2-50.el6
ggz-base-libs-0.99.5-5.1.el6
git-1.7.1-2.el6_0.1
graphviz-2.26.0-7.el6
graphviz-perl-2.26.0-7.el6
graphviz-tcl-2.26.0-7.el6
gvfs-obexftp-1.4.3-13.el6
hal-0.5.14-11.el6
httpd-2.2.15-13.el6
httpd-tools-2.2.15-13.el6
libguestfs-1.7.17-26.el6
libmusicbrainz-2.1.5-11.1.el6
mesa-dri-drivers-7.11-1.el6
mod_dav_svn-1.6.11-2.el6_1.4
mod_perl-2.0.4-10.el6
neon-0.29.3-1.2.el6
perl-XML-Parser-2.36-7.el6
polkit-0.96-2.el6_0.1
python-2.6.6-29.el6
squid-3.1.10-1.el6_1.1
subversion-1.6.11-2.el6_1.4
subversion-javahl-1.6.11-2.el6_1.4
Comment 6 Kurt Seifried 2012-02-21 18:59:26 EST
*** Bug 787080 has been marked as a duplicate of this bug. ***
Comment 7 Joe Orton 2012-02-22 06:20:32 EST
Created attachment 564916 [details]
trimmed version of patch

Thanks Vincent, here's a trimmed down version of that patch which removes all the irrelevant changes.  It still passes the upstream test suite.
Comment 15 Tomas Hoger 2012-03-06 10:36:56 EST
Also:

http://sourceforge.net/projects/expat/files/expat/2.1.0/
Comment 22 Kurt Seifried 2012-03-08 22:59:07 EST
Adding this information for completeness:

#3496608: CVE-2012-0876 - Hash DOS attack.
http://blog.gmane.org/gmane.text.xml.expat.bugs/month=20120301
http://sourceforge.net/tracker/?func=detail&atid=110127&aid=3496608&group_id=10127
Comment 24 Kurt Seifried 2012-03-20 15:33:18 EDT
The upstream fix may also create a regression:

http://sourceforge.net/tracker/?func=detail&aid=3500861&group_id=10127&atid=110127

expat-2.1.0-beta2 will fail a namespace-aware parse of a document relying on the "xml" being bound by default, like the following test document:

<?xml version="1.0"?>
<root xml:whitespace="preserve"/>

xmlwf -n on that document returns "2:0: unbound prefix", while xmlwf from expat 2.0.1 succeeds.

This seems to be caused by the call to setContext(parser, implicitContext) adding that default prefix happening too early (before hash_secret_salt is initialized).
Comment 26 Joe Orton 2012-03-30 09:07:00 EDT
Dave, it has version 2.1.0, so python would require >= 2.1.0.

(If upstream used symbol versioning the runtime deps would work automagically but I don't think it's a great idea to patch in symversions)
Comment 35 Fedora Update System 2012-04-30 20:51:47 EDT
expat-2.1.0-1.fc16 has been pushed to the Fedora 16 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 44 errata-xmlrpc 2012-06-13 10:00:54 EDT
This issue has been addressed in following products:

  Red Hat Enterprise Linux 6
  Red Hat Enterprise Linux 5

Via RHSA-2012:0731 https://rhn.redhat.com/errata/RHSA-2012-0731.html
Comment 45 Jan Lieskovsky 2013-07-09 06:09:23 EDT
Created compat-expat1 tracking bugs for this issue:

Affects: fedora-all [bug 982563]
Comment 52 errata-xmlrpc 2016-01-21 10:54:58 EST
This issue has been addressed in the following products:

  JBoss Web Server 2.1.0

Via RHSA-2016:0062 https://rhn.redhat.com/errata/RHSA-2016-0062.html

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