classification
Title: CVE-2012-0876 (hash table collisions CPU usage DoS) for embedded copy of expat
Type: Stage:
Components: XML Versions: Python 3.3, Python 3.2, Python 3.1, Python 2.7, Python 2.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: gregory.p.smith Nosy List: Arfrever, Jim.Jewett, amaury.forgeotdarc, barry, benjamin.peterson, dmalcolm, georg.brandl, gregory.p.smith, pitrou, python-dev
Priority: release blocker Keywords: patch

Created on 2012-03-09 00:56 by dmalcolm, last changed 2012-03-18 19:40 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
expat-hash-randomization.patch dmalcolm, 2012-03-09 00:56 Patch against devel branch to add fix for CVE-2012-0876 to embedded copy of expat and to use it in pyexpat review
expat-hash-randomization-002.patch gregory.p.smith, 2012-03-14 00:27 review
Messages (27)
msg155198 - (view) Author: Dave Malcolm (dmalcolm) (Python committer) Date: 2012-03-09 00:56
Expat 2.1.0 Beta was recently announced:
  http://mail.libexpat.org/pipermail/expat-discuss/2012-March/002768.html
which contains (among other things) a fix for a hash-collision denial-of-service attack (CVE-2012-0876)

I'm attaching a patch which minimally backports the hash-collision fix part of expat 2.1.0 to the embedded copy of expat in the CPython source tree, and which adds a call to XML_SetHashSalt() to pyexpat when creating parsers.  It reuses part of the hash secret from Py_HashSecret.
msg155217 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2012-03-09 09:36
I hope this can be integrated during the PyCon sprints?
msg155258 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2012-03-09 19:16
Since this has been approved upstream and the Python change is minimal, I think this can just be applied.
msg155262 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-03-09 19:52
Note sure I understand: XML_SetHashSalt() takes a parser argument, but the hash secret is global?
msg155263 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2012-03-09 20:11
No, the salt is stored on the parser. See the line:

+#define hash_secret_salt (parser->m_hash_secret_salt)

Yes, expat code is confusing.
msg155474 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-12 20:44
reviewing now.
msg155516 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-12 23:22
Oddly, test_sax fails once this patch is applied (using 3.1). debugging now.

test_sax
test test_sax failed -- Traceback (most recent call last):
  File "/home/greg/sandbox/python/cpython/3.1/Lib/xml/sax/expatreader.py", line 207, in feed
    self._parser.Parse(data, isFinal)
xml.parsers.expat.ExpatError: unbound prefix: line 1, column 59

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/home/greg/sandbox/python/cpython/3.1/Lib/test/test_sax.py", line 310, in test_5027_1
    parser.parse(test_xml)
  File "/home/greg/sandbox/python/cpython/3.1/Lib/xml/sax/expatreader.py", line 107, in parse
    xmlreader.IncrementalParser.parse(self, source)
  File "/home/greg/sandbox/python/cpython/3.1/Lib/xml/sax/xmlreader.py", line 123, in parse
    self.feed(buffer)
  File "/home/greg/sandbox/python/cpython/3.1/Lib/xml/sax/expatreader.py", line 211, in feed
    self._err_handler.fatalError(exc)
  File "/home/greg/sandbox/python/cpython/3.1/Lib/xml/sax/handler.py", line 38, in fatalError
    raise exception
xml.sax._exceptions.SAXParseException: <unknown>:1:59: unbound prefix
msg155687 - (view) Author: Arfrever Frehtes Taifersar Arahesis (Arfrever) * Date: 2012-03-13 22:51
Maybe it's related to: https://sourceforge.net/tracker/?func=detail&aid=3500861&group_id=10127&atid=110127

(But I think that --with-system-expat should be recommended.)
msg155690 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-13 23:21
sweet, thanks for the reference.  that really looks like the problem.
msg155694 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 00:27
uploaded an updated patch (against 3.1) with the changes from r1.168 to r1.170 xmlparse.c from the expat project.  it fixes the test_sax issue.

there is one other thing that needs fixing (next patch update).

The test for the hash seed being == 0 that falls back to using the expat provided trivial time() based seed undesirable.  We want a hash seed of 0 to be "disabled" matching the old behavior.  this might require adding a flag indicating if the hash seed has been initialized or not.

I'm also going to look at the possibility of using the Python interpreter's prefix and suffix values in some way rather than just prefix to avoid a potential of exposing the seed.
msg155695 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 00:30
A test case for this is also needed.

one that sets the hash seed via the environment variable to a different value for two subprocesses that parse and re-emit an xml document to confirm that all of the xml attributes are present but emitted in a different order indicating that attribute hash randomization was in effect is needed.
msg155720 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 05:27
The existing pyexpat API doesn't give me a way to test if hash randomization is actually working so I'm going ahead without a specific test case for this.

Attributes are either reported to xmlparser.SameElementHandler in a dictionary (unordered) or are reported in a list in the order they appeared on the element depending on the xmlparser.ordered_attributes bool.
msg155722 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 06:06
and given that you cannot expose if this is enabled or not by the order in which things come out of the library... no need to make this change its behavior based on the overall python hash randomization setting.

nobody's tests will break.  there is no way to expose the hash seed.

the latest patch I uploaded is good.  Misc/NEWS entry needed.  I'll push it tomorrow.
msg155785 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 20:13
Replacing the generate_hash_secret_salt function with one containing assert(0) shows that it still gets called so there are apparently still ways that initialize parsers that do not call XML_SetHashSalt using the Python hash prefix.

./python Lib/test/test_xml_etree_c.pypython: /XXX/cpython/3.1/Modules/expat/xmlparse.c:687: generate_hash_secret_salt: Assertion `0' failed.
msg155791 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 20:55
false alarm, thats just what happens when PYTHONHASHSEED=0 (I won't be committing the assert, I was just testing behavior).

For what its worth, the xmlparse.c generate_hash_seed() function is pretty poor as far as picking a random number goes as it is time based and it is often easy for an attacker to figure out the time on a process they're injecting data into and thus construct a targeted attack.  It is still better than nothing but it could be better.  I'd leave improving that up to the upstream expat project.

When PYTHONHASHSEED is enabled, pyexpat will never use that function. It does mean we use a constant seed for the life of the process when it is enabled, and revert to the expat behavior of using the expat parser creation time based seed otherwise.
msg155808 - (view) Author: Roundup Robot (python-dev) Date: 2012-03-14 22:10
New changeset 7b5bc1719477 by Gregory P. Smith in branch '3.1':
Fixes issue #14234: CVE-2012-0876: Randomize hashes of xml attributes
http://hg.python.org/cpython/rev/7b5bc1719477

New changeset d6c197edd99b by Gregory P. Smith in branch '3.2':
Fixes Issue #14234: CVE-2012-0876: Randomize hashes of xml attributes
http://hg.python.org/cpython/rev/d6c197edd99b

New changeset a8b164ab98bf by Gregory P. Smith in branch 'default':
Fixes Issue #14234: CVE-2012-0876: Randomize hashes of xml attributes
http://hg.python.org/cpython/rev/a8b164ab98bf
msg155811 - (view) Author: Roundup Robot (python-dev) Date: 2012-03-14 22:28
New changeset b54f5849013c by Gregory P. Smith in branch '2.7':
Fixes Issue #14234: CVE-2012-0876: Randomize hashes of xml attributes
http://hg.python.org/cpython/rev/b54f5849013c
msg155812 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-14 22:31
the fix is in the 3.1, 3.2, 3.3 and 2.7 trees.

It still need applying to the 2.6 branch (it applies cleanly other than Misc/NEWS); I'll let Barry do that one.

New rc2 release candidates should be made.  Otherwise I think we're ready for the releases.

I'm keeping this open until 2.6 is fixed.
msg155827 - (view) Author: Roundup Robot (python-dev) Date: 2012-03-15 00:19
New changeset 9c8d066013ea by Barry Warsaw in branch '2.6':
- Issue #14234: CVE-2012-0876: Randomize hashes of xml attributes in the hash
http://hg.python.org/cpython/rev/9c8d066013ea
msg155829 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-15 00:32
One issue has been identified when compiling with --system-expat.  if the system expat library does not have the hash salt support, compilation breaks.

fixing now.
msg155832 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-15 01:03
configure --with-system-expat was introduced in 2.7 and 3.2 so 2.6 and 3.1 are good to go for release candidates.

patch tests are running now.
msg155835 - (view) Author: Roundup Robot (python-dev) Date: 2012-03-15 01:15
New changeset b2d4a6a9463e by Gregory P. Smith in branch '3.2':
Fixes Issue 14234: fix for the previous commit, keep compilation when
http://hg.python.org/cpython/rev/b2d4a6a9463e

New changeset db27b7353400 by Gregory P. Smith in branch 'default':
Fixes Issue 14234: fix for the previous commit, keep compilation when
http://hg.python.org/cpython/rev/db27b7353400

New changeset cb72aa8a8008 by Gregory P. Smith in branch '2.7':
Fixes Issue 14234: fix for the previous commit, keep compilation when
http://hg.python.org/cpython/rev/cb72aa8a8008
msg155840 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-15 01:28
okay.  it is time to cut the rc2 release candidates with these changes.
msg155921 - (view) Author: Roundup Robot (python-dev) Date: 2012-03-15 18:01
New changeset 04ff6e206b98 by Gregory P. Smith in branch '2.7':
Fixes Issue #14234: CVE-2012-0876: Randomize hashes of xml attributes
http://hg.python.org/cpython/rev/04ff6e206b98

New changeset ada6bfbeceb8 by Gregory P. Smith in branch '2.7':
Fixes Issue 14234: fix for the previous commit, keep compilation when
http://hg.python.org/cpython/rev/ada6bfbeceb8
msg155956 - (view) Author: Jim Jewett (Jim.Jewett) Date: 2012-03-15 20:50
Looking at http://sourceforge.net/projects/expat/files/expat/2.1.0/, so long as XML_ATTR_INFO isn't defined at compile time, the changes are all considered bugfixes, and the XML_SetHashSalt is the only other changed API.

Is a potential Denial of Service really worse than a crash, such as these fixed bugs:

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

http://sourceforge.net/tracker/?func=detail&aid=1990430&group_id=10127&atid=110127
msg156086 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2012-03-16 21:21
I'm opening another issue to track updating the embedded copy of expat within Python.

FWIW, Python 2.7 & 3.2 and later support a --with-system-expat option which is what I'd *hope* that any OS distro is building their Python with rather than using the older out of date embedded copy of expat (which appears to be derived from expat 2.0.0).
msg156267 - (view) Author: Roundup Robot (python-dev) Date: 2012-03-18 19:40
New changeset cf7337a49a07 by Georg Brandl in branch '3.2':
Transplant from main repo d6c197edd99b: Fixes Issue #14234: CVE-2012-0876: Randomize hashes of xml attributes
http://hg.python.org/cpython/rev/cf7337a49a07

New changeset d54508a86a5d by Gregory P. Smith in branch '3.2':
Fixes Issue 14234: fix for the previous commit, keep compilation when
http://hg.python.org/cpython/rev/d54508a86a5d
History
Date User Action Args
2012-03-18 19:40:10python-devsetmessages: + msg156267
2012-03-16 21:21:54gregory.p.smithsetmessages: + msg156086
2012-03-15 20:50:27Jim.Jewettsetnosy: + Jim.Jewett
messages: + msg155956
2012-03-15 18:01:17python-devsetmessages: + msg155921
2012-03-15 01:28:27gregory.p.smithsetstatus: open -> closed
assignee: barry -> gregory.p.smith
resolution: fixed
messages: + msg155840
2012-03-15 01:15:39python-devsetmessages: + msg155835
2012-03-15 01:03:03gregory.p.smithsetmessages: + msg155832
2012-03-15 00:32:43gregory.p.smithsetmessages: + msg155829
2012-03-15 00:19:18python-devsetmessages: + msg155827
2012-03-14 22:31:32gregory.p.smithsetassignee: gregory.p.smith -> barry
messages: + msg155812
versions: - Python 3.4
2012-03-14 22:28:28python-devsetmessages: + msg155811
2012-03-14 22:10:08python-devsetnosy: + python-dev
messages: + msg155808
2012-03-14 20:55:35gregory.p.smithsetmessages: + msg155791
2012-03-14 20:13:13gregory.p.smithsetmessages: + msg155785
2012-03-14 06:06:35gregory.p.smithsetmessages: + msg155722
2012-03-14 05:27:45gregory.p.smithsetmessages: + msg155720
2012-03-14 00:30:30gregory.p.smithsetassignee: gregory.p.smith
2012-03-14 00:30:06gregory.p.smithsetmessages: + msg155695
2012-03-14 00:27:05gregory.p.smithsetfiles: + expat-hash-randomization-002.patch

messages: + msg155694
2012-03-13 23:21:41gregory.p.smithsetmessages: + msg155690
2012-03-13 22:51:29Arfreversetnosy: + Arfrever
messages: + msg155687
2012-03-12 23:22:28gregory.p.smithsetmessages: + msg155516
2012-03-12 20:44:53gregory.p.smithsetnosy: + gregory.p.smith
messages: + msg155474
2012-03-09 20:11:34amaury.forgeotdarcsetnosy: + amaury.forgeotdarc
messages: + msg155263
2012-03-09 19:52:41pitrousetnosy: + pitrou
messages: + msg155262
2012-03-09 19:16:46benjamin.petersonsetmessages: + msg155258
2012-03-09 09:36:07georg.brandlsetmessages: + msg155217
2012-03-09 09:35:22georg.brandlsetpriority: normal -> release blocker
nosy: + georg.brandl, benjamin.peterson
2012-03-09 01:03:27dmalcolmsetnosy: + barry
2012-03-09 00:56:30dmalcolmcreate