Everything

php

Home » Project » Newsgroups » php.internals » HashDoS »

HashDoS

php.internals

Scott Arciszewski

9 years ago

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/

(Look at all the other languages that already adopted SipHash.)

https://medium.freecodecamp.com/hash-table-attack-8e4371fc5261#.s5r5j42x3

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

Nikita Popov

9 years ago

On Thu, Sep 15, 2016 at 8:48 PM, Scott Arciszewski <scott@paragonie.com>
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/
>
> (Look at all the other languages that already adopted SipHash.)
>
> https://medium.freecodecamp.com/hash-table-attack-8e4371fc5261#.s5r5j42x3
>

Previous discussion on the topic:
http://markmail.org/message/ttbgcvdu4f7uymfb

Nikita

Yasuo Ohgaki

9 years ago

Hi Nikita,

On Fri, Sep 16, 2016 at 3:56 AM, Nikita Popov <nikita.ppv@gmail.com> wrote:

>
> Previous discussion on the topic:
> http://markmail.org/message/ttbgcvdu4f7uymfb

Your proposal is mandatory, IMHO.
Let's implement it ASAP.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Stas Malyshev

9 years ago

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?

>
> (Look at all the other languages that already adopted SipHash.)

Adopted as base data structure in the engine? Which ones? What were the
performance costs?

--
Stas Malyshev
smalyshev@gmail.com

Thomas Hruska

9 years ago

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/

Nikita Popov

9 years ago

On Fri, Sep 16, 2016 at 7: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.
>

Randomizing the starting hash value of DJB has come up in the previous
thread as well -- it sounds nice, but is turns out to be completely
ineffective, because DJB collisions (at least the standard class of
collisions ignoring overflow [1]) are independent of the starting hash
value.

Nikita

[1]:
http://www.phpinternalsbook.com/hashtables/hash_algorithm.html#hash-collisions

Scott Arciszewski

9 years ago

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:

Stas Malyshev

9 years ago

Hi!

> Significant degradation?
>
> SipHash 1-3 is almost as fast as HashDoS-vulnerable hash
> functions: https://github.com/funny-falcon/funny_hash

I see on this link comparison to Murmur3 - but that's not the function
we are using. Is there a comparison to PHP one?

--
Stas Malyshev
smalyshev@gmail.com

Yasuo Ohgaki

9 years ago

Hi all,

On Sat, Sep 17, 2016 at 5:13 PM, Stanislav Malyshev <smalyshev@gmail.com> wrote:

>> Significant degradation?
>>
>> SipHash 1-3 is almost as fast as HashDoS-vulnerable hash
>> functions: https://github.com/funny-falcon/funny_hash
>
> I see on this link comparison to Murmur3 - but that's not the function
> we are using. Is there a comparison to PHP one?

Unfortunately, SipHash was a lot slower. BJB hash is simple and super
fast, even google's CityHash was a lot slower when I tested. (Sorry I
don't keep the number)

I think we are better to limit max collisions.
I'm +1 for Nikita's proposal does this.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Scott Arciszewski

9 years ago

On Sat, Sep 17, 2016 at 6:35 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

> Hi all,
>
> On Sat, Sep 17, 2016 at 5:13 PM, Stanislav Malyshev <smalyshev@gmail.com>
> wrote:
> >> Significant degradation?
> >>
> >> SipHash 1-3 is almost as fast as HashDoS-vulnerable hash
> >> functions: https://github.com/funny-falcon/funny_hash
> >
> > I see on this link comparison to Murmur3 - but that's not the function
> > we are using. Is there a comparison to PHP one?
>
> Unfortunately, SipHash was a lot slower. BJB hash is simple and super
> fast, even google's CityHash was a lot slower when I tested. (Sorry I
> don't keep the number)
>
> I think we are better to limit max collisions.
> I'm +1 for Nikita's proposal does this.
>
> Regards,
>
> --
> Yasuo Ohgaki
> yohgaki@ohgaki.net
>

As long as the pro​blem gets solved, I'm not in favor of any particular
solution.

I do find this amusing, though: the author of djb3 was Daniel J Bernstein,
who also helped develop SipHash. I guess non-cryptographic hash functions
are a small world.

Nikita:

- Do you think your proposed strategy can solve this problem entirely
without dropping djb3?
- Would randomization still help as a defense-in-depth?

To elaborate on the second question: even a 4-byte prefix for the hash
function inputs that's randomly generated at $appropriateIntervalHere might
make intentional collisions harder to trigger. (Then again, maybe not! The
underlying structure of djb3 isn't exactly cryptographic.)

To be clear, "Yes this is entirely solved without switching away from djb"
+ "No, randomization just hurts opcache and doesn't buy us any security"
are an acceptable set of answers to these questions. I just wanted to ask.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com/>

Stas Malyshev

9 years ago

Hi!

> - Do you think your proposed strategy can solve this problem entirely
> without dropping djb3?
> - Would randomization still help as a defense-in-depth?

Note that to avoid problems with opcache we can only randomize on
initial boot (even then synchronizing among different processes sharing
opcache may be challenging). That means that the process would be
running for extended time (at least days, in theory as long as uptime
allows) with the same seed. Given that, I'm not sure how much
randomization would really improve.

> To elaborate on the second question: even a 4-byte prefix for the hash
> function inputs that's randomly generated at $appropriateIntervalHere
> might make intentional collisions harder to trigger. (Then again, maybe
> not! The underlying structure of djb3 isn't exactly cryptographic.)

I don't see how we can do $appropriateIntervalHere if we use opcache. We
could clean the cache of course but I'm not sure server owners would be
very happy if their cache dropped at random intervals with accompanying
load spike.

--
Stas Malyshev
smalyshev@gmail.com

Tom Worster

9 years ago

On 9/20/16 10:25 PM, Stanislav Malyshev wrote:

> Note that to avoid problems with opcache we can only randomize on
> initial boot (even then synchronizing among different processes sharing
> opcache may be challenging). That means that the process would be
> running for extended time (at least days, in theory as long as uptime
> allows) with the same seed. Given that, I'm not sure how much
> randomization would really improve.

While randomization doesn't eliminate the problem, isn't it still a
valid complication for attackers? If everybody's PHP instance is running
with a different hash key, that's harder to attack than if than if they
all have the same key, even if the key isn't frequently changed.

It reminds me of when Logjam was in the news and we realized it wasn't
smart for everyone to use the same default DH primes.

Tom

Stas Malyshev

9 years ago

Hi!

> I think we are better to limit max collisions.
> I'm +1 for Nikita's proposal does this.

Max collision per what? How much would be the limit?

--
Stas Malyshev
smalyshev@gmail.com

Yasuo Ohgaki

9 years ago

Hi Stas,

On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
<smalyshev@gmail.com> wrote:

>
>> I think we are better to limit max collisions.
>> I'm +1 for Nikita's proposal does this.
>
> Max collision per what? How much would be the limit?

Collision by keys.

It would be nice to have configurable limit like regex stack/backtrack limit.
That said, wouldn't 1000 enough for almost all apps?

Anyway, we have two choices
- Simply limit the number of collisions. (Fast and has no impact to code)
- Use crypt safe hash and salt. (Slow and has impact to opcache/etc)

Limiting something is good to have sometimes.
Python even limits number of recursions to 1000 by default.
We have PCRE stack/backtrack limits. (We'll have mbregex stack limit soon)
Collision limit is good one also.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Niklas Keller

9 years ago

2016-09-21 8:54 GMT+02:00 Yasuo Ohgaki <yohgaki@ohgaki.net>:

> Hi Stas,
>
> On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
> <smalyshev@gmail.com> wrote:
> >
> >> I think we are better to limit max collisions.
> >> I'm +1 for Nikita's proposal does this.
> >
> > Max collision per what? How much would be the limit?
>
> Collision by keys.
>
> It would be nice to have configurable limit like regex stack/backtrack
> limit.
> That said, wouldn't 1000 enough for almost all apps?
>

Having a limit isn't a good idea for all use cases, but it works for some.

> Anyway, we have two choices
>  - Simply limit the number of collisions. (Fast and has no impact to code)
>

It totally has impact to code. What happens if we have enough collisions?
Throw an exception? Might break code, any array insert operation might
suddenly fail. Simply fatal? Not suitable for long running applications
like Aerys (https://github.com/amphp/aerys) or PPM (
https://github.com/php-pm/php-pm).

I guess to support these use cases, we have to switch to a cryptographic
hash function here. But I guess it would be totally fine having such a
feature as compile flag, limiting the number of collisions usually and
provide a cryptographic hash function for long running apps to protect them.

I think such an option is fine for those running long running applications,
since they don't rely on setups like shared hosting and can usually compile
their own versions.

>  - Use crypt safe hash and salt. (Slow and has impact to opcache/etc)
>

Do we need a salt here? If not, how does it then impact opcache?

> Limiting something is good to have sometimes.
> Python even limits number of recursions to 1000 by default.
>

Recursion is / should not be affected by user input and thus is a slightly
different topic.

Regards, Niklas

Glenn Eggleton

9 years ago

Hello,

What if we had some sort of configuration limit on collision length?
Would give most of us a viable way to prevent our apps from being attacked,
and yet in the use cases where we require a higher limit we retain the
ability to up the limit or disable it completely.

Regards, Glenn

On Wed, Sep 21, 2016 at 4:06 AM, Niklas Keller <me@kelunik.com> wrote:

Yasuo Ohgaki

9 years ago

Hi Kiklas,

On Wed, Sep 21, 2016 at 5:06 PM, Niklas Keller <me@kelunik.com> wrote:

> 2016-09-21 8:54 GMT+02:00 Yasuo Ohgaki <yohgaki@ohgaki.net>:
>>
>> Hi Stas,
>>
>> On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
>> <smalyshev@gmail.com> wrote:
>> >
>> >> I think we are better to limit max collisions.
>> >> I'm +1 for Nikita's proposal does this.
>> >
>> > Max collision per what? How much would be the limit?
>>
>> Collision by keys.
>>
>> It would be nice to have configurable limit like regex stack/backtrack
>> limit.
>> That said, wouldn't 1000 enough for almost all apps?
>
>
> Having a limit isn't a good idea for all use cases, but it works for some.
>
>>
>> Anyway, we have two choices
>>  - Simply limit the number of collisions. (Fast and has no impact to code)
>
>
> It totally has impact to code. What happens if we have enough collisions?
> Throw an exception? Might break code, any array insert operation might
> suddenly fail. Simply fatal? Not suitable for long running applications like
> Aerys (https://github.com/amphp/aerys) or PPM
> (https://github.com/php-pm/php-pm).
>
> I guess to support these use cases, we have to switch to a cryptographic
> hash function here. But I guess it would be totally fine having such a
> feature as compile flag, limiting the number of collisions usually and
> provide a cryptographic hash function for long running apps to protect them.
>
> I think such an option is fine for those running long running applications,
> since they don't rely on setups like shared hosting and can usually compile
> their own versions.

It's the same as you're saying that PCRE stack/backtrack limit and/or
memory limit is not good idea.
The same argument apply to the stack/backtrack/memory limit, but I
don't think these limits are bad idea at all.

AFIAK, we didn't have a bug report that complains slow hash operation
by collisions yet except intended attack, did we?

Limit does not have to be 1000, but as many as possible up to the
value safe against intended attack.

>
>>
>>  - Use crypt safe hash and salt. (Slow and has impact to opcache/etc)
>
>
> Do we need a salt here? If not, how does it then impact opcache?

Yes. It's mandatory.
Even crypt quality hash has collisions. Attack is possible once
attackers collect enough number of collisions.

Salt breaks hashed key compatibility. Opcache saves hashes and salt  breaks it.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Stas Malyshev

9 years ago

Hi!

> Hi Stas,
>
> On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
> <smalyshev@gmail.com> wrote:
>>
>>> I think we are better to limit max collisions.
>>> I'm +1 for Nikita's proposal does this.
>>
>> Max collision per what? How much would be the limit?
>
> Collision by keys.

Not sure I understand. What would be counted - number of collision per
key? Per hashtable? Per process? Per request?

> It would be nice to have configurable limit like regex stack/backtrack limit.
> That said, wouldn't 1000 enough for almost all apps?

Certainly not. Not even nearly enough. Collisions are pretty frequent
with short strings, for example, and for a big long-running application
1000 hash collisions is nothing. I think you severely underestimate how
frequent hash collisions are, with simple function like we're using,
over millions and millions of hash accesses that we're doing routinely.

I did a quick check, and just running run-tests.php -h (without any
tests!) produces about 5K collisions. Running composer (without doing
anything) - 8K collisions. Running composer update on a simple project -
400K (!) collisions. Now these are pretty simple cases compared to what
a complex modern PHP application does. So I think you are
underestimating it by about 4-5 orders of magnitude.

>
> Anyway, we have two choices
>  - Simply limit the number of collisions. (Fast and has no impact to code)

Fast: true, no impact: not so much. If the limit is too low for your app
(and you probably have no idea how many collisions your app has, and it
is probably highly varied too) your app breaks in some very creative
ways, including dropping dead in the middle of transactions, being
unable to handle errors, etc.

>  - Use crypt safe hash and salt. (Slow and has impact to opcache/etc)

These not the only two choices.

> Limiting something is good to have sometimes.
> Python even limits number of recursions to 1000 by default.

Recursion limits are completely different. With recursion, with any
proper algorithm, the deeper you go the probability of having next
recursion step drops dramatically (usually exponentially - that's how
you build performant algorithms). However, hash collisions are
completely independent, so having one does not change the chance you
have another (in fact, it may make it higher if the same data is
processed again).

Which means, for recursion, it is very probable there is a limit that
most of your code will never reach. Even then we are cautious of it as
there's no good number for a natural limit.

But with hash collisions, I just see no way to tell "10K collisions is
enough for anything" and at least my quick checks - unless I massively
messed up the test - shows that it's not easy to find a practical limit,
at least with current hash function.

> We have PCRE stack/backtrack limits. (We'll have mbregex stack limit soon)
> Collision limit is good one also.

Does not follow, as per above.

--
Stas Malyshev
smalyshev@gmail.com

Yasuo Ohgaki

9 years ago

Hi Stas,

On Thu, Sep 22, 2016 at 7:47 AM, Stanislav Malyshev <smalyshev@gmail.com> wrote:

>> On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
>> <smalyshev@gmail.com> wrote:
>>>
>>>> I think we are better to limit max collisions.
>>>> I'm +1 for Nikita's proposal does this.
>>>
>>> Max collision per what? How much would be the limit?
>>
>> Collision by keys.
>
> Not sure I understand. What would be counted - number of collision per
> key? Per hashtable? Per process? Per request?

IIRC, proposed patch was detecting collisions per key.

>
>> It would be nice to have configurable limit like regex stack/backtrack limit.
>> That said, wouldn't 1000 enough for almost all apps?
>
> Certainly not. Not even nearly enough. Collisions are pretty frequent
> with short strings, for example, and for a big long-running application
> 1000 hash collisions is nothing. I think you severely underestimate how
> frequent hash collisions are, with simple function like we're using,
> over millions and millions of hash accesses that we're doing routinely.
>
> I did a quick check, and just running run-tests.php -h (without any
> tests!) produces about 5K collisions. Running composer (without doing
> anything) - 8K collisions. Running composer update on a simple project -
> 400K (!) collisions. Now these are pretty simple cases compared to what
> a complex modern PHP application does. So I think you are
> underestimating it by about 4-5 orders of magnitude.

I agree that we cannot be sure how many collision limit is proper for
certain app.
This is the same for memory limit, stack limit, backtrack limit,
recursion limit.

It is possible to set reasonable limit that is good enough for almost
all apps. AFAIK, we don't have a bug report complains slow hash
operation for normal code yet. IMO, this is the evidence that we can
set collision limit safely and prevent intended hash collision
attacks.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Tom Worster

9 years ago

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

Tom Worster

9 years ago

On 9/15/16 2:48 PM, 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/
>
> (Look at all the other languages that already adopted SipHash.)

I briefly looked through the "Users" list and didn't find anything
equivalent to using it as PHP's internal base hash.

Python and Rust have an implementation available to users. Ruby is using
it internally but I think it's focused on JSON.

There's some good info[1] on the situation in Perl 5. While SipHash is
available it requires a non-default compile-time option.

Correct me if I'm not reading the situation right.

Tom

[1]
http://news.perlfoundation.org/2012/12/improving-perl-5-grant-report-11.html