Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:89484
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.160.193 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <014301d129cc$4f97f140$eec7d3c0$@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>
Date: Sun, 29 Nov 2015 12:44:36 +0100
Message-ID: <CAF+90c-tJ=scL3p=tdBYJD9N35qFdGOHhB8BRc9KF9t+hRO57g@mail.gmail.com>
To: Pascal KISSIAN <php-mailing-list@lool.fr>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a114090e4f140070525ac72cd
Subject: Re: HashDos protection
From: nikita.ppv@gmail.com (Nikita Popov)

--001a114090e4f140070525ac72cd
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Sat, Nov 28, 2015 at 12:02 PM, Pascal KISSIAN <php-mailing-list@lool.fr>
wrote:

> Sorry Nikita,
>
>
>
> I didn=E2=80=99t fully read your 1st message because it was speaking on c=
hanging
> hash algo=E2=80=A6, and I=E2=80=99ve been a bit lazy on that=E2=80=A6
>
>
>
> However, I only have thought about a minor change introducing a salt.
>
> In the zend_inline_hash_func , hash is initialized with Z_UL(5381) =E2=80=
=A6 what
> about just adding a salt value to this number, this would not make any
> performance issue.
>

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-collisi=
ons
.


> For hashing integers, why just not adding a salt value also=E2=80=A6  and=
 no
> performance issue=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 number
to it, the same relation still holds: (hash + salt) % table_size =3D=3D (ha=
sh +
salt + N * table_size) % table_size, so elements that collided previously
still collide.


> For storing  the salt, if you choose to have one different random value
> for each hash table, it would not be a problem for arrays living in
> opcache SHM=E2=80=A6
>

Randomizing the string hashing function would however prevent caching the
hash in the zend_string structure.

Nikita

--001a114090e4f140070525ac72cd--