Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:89498
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 74.125.82.42 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <005901d12b77$246b4f10$6d41ed30$@lool.fr>
References: <CAF+90c_pVFVbzqThuPg1V3VDTV-7Ci4O6T6hNtY5XPgVb2Mt-Q@mail.gmail.com>
	<010e01d12978$231e7cf0$695b76d0$@lool.fr>
	<CAF+90c_wsXghTbFKGVuh7bKEuu_K0vBUE96sjc=etDbbMrMowQ@mail.gmail.com>
	<014301d129cc$4f97f140$eec7d3c0$@lool.fr>
	<CAF+90c-tJ=scL3p=tdBYJD9N35qFdGOHhB8BRc9KF9t+hRO57g@mail.gmail.com>
	<005901d12b77$246b4f10$6d41ed30$@lool.fr>
Date: Mon, 30 Nov 2015 14:06:27 +0000
Message-ID: <CABHuAWw=bCRbRuKokJ0rJd0EMbC5p1Rm8UH3QWJJ9-XBOxHNhQ@mail.gmail.com>
To: Pascal KISSIAN <php-mailing-list@lool.fr>
Cc: Nikita Popov <nikita.ppv@gmail.com>, PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a1148e18c1547e90525c28c56
Subject: Re: [PHP-DEV] RE: HashDos protection
From: t.carnage@gmail.com (Chris Riley)

--001a1148e18c1547e90525c28c56
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On 30 November 2015 at 13:58, Pascal KISSIAN <php-mailing-list@lool.fr>
wrote:

> >De : Nikita Popov [mailto:nikita.ppv@gmail.com]
> >Envoy=C3=A9 : dimanche 29 novembre 2015 12:45
> >=C3=80 : Pascal KISSIAN
> >Cc : PHP internals
> >Objet : Re: HashDos protection
>
> >Collisions in DJBX33A are (integer overflow notwithstanding) completely
> independent of the starting value, so randomizing it wouldn't help. If
> you're interested in how DJB collisions are constructed, see
> http://www.phpinternalsbook.com/hashtables/hash_algorithm.html#hash-colli=
sions
> .
>
>
>
>               Very interesting reading, thanks=E2=80=A6
>
>
>
>
>
>
>
> >Similarly, this would not have any effect either. We reduce hashes using
> an equivalent of hash % table_size, which is the same as (hash + N *
> table_size) % table_size for any N. If you simply add an additional numbe=
r
> to it, the same relation still holds: (hash + salt) % table_size =3D=3D (=
hash +
> salt + N * table_size) % table_size, so elements that collided previously
> still collide.
>
>
>
> You=E2=80=99re absolutely right!  Just adding something results in a tran=
slation
> of the hash table cell=E2=80=A6
>
> Perhaps another operation could do the job?  Multiply still keeps the
> collision for the modulo equal to 0=E2=80=A6 perhaps add + multiply =E2=
=80=A6.
>
>
>
> However, my main feeling is that "An ounce of prevention is worth a pound
> of cure"=E2=80=A6
> =E2=80=A6 and my preferences will go to your second option =E2=80=A6  tak=
ing care of not
> degrading performance=E2=80=A6
>
>
>
> pk
>
>
As for what other languages do, Python, Ruby and Perl all seem to have
switched to using sipHash - maybe we should consider this too

--001a1148e18c1547e90525c28c56--