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

[Mark Shannon]

Michael Foord 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.
> 

The attack relies on being able to predict the hash value for a given 
string. Randomising the string hash function is quite straightforward.
There is no need to change the dictionary code.

A possible (*untested*) patch is attached. I'll leave it for those more 
familiar with unicodeobject.c to do properly.

Cheers,
Mark
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hash.patch
Type: text/x-diff
Size: 1367 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-dev/attachments/20111229/df516875/attachment.patch>