Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96085
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.218.47 as permitted sender)
To: Nikita Popov <nikita.ppv@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>
Cc: PHP Internals <internals@lists.php.net>
Message-ID: <edeb9734-a3d4-bd96-f57c-fa1687473e1b@gmail.com>
Date: Wed, 21 Sep 2016 16:07:13 -0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:45.0)
 Gecko/20100101 Thunderbird/45.2.0
MIME-Version: 1.0
In-Reply-To: <CAF+90c-uFg9A2f1SVYTNgjQuFX5PkenrtXd8kf37cYoG0EfgEw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] HashDoS
From: smalyshev@gmail.com (Stanislav Malyshev)

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.

-- 
Stas Malyshev
smalyshev@gmail.com