Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:96061 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 47566 invoked from network); 21 Sep 2016 14:23:17 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 21 Sep 2016 14:23:17 -0000 Authentication-Results: pb1.pair.com header.from=nikita.ppv@gmail.com; sender-id=pass Authentication-Results: pb1.pair.com smtp.mail=nikita.ppv@gmail.com; spf=pass; sender-id=pass Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.161.178 as permitted sender) X-PHP-List-Original-Sender: nikita.ppv@gmail.com X-Host-Fingerprint: 209.85.161.178 mail-yw0-f178.google.com Received: from [209.85.161.178] ([209.85.161.178:35774] helo=mail-yw0-f178.google.com) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 12/E6-04117-4D792E75 for ; Wed, 21 Sep 2016 10:23:17 -0400 Received: by mail-yw0-f178.google.com with SMTP id u82so54892464ywc.2 for ; Wed, 21 Sep 2016 07:23:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=P1mlo3DzL4mBIiL0fXuZFphdDlCZ8OOSUnmdWDLPD0Q=; b=nP8Lmbm9vtOyANAXU4C56+mZEOY71ngIIPvritcT9vwQSRY9JJ6URq/FFwj/LlYTvG mvDR3aqnOpp98e0DDio8+EmGx7T8ucuSdlaHZtGwGjHswCttlMPathDPTZayTX7dX46w zyERjMBoaNpPS/c/YTS0v2q70q5/YvyrcuGk2iw9jZbDHHfNZFN2gzhMGezQpqO+2Xyk 13tT4WBaJV7rM96kvs83X4kKWgBrfVPFB/uI7nchwiAIxUBcPS+NT5EJEpM96Lsv24Hs fpPsiA8Uye/7fvehaenH1JzgWNNGc43psS/1Q+PEvM6/LuMH2qQnqKnTJegmkS7a2fsX EEDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=P1mlo3DzL4mBIiL0fXuZFphdDlCZ8OOSUnmdWDLPD0Q=; b=UJxkboRDWcED1hCJASLjLhwVBrG5uwsdASjdNbKOizEaQj1WaxaA60B5+9wU1NhZ6K yDPhISdYd+cqhgYK5TUXRgkNKa+J6N7oVOpIcPmRxR2esYso6dItc0bK3XQMLyd/fhbP ZQEmKVKNVD6lGgG7pr9bkHJQhivyPwOeLiQ76oNkEv5qy/X8J7t0jk1n3++l6v31EYRd 8T1j9ek0AgMWXGJ87DY/4zJxXQRSSYp1hYi9HnGfa8soMzADTXLpfJiWqwe+ggnEwukn AuREHNAGWmTBhlLx9DP8AMbLWsnelhmm1MkvKjnbqNKibd8gWCi7Q0gM/y0JM9l0AlW4 4y1Q== X-Gm-Message-State: AE9vXwP+obkFOdaJfXjpjtfYOuOZWb7ntw48CrReeJ40UmuSNNTgYEiMJxm4S2c6lRTPHvJgtg+XEihs7hrVvw== X-Received: by 10.13.234.8 with SMTP id t8mr36778154ywe.170.1474467791722; Wed, 21 Sep 2016 07:23:11 -0700 (PDT) MIME-Version: 1.0 Received: by 10.13.215.150 with HTTP; Wed, 21 Sep 2016 07:23:11 -0700 (PDT) In-Reply-To: References: <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com> <9522ebc9-8d8b-045e-b701-02f1166063e6@gmail.com> <40868951-8BDA-4860-884C-B8252C1839E3@gmail.com> Date: Wed, 21 Sep 2016 16:23:11 +0200 Message-ID: To: Tom Worster Cc: Rowan Collins , PHP Internals Content-Type: multipart/alternative; boundary=94eb2c0872daf55e44053d054801 Subject: Re: [PHP-DEV] HashDoS From: nikita.ppv@gmail.com (Nikita Popov) --94eb2c0872daf55e44053d054801 Content-Type: text/plain; charset=UTF-8 On Wed, Sep 21, 2016 at 4:05 PM, Tom Worster wrote: > On 9/21/16 8:37 AM, Rowan Collins wrote: > >> On 21 September 2016 13:02:20 BST, Glenn Eggleton >> wrote: >> >>> What if we had some sort of configuration limit on collision length? >>> >> >> Previous discussions have come to the conclusion that the difference >> between normal collision frequency and sufficient for a DoS is so large >> that the only meaningful settings would be on or off. e.g. the proposed >> limit is 1000, and randomly inserting millions of rows produces about 12. >> >> The problem with long running applications is not that they need to raise >> the limit, it's that they need to handle the error gracefully if they are >> in fact under attack. Because hash tables are so ubiquitous in the engine, >> there's no guarantee that that's possible, so an attacker would have the >> ability to crash the process with the limit turned on, or hang the CPU with >> the limit turned off. >> > > Right. It seems like count-and-limit pushes the problem onto the user who > then has to discriminate normal from malicious causes for rising counters > and find appropriate actions for each. > > Even a sophisticated user who understands hash collision counters may not > welcome this since it adds complexity that's hard to test and involves > questionable heuristics. > > Tom > Quoting a relevant part of the previous discussion: > 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. 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. Nikita --94eb2c0872daf55e44053d054801--