[Python-Dev] Counting collisions for the win
pydev at sievertsen.de
Fri Jan 20 16:55:32 CET 2012
I still see at least two ways to create a DOS attack even with the
I assumed that it's possible to send ~500KB of payload to the
1. It's fully deterministic which slots the dict will lookup.
Since we don't count slot-collisions, but only hash-value-collisions
this can be exploited easily by creating strings with the hash-values
along the lookup-way of an arbitrary (short) string.
So first we pick an arbitrary string. Then calculate which slots it will
visit on the way to the first empty slot. Then we create strings with
hash-values for these slots.
This attack first injects the strings to fill all the slots that the
one short string will want to visit. Then it adds THE SAME string
again and again. Since the entry is already there, nothing will be added
and no additional collisions happen, no exception raised.
$ ls -l super.txt
-rw-r--r-- 1 fx5 fx5 520000 20. Jan 10:19 super.txt
$ tail -n3 super.txt
$ wc -l super.txt
$ time python -c 'dict((unicode(l[:-1]), 0) for l in open("super.txt"))'
2. The second attack actually attacks that 1000 allowed string
comparisons are still a lot of work.
First I added 999 strings that collide with a one-byte string "a". In
some applications a zero-byte string might work even better. Then I
can add a many thousand of the "a"'s, just like the first attack.
$ ls -l 1000.txt
-rw-r--r-- 1 fx5 fx5 500000 20. Jan 16:15 1000.txt
$ head -n 3 1000.txt
$ wc -l 1000.txt
$ tail -n 3 1000.txt
$ time python -c 'dict((unicode(l[:-1]), 0) for l in open("1000.txt"))'
Of course the first attack is far more efficient. One could argue
that 16 seconds is not enough for an attack. But maybe it's possible
to send 1MB, have zero-bytes strings, and since for example django
does 5 lookups per query-string this will keep it busy for ~80 seconds on
What to do now?
I think it's not smart to reduce the number of allowed collisions
AND count all slot-collisions at the same time.
More information about the Python-Dev