[issue13703] Hash collision security issue
report at bugs.python.org
Wed Jan 11 19:05:30 CET 2012
Marc-Andre Lemburg <mal at egenix.com> added the comment:
Antoine Pitrou wrote:
> Antoine Pitrou <pitrou at free.fr> added the comment:
>> On my slow dev machine 1000 collisions run in around 22ms:
>> python2.7 -m timeit -n 100 "dict((x*(2**64 - 1), 1) for x in xrange(1, 1000))"
>> 100 loops, best of 3: 22.4 msec per loop
>> Using this for a DOS attack would be rather noisy, much unlike
>> sending a single POST.
> Note that sending one POST is not enough, unless the attacker is content
> with blocking *one* worker process for a couple of seconds or minutes
> (which is a rather tiny attack if you ask me :-)). Also, you can combine
> many dicts in a single JSON list, so that the 1000 limit isn't
> overreached for any of the dicts.
Right, but such an approach only scales linearly and doesn't
exhibit the quadric nature of the collision resolution.
The above with 10000 items takes 5 seconds on my machine.
The same with 100000 items is still running after 16 minutes.
> So in all cases the attacker would have to send many of these POST
> requests in order to overwhelm the target machine. That's how DOS
> attacks work AFAIK.
Depends :-) Hiding a few tens of such requests in the input stream
of a busy server is easy. Doing the same with thousands of requests
is a lot harder.
FWIW: The above dict string version just has some 263kB for the 100000
case, 114kB if gzip compressed.
>> Yes, which is why the patch should be disabled by default (using
>> an env var) in dot-releases. It's probably also a good idea to
>> make the limit configurable to adjust to ones needs.
> Agreed if it's disabled by default then it's not a problem, but then
> Python is vulnerable by default...
Yes, but at least the user has an option to switch on the added
protection. We'd need some field data to come to a decision.
Python tracker <report at bugs.python.org>
More information about the Python-bugs-list