Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:96091 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 24787 invoked from network); 22 Sep 2016 07:46:13 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 22 Sep 2016 07:46:13 -0000 Authentication-Results: pb1.pair.com smtp.mail=rowan.collins@gmail.com; spf=pass; sender-id=pass Authentication-Results: pb1.pair.com header.from=rowan.collins@gmail.com; sender-id=pass Received-SPF: pass (pb1.pair.com: domain gmail.com designates 74.125.82.42 as permitted sender) X-PHP-List-Original-Sender: rowan.collins@gmail.com X-Host-Fingerprint: 74.125.82.42 mail-wm0-f42.google.com Received: from [74.125.82.42] ([74.125.82.42:35005] helo=mail-wm0-f42.google.com) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id EF/A2-01233-44C83E75 for ; Thu, 22 Sep 2016 03:46:13 -0400 Received: by mail-wm0-f42.google.com with SMTP id l132so311126421wmf.0 for ; Thu, 22 Sep 2016 00:46:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=user-agent:in-reply-to:references:mime-version :content-transfer-encoding:subject:from:date:to:cc:message-id; bh=XhEtz2Nn54xKk4ECTTdfmVlE4aX/su65O8ZgM6c1EeA=; b=CKo8C0lP9mCzymFqEMtfZsXMBoZs0qEe7PnC40eX92qPYL6bKPInnPED/yerETrUPM Eb30wT113r6+50u2T61e/rj05g1F7oCiF1ldzKm2dTHpLaJCIiozbCxg4WvW/6+lum+q YWhd1LTqaPkt70x3eMTK7YrDkIzgFZAmWdHzgwJH4mtd70GCZ84DKn0ezwkQqPRFgKc2 +C/dCETrYCaa03aP/nbvB58kzxb11den8BvVvMKn4kUTNftAIif9MDQfPAHlc9wCwXXf dFRpJbf/gT/sb75QpJG5SYUdcxEpVCdawWQ/nRBcegjF1HxCrj4aa38iD/cY9+Ge48qL JQdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:user-agent:in-reply-to:references:mime-version :content-transfer-encoding:subject:from:date:to:cc:message-id; bh=XhEtz2Nn54xKk4ECTTdfmVlE4aX/su65O8ZgM6c1EeA=; b=Egzix05g9TwhVUD8HacHnFiEya+vJLJ+u2Zqxk8i6qLGE15C8sk+TodM6FtGayVXBC zlU1H7E4DaoGeeYqrQCbuEIUCxtm96+WfDViztiSrJFulK3pbx4ephCvWxUs2K26/dS4 FXMVWY4M3waZ13HZnwsCNJqmAsvnSqOM7C7qmVk5sP/DAb85DvEf6clyri3g1+f5AguT PGm+VVDGtRqToETKKRBJ5y57/RurzS+2pexyYiCQQ8DbpHPzH+K2M4gveDg3Zep3Uv4q BYt6jPZ/z/EzE+N7j6dz7dNw4ewlMr3yAOY+S+L9vwUb2RcRtXHG3WnRwgfECbqYJiEq aziA== X-Gm-Message-State: AE9vXwOc+pXfI8GfDX79wZmbxplLHxAc+btVj5UJw9IPd4k1AQ+lwzq6cxAoQYsFa/M4YQ== X-Received: by 10.28.39.134 with SMTP id n128mr7020684wmn.60.1474530370150; Thu, 22 Sep 2016 00:46:10 -0700 (PDT) Received: from android-c07b90b023759a5a.default ([95.148.161.240]) by smtp.gmail.com with ESMTPSA id r2sm29690132wmf.14.2016.09.22.00.46.08 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 22 Sep 2016 00:46:09 -0700 (PDT) User-Agent: K-9 Mail for Android In-Reply-To: <88433a67-3121-bacb-5db4-89c337914c5b@gmail.com> References: <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com> <9522ebc9-8d8b-045e-b701-02f1166063e6@gmail.com> <40868951-8BDA-4860-884C-B8252C1839E3@gmail.com> <88433a67-3121-bacb-5db4-89c337914c5b@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 Date: Thu, 22 Sep 2016 08:46:06 +0100 To: Stanislav Malyshev ,Nikita Popov CC: PHP Internals Message-ID: <5AF206DB-730A-4B03-8D5D-B7C46029AD1A@gmail.com> Subject: Re: [PHP-DEV] HashDoS From: rowan.collins@gmail.com (Rowan Collins) On 22 September 2016 00:23:16 BST, Stanislav Malyshev wrote: >In which case some limit like 1000 (just random number but can be >tested) would probably be OK. The question now is would it be enough to >block DoS? I.e. if we construct data to cause 999 collisions each time >to stay just under the limit, can we still cause trouble or not? It's >still almost 1000 times slower it's supposed to be... I think I'm right in saying that the power of the attack comes in the fact that the total time doesn't scale linearly but exponentially. Inserting a third element into a chain of two is faster than inserting a tenth element into a chain of nine. So a hash that hits the limit is more than 1000 times slower than a natural one, but 1000 chains of 999 is orders of magnitude faster than one chain of 999000. That doesn't exactly answer the question of whether 1000 is the right value, of course. Regards, -- Rowan Collins [IMSoP]