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

[geremy condra]

On Wed, Dec 28, 2011 at 8:49 PM, Eric Snow <ericsnowcurrently at gmail.com> wrote:
> On Wed, Dec 28, 2011 at 6:28 PM, Michael Foord
> <fuzzyman at voidspace.org.uk> wrote:
>> Hello all,
>>
>> A paper (well, presentation) has been published highlighting security problems with the hashing algorithm (exploiting collisions) in many programming languages Python included:
>>
>>         http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf
>>
>> Although it's a security issue I'm posting it here because it is now public and seems important.
>>
>> The issue they report can cause (for example) handling an http post to consume horrible amounts of cpu. For Python the figures they quoted:
>>
>>        reasonable-sized attack strings only for 32 bits Plone has max. POST size of 1 MB
>>        7 minutes of CPU usage for a 1 MB request
>>        ~20 kbits/s → keep one Core Duo core busy
>>
>> This was apparently reported to the security list, but hasn't been responded to beyond an acknowledgement on November 24th (the original report didn't make it onto the security list because it was held in a moderation queue).
>>
>> The same vulnerability was reported against various languages and web frameworks, and is already fixed in some of them.
>>
>> Their recommended fix is to randomize the hash function.
>
> Ironically, this morning I ran across a discussion from about 8 years
> ago on basically the same thing:
>
> http://mail.python.org/pipermail/python-dev/2003-May/035874.html
>
>  From what I read in the thread, it didn't seem like anyone here was
> too worried about it.  Does this new research change anything?

Not really. It's actually somewhat behind previous work in that it
doesn't exploit the timing deltas, just generates very large ones.

Geremy Condra