Bug 750555 - (CVE-2012-1150) CVE-2012-1150 python: hash table collisions CPU usage DoS (oCERT-2011-003)
CVE-2012-1150 python: hash table collisions CPU usage DoS (oCERT-2011-003)
Product: Security Response
Classification: Other
Component: vulnerability (Show other bugs)
All Linux
medium Severity medium
: ---
: ---
Assigned To: Red Hat Product Security
: Security
Depends On: 771528 771534 802209 802210 805382 805383 805384 805385
Blocks: hashdos/oCERT-2011-003 750561 790031
  Show dependency treegraph
Reported: 2011-11-01 11:03 EDT by Jan Lieskovsky
Modified: 2015-11-24 09:51 EST (History)
15 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Last Closed: 2012-07-18 06:16:47 EDT
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---

Attachments (Terms of Use)

External Trackers
Tracker ID Priority Status Summary Last Updated
Python 13703 None None None Never

  None (edit)
Description Jan Lieskovsky 2011-11-01 11:03:19 EDT
Julian Wälde and Alexander Klink reported a flaw in the hash function used in the implementation of the Python dictionaries (associative arrays).

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.

As various web application frameworks for Python automatically pre-fill certain dictionaries with data from the HTTP request (such as GET or POST parameters) for Python web application, a remote attacker could use this flaw to make Python interpreter use excessive amount of CPU time by sending a POST request with large amount of parameters which hash to the same value.

This problem is similar to the issue that was previously reported for and fixed in e.g. perl:
Comment 2 Jan Lieskovsky 2011-11-01 11:07:17 EDT

Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
Comment 10 Tomas Hoger 2011-12-30 08:38:04 EST
New and old threads on python-dev related to this issue:

Comment 13 Dave Malcolm 2012-01-03 18:56:07 EST
(this is being tracked upstream as http://bugs.python.org/issue13703 )
Comment 21 Dave Malcolm 2012-01-13 00:15:46 EST
python-dev status update: http://comments.gmane.org/gmane.comp.python.devel/128617
Comment 31 Dave Malcolm 2012-01-19 23:27:26 EST
The collision-counting approach is now favored upstream (over hash randomization):
[+1 from Guido here: http://mail.python.org/pipermail/python-dev/2012-January/115692.html ]
Comment 32 Dave Malcolm 2012-01-19 23:32:46 EST
For reference, latest version of lemburg's patch using collision-counting approach is currently this one:
(from 2012-01-06)
Comment 35 Dave Malcolm 2012-01-23 21:55:09 EST
Upstream seems to be dithering between collision-counting and hash randomization, or some combination, and the discussion seems to have grown out-of-control.

For my part, I've posted some patches upstream:

(A) "hash-collision-counting-dmalcolm-2012-01-20-001.patch"
    (see http://bugs.python.org/issue13703#msg151707 )
in which I further developed lemburg's first collision-counting patch

I then had a brainstorm and tried another approach:
(B) "amortized-probe-counting-dmalcolm-2012-01-20-002.patch"
    (see http://bugs.python.org/issue13703#msg151714 )

(C) "amortized-probe-counting-dmalcolm-2012-01-21-003.patch"
    (see http://bugs.python.org/issue13703#msg151735 )
tracking per-dict statistics, in particular: the amortized average cost per modification of each dict, and raising an exception when the average exceeds a given threshold for a given dict.  This seems to work for all of python's test suite, and very quickly detects and complains about hostile input.  It's rather experimental though, and the ratio/scale-factor is a number I chose arbitrarily, and I haven't gone through the math or gathered real numbers on real code.  There are a few issues that would need fixing (see Antoine Pitrou's comments on it).

However, there's an argument that any approach that can lead to dict (or set) raising an exception is flawed: see http://bugs.python.org/issue13703#msg151796  It strikes me that this "protection" may allow yet another new class of attack, it which the attacker slowly poisons inputs, so that when a dict is constructed at some later point, an exception is raised you weren't expecting.  If the protection wasn't there you'd get the extreme slowdown, rather an exception.  But: my patch is too good :)  it's too efficient at detecting when it's under attack: the exception is raised too quickly, and so arguably we've made the job easier for the attacker.  But maybe I'm overthinking this?  Perhaps I just need to tune things?

(D) http://bugs.python.org/issue13703#msg151847
in which I backported haypo's hash randomization patch from the main branch to the 2.7 branch.  This patch disables the hash randomization by default, and only does it for string-like types, not numeric types (for reasons noted in that comment).  When enabled with "PYTHONHASHRANDOMIZATION=1 python", this patch successfully blocks the reproducer.  (there's also another hash randomization patch beyond haypo's, which does a few things a little differently; see python issue 13704).

Note that hash randomization is known to break Django's test suite, which is why I'm wary about enabling it by default.
Comment 37 Dave Malcolm 2012-01-25 06:54:52 EST
I came up with a hybrid approach, which I believe combines the best aspects of the collision-counting and hash-randomization approaches.

I've posted it for upstream review here:


In this approach, by default, hash() and dict don't use hash randomization - preserving existing behavior.  It detects when a given dict is under attack, and transitions just that dict to use randomized hashes.

It preserves ABI - however, in order to do this, the randomization only happens for str/unicode/bytes keys.  I believe this is a reasonable compromise, given the various attack scenarios on a web server (e.g. it should cover HTTP headers, POST fields, JSON, XML-RPC).

It will probably need performance tuning and extensive testing.
Comment 38 Dave Malcolm 2012-01-27 21:19:36 EST
Upstream has reached a consensus about a security release (adding hash-randomization in disabled form with an envvar to enable it):

I've been volunteered by the release managers of those upstream branches to create the patches (based on the work I've already done; see (D) above:
http://bugs.python.org/issue13703#msg151847 ).
Comment 55 Kurt Seifried 2012-03-10 00:52:17 EST
Added CVE as per http://www.openwall.com/lists/oss-security/2012/03/10/3
Comment 56 Huzaifa S. Sidhpurwala 2012-03-12 01:41:23 EDT
Created python tracking bugs for this issue

Affects: fedora-all [bug 802209]
Comment 57 Huzaifa S. Sidhpurwala 2012-03-12 01:41:31 EDT
Created python3 tracking bugs for this issue

Affects: fedora-all [bug 802210]
Comment 69 Fedora Update System 2012-05-02 00:49:27 EDT
python-2.7.3-3.fc17, python-docs-2.7.3-1.fc17 has been pushed to the Fedora 17 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 70 Fedora Update System 2012-05-03 03:28:12 EDT
python3-3.2.3-1.fc15 has been pushed to the Fedora 15 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 71 Tomas Hoger 2012-05-03 08:43:59 EDT
This issue was fixed upstream in versions 2.6.8, 2.7.3, 3.1.5 and 3.2.3:


The final upstream solution is to use hash randomization.  However, randomization is disabled by default to avoid breaking code that incorrectly relies on specific ordering of dictionary keys.  Updated python versions provide following ways to enable randomization:

- PYTHONHASHSEED environment variable, which is expected to be set to a decimal number in the range [0,4294967295], or "random", with the following meaning:
  - "random" - new random seed is generated during interpreter start, seed
    is not predictable across python interpreter invocations
  - 0 - use the same seed as was used by older python versions, effectively
    disabling randomization
  - other values - use specific fixed seed value, which is different from
    seed that was used in older python versions; this may be useful in test
    suites or environments when multiple python instances are expected to
    produce the same hash values
- -R command line option, its use is equivalent to setting PYTHONHASHSEED environment variable to "random"

Refer to python command manual page for further details:
Comment 73 Fedora Update System 2012-05-05 21:25:59 EDT
python-2.7.3-1.fc16, python-docs-2.7.3-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 74 Fedora Update System 2012-05-07 00:16:33 EDT
python3-3.2.3-5.fc17 has been pushed to the Fedora 17 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 75 Fedora Update System 2012-05-07 18:09:44 EDT
python26-2.6.8-1.el5 has been pushed to the Fedora EPEL 5 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 76 Tomas Hoger 2012-06-08 06:05:36 EDT
As part of this fix, an implementation of os.random was moved from the os module (part of the Python standard library) the posix module (built in to the Python executable binary).  This causes no issues for most use cases, but may cause problems where updated Python standard library is used with not updated Python executable.  Such problem was reported for Python virtualenv use cases, see:


The above link also provides instructions on how to fix the problem.  These instructions are also available on the virtualenv project news page:


  Warning: Python bugfix releases 2.6.8, 2.7.3, 3.1.5 and 3.2.3 include a
  change that will cause “import random” to fail with “cannot import name
  urandom” on any virtualenv created on a Unix host with an earlier release
  of Python 2.6/2.7/3.1/3.2, if the underlying system Python is upgraded.
  This is due to the fact that a virtualenv uses the system Python’s standard
  library but contains its own copy of the Python interpreter, so an upgrade
  to the system Python results in a mismatch between the version of the Python
  interpreter and the version of the standard library. It can be fixed by
  removing $ENV/bin/python and re-running virtualenv on the same target
  directory with the upgraded Python.
Comment 77 errata-xmlrpc 2012-06-18 08:32:36 EDT
This issue has been addressed in following products:

  Red Hat Enterprise Linux 6

Via RHSA-2012:0744 https://rhn.redhat.com/errata/RHSA-2012-0744.html
Comment 78 errata-xmlrpc 2012-06-18 08:42:54 EDT
This issue has been addressed in following products:

  Red Hat Enterprise Linux 5

Via RHSA-2012:0745 https://rhn.redhat.com/errata/RHSA-2012-0745.html
Comment 79 Fedora Update System 2012-06-19 10:53:04 EDT
python3-3.2.3-2.fc16 has been pushed to the Fedora 16 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 80 Ratul Gupta 2013-12-10 05:36:05 EST
CVE-2013-7040 is filed as a followup for this bug.

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