Author dmalcolm
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Jim.Jewett, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.snow, fx5, georg.brandl, grahamd, gregory.p.smith, gvanrossum, gz, haypo, jcea, lemburg, mark.dickinson, merwok, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, zbysz
Date 2012-01-21.03:16:22
SpamBayes Score 0.0
Marked as misclassified No
Message-id <1327115744.4992.180.camel@surprise>
In-reply-to <1327100080.4992.149.camel@surprise>
Content
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
Files
File name Uploaded
amortized-probe-counting-dmalcolm-2012-01-20-002.patch dmalcolm, 2012-01-21.03:16:17
History
Date User Action Args
2012-01-21 03:16:26dmalcolmsetrecipients: + dmalcolm, lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, haypo, christian.heimes, benjamin.peterson, merwok, grahamd, Arfrever, v+python, alex, zbysz, skrah, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5
2012-01-21 03:16:24dmalcolmlinkissue13703 messages
2012-01-21 03:16:22dmalcolmcreate