Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96084
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.218.43 as permitted sender)
To: Yasuo Ohgaki <yohgaki@ohgaki.net>
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>
Cc: Scott Arciszewski <scott@paragonie.com>,
 Thomas Hruska <thruska@cubiclesoft.com>,
 PHP Internals <internals@lists.php.net>
Message-ID: <7642ae28-a347-653a-026a-2fb0fa613f85@gmail.com>
Date: Wed, 21 Sep 2016 15:47:37 -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: <CAGa2bXYNZwKrT=Ei8r1DghGjqOGiMUVPEGY31wYK9Hpt+C9XMQ@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!

> Hi Stas,
> 
> On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
> <smalyshev@gmail.com> wrote:
>>
>>> I think we are better to limit max collisions.
>>> I'm +1 for Nikita's proposal does this.
>>
>> Max collision per what? How much would be the limit?
> 
> Collision by keys.

Not sure I understand. What would be counted - number of collision per
key? Per hashtable? Per process? Per request?

> It would be nice to have configurable limit like regex stack/backtrack limit.
> That said, wouldn't 1000 enough for almost all apps?

Certainly not. Not even nearly enough. Collisions are pretty frequent
with short strings, for example, and for a big long-running application
1000 hash collisions is nothing. I think you severely underestimate how
frequent hash collisions are, with simple function like we're using,
over millions and millions of hash accesses that we're doing routinely.

I did a quick check, and just running run-tests.php -h (without any
tests!) produces about 5K collisions. Running composer (without doing
anything) - 8K collisions. Running composer update on a simple project -
400K (!) collisions. Now these are pretty simple cases compared to what
a complex modern PHP application does. So I think you are
underestimating it by about 4-5 orders of magnitude.

> 
> Anyway, we have two choices
>  - Simply limit the number of collisions. (Fast and has no impact to code)

Fast: true, no impact: not so much. If the limit is too low for your app
(and you probably have no idea how many collisions your app has, and it
is probably highly varied too) your app breaks in some very creative
ways, including dropping dead in the middle of transactions, being
unable to handle errors, etc.

>  - Use crypt safe hash and salt. (Slow and has impact to opcache/etc)

These not the only two choices.

> Limiting something is good to have sometimes.
> Python even limits number of recursions to 1000 by default.

Recursion limits are completely different. With recursion, with any
proper algorithm, the deeper you go the probability of having next
recursion step drops dramatically (usually exponentially - that's how
you build performant algorithms). However, hash collisions are
completely independent, so having one does not change the chance you
have another (in fact, it may make it higher if the same data is
processed again).

Which means, for recursion, it is very probable there is a limit that
most of your code will never reach. Even then we are cautious of it as
there's no good number for a natural limit.

But with hash collisions, I just see no way to tell "10K collisions is
enough for anything" and at least my quick checks - unless I massively
messed up the test - shows that it's not easy to find a practical limit,
at least with current hash function.

> We have PCRE stack/backtrack limits. (We'll have mbregex stack limit soon)
> Collision limit is good one also.

Does not follow, as per above.
-- 
Stas Malyshev
smalyshev@gmail.com