Message152753
On Mon, Feb 6, 2012 at 12:07 PM, Marc-Andre Lemburg
<report@bugs.python.org> wrote:
>
> Marc-Andre Lemburg <mal@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... |
|
Date |
User |
Action |
Args |
2012-02-06 18:31:37 | Jim.Jewett | set | recipients:
+ Jim.Jewett, lemburg, gvanrossum, tim.peters, loewis, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, vstinner, christian.heimes, benjamin.peterson, eric.araujo, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, PaulMcMillan, fx5, skorgu |
2012-02-06 18:31:37 | Jim.Jewett | link | issue13703 messages |
2012-02-06 18:31:36 | Jim.Jewett | create | |
|