Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:89496 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 35676 invoked from network); 30 Nov 2015 13:58:13 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 30 Nov 2015 13:58:13 -0000 Authentication-Results: pb1.pair.com smtp.mail=php-mailing-list@lool.fr; spf=permerror; sender-id=unknown Authentication-Results: pb1.pair.com header.from=php-mailing-list@lool.fr; sender-id=unknown Received-SPF: error (pb1.pair.com: domain lool.fr from 212.27.42.3 cause and error) X-PHP-List-Original-Sender: php-mailing-list@lool.fr X-Host-Fingerprint: 212.27.42.3 smtp3-g21.free.fr Received: from [212.27.42.3] ([212.27.42.3:54743] helo=smtp3-g21.free.fr) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 78/8D-04444-4F55C565 for ; Mon, 30 Nov 2015 08:58:13 -0500 Received: from daffy (unknown [82.242.106.155]) by smtp3-g21.free.fr (Postfix) with ESMTP id 7CB41A625E; Mon, 30 Nov 2015 14:57:33 +0100 (CET) To: "'Nikita Popov'" Cc: "'PHP internals'" References: <010e01d12978$231e7cf0$695b76d0$@lool.fr> <014301d129cc$4f97f140$eec7d3c0$@lool.fr> In-Reply-To: Date: Mon, 30 Nov 2015 14:58:08 +0100 Message-ID: <005901d12b77$246b4f10$6d41ed30$@lool.fr> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_005A_01D12B7F.862FB710" X-Priority: 1 (Highest) X-MSMail-Priority: High X-Mailer: Microsoft Outlook 14.0 Thread-Index: AQEkNhkZaWBBMPbsdhih7rI8XPIJCAH/uWNtAc4SvCACsyvLPgLomdlGn8Mw2tA= Content-Language: fr Importance: High Subject: RE: HashDos protection From: php-mailing-list@lool.fr ("Pascal KISSIAN") ------=_NextPart_000_005A_01D12B7F.862FB710 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable >De : Nikita Popov [mailto:nikita.ppv@gmail.com]=20 >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. =20 Very interesting reading, thanks=E2=80=A6 =20 =20 =20 >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 (hash + salt + N * table_size) % table_size, so elements that = collided previously still collide. =20 You=E2=80=99re absolutely right! Just adding something results in a = translation 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. =20 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 = taking care of not degrading performance=E2=80=A6 =20 pk ------=_NextPart_000_005A_01D12B7F.862FB710--