Message 151714 - Python tracker (original) (raw)
On Fri, 2012-01-20 at 22:55 +0000, Dave Malcolm wrote:
Dave Malcolm <dmalcolm@redhat.com> added the comment:
On Fri, 2012-01-06 at 12:52 +0000, Marc-Andre Lemburg wrote:
Marc-Andre Lemburg <mal@egenix.com> added the comment:
Demo patch implementing the collision limit idea for Python 2.7.
Added file: http://bugs.python.org/file24151/hash-attack.patch
Marc: is this the latest version of your patch?
Whether or not we go with collision counting and/or adding a random salt to hashes and/or something else, I've had a go at updating your patch
Although debate on python-dev seems to have turned against the collision-counting idea, based on flaws reported by Frank Sievertsen http://mail.python.org/pipermail/python-dev/2012-January/115726.html it seemed to me to be worth at least adding some test cases to flesh out the approach. Note that the test cases deliberately avoid containing "hostile" data.
I had a brainstorm, and I don't yet know if the following makes sense, but here's a crude patch with another approach, which might get around the issues Frank raises.
Rather than count the number of equal-hash collisions within each call to lookdict, instead keep a per-dict count of the total number of iterations through the probe sequence (regardless of the hashing), amortized across all calls to lookdict, and if it looks like we're going O(n^2) rather than O(n), raise an exception. Actually, that's not quite it, but see below...
We potentially have 24 words of per-dictionary storage hiding in the ma_smalltable area within PyDictObject, which we can use when ma_mask >= PyDict_MINSIZE (when mp->ma_table != mp->ma_smalltable), without changing sizeof(PyDictObject) and thus breaking ABI. I hope there isn't any code out there that uses this space. (Anyone know of any?)
This very crude patch uses that area to add per-dict tracking of the total number of iterations spent probing for a free PyDictEntry whilst constructing the dictionary. It rules that if we've gone more than (32
- ma_used) iterations whilst constructing the dictionary (counted across all ma_lookup calls), then we're degenerating into O(n^2) behavior, and this triggers an exception. Any other usage of ma_lookup resets the count (e.g. when reading values back). I picked the scaling factor of 32 from out of the air; I hope there's a smarter threshold.
I'm assuming that an attack scenario tends to involve a dictionary that goes through a construction phase (which the attacker is aiming to change from O(N) to O(N^2)), and then a usage phase, whereas there are other patterns of dictionary usage in which insertion and lookup are intermingled for which this approach wouldn't raise an exception.
This leads to exceptions like this:
AlgorithmicComplexityError: dict construction used 4951 probes for 99 entries at key 99 with hash 42
(i.e. the act of constructing a dict with 99 entries required traversing 4951 PyDictEntry slots, suggesting someone is sending deliberately awkward data).
Seems to successfully handle both the original DoS and the second scenario in Frank's email. I don't have a reproducer for the first of Frank's scenarios, but in theory it ought to handle it. (I hope!)
Have seen two failures within python test suite from this, which I hope can be fixed by tuning the thresholds and the reset events (they seem to happen when a large dict is emptied).
May have a performance impact, but I didn't make any attempt to optimize it (beyond picking a power of two for the scaling factor).
(There may be random bits of the old patch thrown in; sorry)
Thoughts? (apart from "ugh! it's ugly!" yes I know - it's late here) Dave