Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96039
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain paragonie.com designates 209.85.218.52 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAGa2bXYad=5CNKUR4GTR-uB8L1Gb-2CJk5Fiperz5D_CTL+rxw@mail.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>
Date: Tue, 20 Sep 2016 10:33:44 -0400
Message-ID: <CAKws9z3kP+MRXbAdWW2DCdFNj61v_t=paW4ThjrUYy25hQFRAg@mail.gmail.com>
To: Yasuo Ohgaki <yohgaki@ohgaki.net>
Cc: Stanislav Malyshev <smalyshev@gmail.com>, Thomas Hruska <thruska@cubiclesoft.com>, 
	PHP Internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a113decbce1f1e7053cf15030
Subject: Re: [PHP-DEV] HashDoS
From: scott@paragonie.com (Scott Arciszewski)

--001a113decbce1f1e7053cf15030
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Sat, Sep 17, 2016 at 6:35 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

> Hi all,
>
> On Sat, Sep 17, 2016 at 5:13 PM, Stanislav Malyshev <smalyshev@gmail.com>
> wrote:
> >> Significant degradation?
> >>
> >> SipHash 1-3 is almost as fast as HashDoS-vulnerable hash
> >> functions: https://github.com/funny-falcon/funny_hash
> >
> > I see on this link comparison to Murmur3 - but that's not the function
> > we are using. Is there a comparison to PHP one?
>
> Unfortunately, SipHash was a lot slower. BJB hash is simple and super
> fast, even google's CityHash was a lot slower when I tested. (Sorry I
> don't keep the number)
>
> I think we are better to limit max collisions.
> I'm +1 for Nikita's proposal does this.
>
> Regards,
>
> --
> Yasuo Ohgaki
> yohgaki@ohgaki.net
>



As long as the pro=E2=80=8Bblem gets solved, I'm not in favor of any partic=
ular
solution.

I do find this amusing, though: the author of djb3 was Daniel J Bernstein,
who also helped develop SipHash. I guess non-cryptographic hash functions
are a small world.

Nikita:

- Do you think your proposed strategy can solve this problem entirely
without dropping djb3?
- Would randomization still help as a defense-in-depth?

To elaborate on the second question: even a 4-byte prefix for the hash
function inputs that's randomly generated at $appropriateIntervalHere might
make intentional collisions harder to trigger. (Then again, maybe not! The
underlying structure of djb3 isn't exactly cryptographic.)

To be clear, "Yes this is entirely solved without switching away from djb"
+ "No, randomization just hurts opcache and doesn't buy us any security"
are an acceptable set of answers to these questions. I just wanted to ask.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com/>

--001a113decbce1f1e7053cf15030--