User: Password:
Subscribe / Log in / New account

Denial of service via hash collisions

Denial of service via hash collisions

Posted Jan 16, 2012 10:31 UTC (Mon) by ekj (guest, #1524)
Parent article: Denial of service via hash collisions

The hash-function used at the core of Python is vulnerable to this. It's trivial to provide "perverse" input where all the items hashes identically, and doing this changes the expected runtime of looking up a element in a dictionary from O(1) to O(n).

Potentially, this means you can create a DOS-attack on any python-program that puts user-provided things in a dictionary in such a way that the user influences the key, if the dict is large enough and/or the performance-constraints are tight enough that O(n) instead of O(1) matters.

The overhead is fairly high though, in practical testing even a 15-deep collision (i.e. a element that requires 15 attempts to locate) takes double time, compared to an element that's found at the first attempt. If it's linear (it should be, but I ain't actually tested that), then worst-case a 15-element dict would have only half the predicted performance - which is unlikely to cause a DOS.

But a 150 element-array could have 1/10th the expected performance, and "perverse" 1500-element dictionary could require 100 times as long to process as expected - and that starts looking like a potential DOS.

(Log in to post comments)

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds