[Python-Dev] Counting collisions for the win

[Guido van Rossum]

On Fri, Jan 20, 2012 at 1:34 AM, "Martin v. Löwis" <martin at v.loewis.de>wrote:

> > The last solution is very simple: count collision and raise an
> > exception if it hits a limit. The path is something like 10 lines
> > whereas the randomized hash is more close to 500 lines, add a new
> > file, change Visual Studio project file, etc. First I thaught that it
> > would break more applications than the randomized hash
>
> The main issue with that approach is that it allows a new kind of attack.
>
> An attacker now needs to find 1000 colliding keys, and submit them
> one-by-one into a database. The limit will not trigger, as those are
> just database insertions.
>
> Now, if the applications also as a need to read the entire database
> table into a dictionary, that will suddenly break, and not for the
> attacker (which would be ok), but for the regular user of the
> application or the site administrator.
>
> So it may be that this approach actually simplifies the attack, making
> the cure worse than the disease.
>

It would be a pretty lousy app that tried to load the contents of an entire
database into a dict. It seems that this would require much more knowledge
of what the app is trying to do before a successful attack can be mounted.
So I don't think this is worse than the original attack -- I think it
requires much more ingenuity of an attacker. (I'm thinking that the
original attack is trivial once the set of 65000 colliding keys is public
knowledge, which must be only a matter of time.)

-- 
--Guido van Rossum (python.org/~guido)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20120120/0dfe4463/attachment.html>