Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96087
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.213.182 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <edeb9734-a3d4-bd96-f57c-fa1687473e1b@gmail.com>
References: <CAKws9z2EWkNNhM7tOMh-_pQ3iLjVj7hbXTB1Hh3a19utPzj-9A@mail.gmail.com>
 <e741fec3-b301-647c-b24c-dec2fa92554c@gmail.com> <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com>
 <CAKws9z38_QhH8rnshJu=SP1Aav7jhMnVR2H992+Lse7iMeQ3oA@mail.gmail.com>
 <ffc669b5-8764-3879-0c5a-d047d75c9b45@gmail.com> <CAGa2bXYad=5CNKUR4GTR-uB8L1Gb-2CJk5Fiperz5D_CTL+rxw@mail.gmail.com>
 <9522ebc9-8d8b-045e-b701-02f1166063e6@gmail.com> <CAGa2bXYNZwKrT=Ei8r1DghGjqOGiMUVPEGY31wYK9Hpt+C9XMQ@mail.gmail.com>
 <CANUQDCjcnFdPyG133z6g0DdRLZjUG=+BRhcv4Es9Z+WeoU-Prg@mail.gmail.com>
 <CAFGtT7Zd3+iRuaJtwpML3hO6Kbdu7YtnNOE14zvA78E=QiNprg@mail.gmail.com>
 <40868951-8BDA-4860-884C-B8252C1839E3@gmail.com> <d2080444-9a17-b3db-89fa-c383155a5756@thefsb.org>
 <CAF+90c-uFg9A2f1SVYTNgjQuFX5PkenrtXd8kf37cYoG0EfgEw@mail.gmail.com> <edeb9734-a3d4-bd96-f57c-fa1687473e1b@gmail.com>
Date: Thu, 22 Sep 2016 01:30:42 +0200
Message-ID: <CAF+90c9HTpxtY8zeKoOfjdQXTkrVQSw8fb9Ws0-Qs_xmJtttZw@mail.gmail.com>
To: Stanislav Malyshev <smalyshev@gmail.com>
Cc: PHP Internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=f403045c05f80bad37053d0cefda
Subject: Re: [PHP-DEV] HashDoS
From: nikita.ppv@gmail.com (Nikita Popov)

--f403045c05f80bad37053d0cefda
Content-Type: text/plain; charset=UTF-8

On Thu, Sep 22, 2016 at 1:07 AM, Stanislav Malyshev <smalyshev@gmail.com>
wrote:

> Hi!
>
> >> Lets [try] to quantify the probability of reaching the collision limit C
> > with a hashtable of size N and assuming a random hash distribution. The
> > upper bound for this should be (N choose C) * (1/N)^(C-1), with
> (1/N)^(C-1)
> > being the probability that C elements hash to one value and (N over C)
> the
> > number of C element subsets of an N element set. For large N and N >> C
> we
> > approximate (N choose C) to (e*N/C)^C / sqrt(2pi*C). As such our upper
> > bound becomes N * (e/C)^C / sqrt(2pi*C). Choosing N = 2^31 (largest
> > possible hashtable) we get for C = 20 probability 8.9E-10 and for C = 100
> > probability 2.3E-149. The patch uses C = 1000.
>
> I assume you're talking here about per-hashtable limit?
> Here I notice two things:
>
> 1. Hash keys are not really random. Which can both improve and make it
> worse, but we have a lot of keys named "key" and not a lot of keys named
> "\x07\xF5\xDD".
>
> 2. This does not account for the fact that if we have two keys used by
> app colliding, we'll probably see this collision a lot. Of course, if
> we're counting per-hashtable, that would make is somewhat less, but still.
>
> To validate this theory, I applied the following patch:
>
> https://gist.github.com/smalyshev/2c3c085998ba81d6c163a27386aaacd8
>
> And run composer update on one of my projects. I got these lines:
>
> Destroyed hash with coll = 48454
> Destroyed hash with coll = 41871
> Destroyed hash with coll = 41828
> Destroyed hash with coll = 40535
> Destroyed hash with coll = 32774
> Destroyed hash with coll = 22782
> Destroyed hash with coll = 21381
> Destroyed hash with coll = 15232
> Destroyed hash with coll = 14745
> Destroyed hash with coll = 12216
> Destroyed hash with coll = 11742
> Destroyed hash with coll = 11625
> Destroyed hash with coll = 8916
> Destroyed hash with coll = 6820
> Destroyed hash with coll = 5911
> Destroyed hash with coll = 5429
> Destroyed hash with coll = 3390
> Destroyed hash with coll = 1188
>
> I.e. there were 18 hashes with more than 1000 collisions on the course
> of the run. Is there something wrong with my count or am I counting
> wrong things (I didn't see the patch for limiting counts so maybe I'm
> still counting wrong things).
>
> > In other words, it is extremely unlikely that you hit the collision limit
> > by accident, with non-malicious data. So no, the user does not have to
> > discriminate normal from malicious causes. If the limit triggers, it's
> > malicious.
>
> I'm not so sure of this now - unless, again, I misunderstand what we're
> counting.


As linked in my first reply, there was a previous discussion on the topic:
http://markmail.org/message/ttbgcvdu4f7uymfb
The collision-counting approach that Yasuo references is linked at the
start of the first mail: https://github.com/php/php-src/pull/1565

Collisions are counted during insertion operations. While we perform a
hashtable insertion, we first need to iterate over the existing buckets for
a certain hash to see if the insert is actually an update. The
implementation simply keeps track of how many buckets we inspect while
doing that. If the number is above a certain threshold, an error is
generated.

As such, the number of collisions per hashtable is not important. Only the
number of collisions for a certain hash-value is relevant. Getting C=1000
collisions for a single hash-value is extremely unlikely until you
explicitly design your keys to trigger this situation.

Nikita

--f403045c05f80bad37053d0cefda--