Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96020
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain paragonie.com designates 209.85.218.53 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com>
References: <CAKws9z2EWkNNhM7tOMh-_pQ3iLjVj7hbXTB1Hh3a19utPzj-9A@mail.gmail.com>
 <e741fec3-b301-647c-b24c-dec2fa92554c@gmail.com> <7d5727ba-da33-e3c5-1d1f-318c45d81616@cubiclesoft.com>
Date: Fri, 16 Sep 2016 09:30:05 -0400
Message-ID: <CAKws9z38_QhH8rnshJu=SP1Aav7jhMnVR2H992+Lse7iMeQ3oA@mail.gmail.com>
To: Thomas Hruska <thruska@cubiclesoft.com>
Cc: Stanislav Malyshev <smalyshev@gmail.com>, PHP Internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a1142ff74e55e31053c9ff504
Subject: Re: [PHP-DEV] HashDoS
From: scott@paragonie.com (Scott Arciszewski)

--001a1142ff74e55e31053c9ff504
Content-Type: text/plain; charset=UTF-8

Significant degradation?

SipHash 1-3 is almost as fast as HashDoS-vulnerable hash functions:
https://github.com/funny-falcon/funny_hash

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

On Fri, Sep 16, 2016 at 1:59 AM, Thomas Hruska <thruska@cubiclesoft.com>
wrote:

> On 9/15/2016 5:20 PM, Stanislav Malyshev wrote:
>
>> Hi!
>>
>> On 9/15/16 11:48 AM, Scott Arciszewski wrote:
>>
>>> Would the Internals team be open to discussing mitigating HashDoS in a
>>> future version of PHP? i.e. everywhere, even for json_decode() and
>>> friends,
>>> by fixing the problem rather than capping the maximum number of input
>>> parameters and hoping it's good enough.
>>>
>>> I'd propose SipHash (and/or a derivative):
>>> https://www.131002.net/siphash/
>>>
>>
>> I am worries about performance. Base hash structure has to be *very*
>> fast. I have doubts that cryptographic function can perform at these
>> levels. Did you test what is performance of this function compared to
>> existing hash function?
>>
>
> 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.
>
> 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.
>
> --
> Thomas Hruska
> CubicleSoft President
>
> I've got great, time saving software that you will find useful.
>
> http://cubiclesoft.com/
>

--001a1142ff74e55e31053c9ff504--