Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:96088 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 3813 invoked from network); 21 Sep 2016 23:30:47 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 21 Sep 2016 23:30:47 -0000 Authentication-Results: pb1.pair.com header.from=yohgaki@ohgaki.net; sender-id=pass Authentication-Results: pb1.pair.com smtp.mail=yohgaki@ohgaki.net; spf=pass; sender-id=pass Received-SPF: pass (pb1.pair.com: domain ohgaki.net designates 180.42.98.130 as permitted sender) X-PHP-List-Original-Sender: yohgaki@ohgaki.net X-Host-Fingerprint: 180.42.98.130 ns1.es-i.jp Received: from [180.42.98.130] ([180.42.98.130:37916] helo=es-i.jp) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 92/50-01233-42813E75 for ; Wed, 21 Sep 2016 19:30:46 -0400 Received: (qmail 4178 invoked by uid 89); 21 Sep 2016 23:24:00 -0000 Received: from unknown (HELO mail-qk0-f180.google.com) (yohgaki@ohgaki.net@209.85.220.180) by 0 with ESMTPA; 21 Sep 2016 23:24:00 -0000 Received: by mail-qk0-f180.google.com with SMTP id g67so1335439qkd.0 for ; Wed, 21 Sep 2016 16:23:59 -0700 (PDT) X-Gm-Message-State: AE9vXwOPx6YUaVx3jqzduCL+QzQahCDF63rDwcYHXlpSySy4c3wUQgnAkz5+6fUjHuEFmMgqbnbhikDUbwy7eA== X-Received: by 10.55.121.67 with SMTP id u64mr47278347qkc.114.1474500233647; Wed, 21 Sep 2016 16:23:53 -0700 (PDT) MIME-Version: 1.0 Received: by 10.140.84.168 with HTTP; Wed, 21 Sep 2016 16:23:13 -0700 (PDT) In-Reply-To: <7642ae28-a347-653a-026a-2fb0fa613f85@gmail.com> References: <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com> <9522ebc9-8d8b-045e-b701-02f1166063e6@gmail.com> <7642ae28-a347-653a-026a-2fb0fa613f85@gmail.com> Date: Thu, 22 Sep 2016 08:23:13 +0900 X-Gmail-Original-Message-ID: Message-ID: To: Stanislav Malyshev Cc: Scott Arciszewski , Thomas Hruska , PHP Internals Content-Type: text/plain; charset=UTF-8 Subject: Re: [PHP-DEV] HashDoS From: yohgaki@ohgaki.net (Yasuo Ohgaki) Hi Stas, On Thu, Sep 22, 2016 at 7:47 AM, Stanislav Malyshev wrote: >> On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev >> 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? IIRC, proposed patch was detecting collisions per key. > >> 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. I agree that we cannot be sure how many collision limit is proper for certain app. This is the same for memory limit, stack limit, backtrack limit, recursion limit. It is possible to set reasonable limit that is good enough for almost all apps. AFAIK, we don't have a bug report complains slow hash operation for normal code yet. IMO, this is the evidence that we can set collision limit safely and prevent intended hash collision attacks. Regards, -- Yasuo Ohgaki yohgaki@ohgaki.net