[Python-Dev] Hash collision security issue (now public)

[Christian Heimes]

Am 29.12.2011 02:37, schrieb Jesse Noller:
> Back up link for the PDF:
> http://dl.dropbox.com/u/1374/2007_28C3_Effective_DoS_on_web_application_platforms.pdf
> 
> Ocert disclosure:
> http://www.ocert.org/advisories/ocert-2011-003.html

>From http://www.nruns.com/_downloads/advisory28122011.pdf

---
Python uses a hash function which is very similar to DJBX33X, which can
be broken using a
meet-in-the-middle attack. It operates on register size and is thus
different for 64 and 32 bit
machines. While generating multi-collisions efficiently is also possible
for the 64 bit version
of the function, the resulting colliding strings are too large to be
relevant for anything more
than an academic attack.

Plone as the most prominent Python web framework accepts 1 MB of POST
data, which it
parses in about 7 minutes of CPU time in the worst case.
This gives an attacker with about 20 kbit/s the possibility to keep one
Core Duo core
constantly busy. If the attacker is in the position to have a Gigabit
line available, he can keep
about 50.000 Core Duo cores busy.
---

If I remember correctly CPython uses the long for its hash function so
64bit Windows uses a 32bit hash.