[issue13703] Hash collision security issue

[Jim Jewett]

Jim Jewett <jimjjewett at gmail.com> added the comment:

On Mon, Feb 6, 2012 at 8:12 AM, Marc-Andre Lemburg
<report at bugs.python.org> wrote:
>
> Marc-Andre Lemburg <mal at egenix.com> added the comment:
>
> Antoine Pitrou wrote:
>>
>> The simple collision counting approach leaves a gaping hole open, as
>> demonstrated by Frank.

> Could you elaborate on this ?

> Note that I've updated the collision counting patch to cover both
> possible attack cases I mentioned in http://bugs.python.org/issue13703#msg150724.
> If there's another case I'm unaware of, please let me know.

The problematic case is, roughly,

(1)  Find out what N will trigger collision-counting countermeasures.
(2)  Insert N-1 colliding entries, to make it as slow as possible.
(3)  Keep looking up (or updating) the N-1th entry, so that the
slow-as-possible-without-countermeasures path keeps getting rerun.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13703>
_______________________________________