Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96037
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain thefsb.org designates 173.203.187.107 as permitted sender)
To: Thomas Hruska <thruska@cubiclesoft.com>,
 PHP Internals <internals@lists.php.net>
References: <CAKws9z2EWkNNhM7tOMh-_pQ3iLjVj7hbXTB1Hh3a19utPzj-9A@mail.gmail.com>
 <e741fec3-b301-647c-b24c-dec2fa92554c@gmail.com>
 <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com>
Message-ID: <663c176b-dc0c-5d79-e690-8c02229b3417@thefsb.org>
Date: Tue, 20 Sep 2016 10:22:10 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:45.0)
 Gecko/20100101 Thunderbird/45.2.0
MIME-Version: 1.0
In-Reply-To: <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] HashDoS
From: fsb@thefsb.org (Tom Worster)

On 9/16/16 1:59 AM, Thomas Hruska wrote:

> If anyone wants a VERY rough estimate of relative performance
> degradation as a result of switching to SipHash, here's a somewhat naive
> C++ implementation of a similar data structure to that found in PHP:
>
> https://github.com/cubiclesoft/cross-platform-cpp
>
> (See the "Hash performance benchmark" results at the above link.)
>
> In short, there's a significant degradation just switching from djb2 to
> SipHash depending on key type.  A similar effect would probably be seen
> in PHP.

The difference is big enough that people won't want this as a precaution 
affecting all of PHP's hashes.

But it's small enough that people might opt for it as a defensive 
measure in case of serious attacks in the wild. So having an 
implementation but not compiling it by default would be interesting.


> Randomizing the starting hash value for djb2 during the core startup
> sequence *could* also be effective for mitigating HashDoS.  Extensive
> testing would have to be done to determine how collision performance
> plays out with randomized starting hash values.  I can't find any
> arguments anywhere against using randomized starting hash values for
> djb2.  Also of note, the 33 multiplier seems more critical than anything
> else for mixing bits together.

This is consistent with what Nicholas Clark wrote[1] that I mentioned 
already in my reply to Scott.

However, he also says

 > I've got a sneaking suspicion that this story still has legs, and 
that someone will pop up with some new surprise or twist. Hence I'm 
keeping an eye open to spot any more developments in this decade old 
saga, in case there is action Perl 5 needs to take.

In which case it is nice for Perl to have SipHash implemented but not 
compiled by default.

Tom


[1] 
http://news.perlfoundation.org/2012/12/improving-perl-5-grant-report-11.html