Bug 786617 (CVE-2012-0876) - CVE-2012-0876 expat: hash table collisions CPU usage DoS
Summary: CVE-2012-0876 expat: hash table collisions CPU usage DoS
Keywords:
Status: CLOSED ERRATA
Alias: CVE-2012-0876
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=20120303,repor...
: 787080 (view as bug list)
Depends On: 811830 811831 811832 811833 811834 811835 811836 811837 982563 982566 1200324 1200326 1238184
Blocks: hashdos, oCERT-2011-003 782164 801654 1286624
TreeView+ depends on / blocked
 
Reported: 2012-02-01 22:33 UTC by Vincent Danen
Modified: 2019-06-08 19:02 UTC (History)
65 users (show)

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.
Clone Of:
Environment:
Last Closed: 2015-01-17 04:42:21 UTC


Attachments (Terms of Use)
potential patch to correct the flaw against upstream CVS version (21.62 KB, patch)
2012-02-01 22:38 UTC, Vincent Danen
no flags Details | Diff
proposed upstream patch (25.03 KB, patch)
2012-02-21 22:21 UTC, Vincent Danen
no flags Details | Diff
trimmed version of patch (20.00 KB, patch)
2012-02-22 11:20 UTC, Joe Orton
no flags Details | Diff
XML file generator (687 bytes, text/plain)
2012-02-22 22:16 UTC, Joe Orton
no flags Details


Links
System ID Priority Status Summary Last Updated
Red Hat Product Errata RHSA-2012:0731 normal SHIPPED_LIVE Moderate: expat security update 2012-06-13 18:00:12 UTC
Mozilla Foundation 741713 None None None 2019-04-07 03:17:30 UTC
Red Hat Product Errata RHSA-2016:0062 normal SHIPPED_LIVE Moderate: Red Hat JBoss Web Server 2.1.0 security update 2018-02-15 23:12:52 UTC

Description Vincent Danen 2012-02-01 22:33:08 UTC
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 22:36:22 UTC
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 22:38:23 UTC
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 22:21:53 UTC
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 23:55:52 UTC
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 23:59:26 UTC
*** Bug 787080 has been marked as a duplicate of this bug. ***

Comment 7 Joe Orton 2012-02-22 11:20:32 UTC
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 15:36:56 UTC
Also:

http://sourceforge.net/projects/expat/files/expat/2.1.0/

Comment 22 Kurt Seifried 2012-03-09 03:59:07 UTC
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 19:33:18 UTC
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 13:07:00 UTC
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-05-01 00:51:47 UTC
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 14:00:54 UTC
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 10:09:23 UTC
Created compat-expat1 tracking bugs for this issue:

Affects: fedora-all [bug 982563]

Comment 52 errata-xmlrpc 2016-01-21 15:54:58 UTC
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.