[issue13703] Hash collision security issue

[Jim Jewett]

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

On Mon, Feb 6, 2012 at 12:07 PM, Marc-Andre Lemburg
<report at bugs.python.org> wrote:
>
> Marc-Andre Lemburg <mal at egenix.com> added the comment:
>
> Jim Jewett wrote:

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

> Since N is constant, I don't see how such an "attack" could be used
> to trigger the O(n^2) worst-case behavior.

Agreed; it tops out with a constant, but if it takes only 16 bytes of
input to force another run through a 1000-long collision, that may
still be too much leverage.

> BTW: If you set the limit N to e.g. 100 (which is reasonable given
> Victor's and my tests),

Agreed.  Frankly, I think 5 would be more than reasonable so long as
there is a fallback.

> the time it takes to process one of those
> sets only takes 0.3 ms on my machine. That's hardly usable as basis
> for an effective DoS attack.

So it would take around 3Mb to cause a minute's delay...

----------

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