# HashDoS

- Thread: https://externals.io/message/96007
- Original archive: https://news-web.php.net/php.internals/96007
- Started by Scott Arciszewski on 2016-09-15T18:48:28+00:00
- Messages: 52
- Page 1 of 3: messages 1 to 25 (25 per page, add `?page=N` to the URL)
- Next page: https://externals.io/message/96007.md?page=2
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #96007 — Scott Arciszewski — 2016-09-15T18:48:28+00:00

URL: https://externals.io/message/96007#96007

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

---

## #96008 — Nikita Popov — 2016-09-15T18:56:42+00:00

URL: https://externals.io/message/96007#96008 · In reply to: #96007

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

---

## #96010 — Yasuo Ohgaki — 2016-09-15T21:14:07+00:00

URL: https://externals.io/message/96007#96010 · In reply to: #96008

Hi Nikita,


>
> 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

---

## #96011 — Stanislav Malyshev — 2016-09-16T00:20:43+00:00

URL: https://externals.io/message/96007#96011 · In reply to: #96007

Hi!


> 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

---

## #96014 — Thomas Hruska — 2016-09-16T05:59:39+00:00

URL: https://externals.io/message/96007#96014 · In reply to: #96011

> Hi!
>
> 
> > […]
>
> 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/

---

## #96018 — Nikita Popov — 2016-09-16T10:20:59+00:00

URL: https://externals.io/message/96007#96018 · In reply to: #96014

On Fri, Sep 16, 2016 at 7:59 AM, Thomas Hruska <thruska@cubiclesoft.com>
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.
>
> 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

---

## #96020 — Scott Arciszewski — 2016-09-16T13:30:05+00:00

URL: https://externals.io/message/96007#96020 · In reply to: #96014

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:

> 
>
> > […]
>
> 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/

---

## #96023 — Stanislav Malyshev — 2016-09-17T08:13:49+00:00

URL: https://externals.io/message/96007#96023 · In reply to: #96020

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

---

## #96025 — Yasuo Ohgaki — 2016-09-17T22:35:50+00:00

URL: https://externals.io/message/96007#96025 · In reply to: #96023

Hi all,


> > […]
>
> 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

---

## #96037 — Tom Worster — 2016-09-20T14:22:10+00:00

URL: https://externals.io/message/96007#96037 · In reply to: #96014

> 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

---

## #96038 — Tom Worster — 2016-09-20T14:22:49+00:00

URL: https://externals.io/message/96007#96038 · In reply to: #96007

> 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

---

## #96039 — Scott Arciszewski — 2016-09-20T14:33:44+00:00

URL: https://externals.io/message/96007#96039 · In reply to: #96025

> Hi all,
>
> On Sat, Sep 17, 2016 at 5:13 PM, Stanislav Malyshev <smalyshev@gmail.com>
> wrote:
> > […]
>
> 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/

---

## #96041 — Stanislav Malyshev — 2016-09-21T02:25:39+00:00

URL: https://externals.io/message/96007#96041 · In reply to: #96039

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

---

## #96042 — Stanislav Malyshev — 2016-09-21T02:26:43+00:00

URL: https://externals.io/message/96007#96042 · In reply to: #96025

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

---

## #96043 — Yasuo Ohgaki — 2016-09-21T06:54:02+00:00

URL: https://externals.io/message/96007#96043 · In reply to: #96042

Hi Stas,

On Wed, Sep 21, 2016 at 11:26 AM, Stanislav Malyshev
<smalyshev@gmail.com> wrote:
>
> > […]
>
> 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

---

## #96044 — Niklas Keller — 2016-09-21T08:06:25+00:00

URL: https://externals.io/message/96007#96044 · In reply to: #96043

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:
> > […]
>
> 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


> 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

---

## #96048 — Glenn Eggleton — 2016-09-21T12:02:20+00:00

URL: https://externals.io/message/96007#96048 · In reply to: #96044

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



> 2016-09-21 8:54 GMT+02:00 Yasuo Ohgaki <yohgaki@ohgaki.net>:
>
> > […]
>
> Having a limit isn't a good idea for all use cases, but it works for some.
>
>
> > […]
> 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.
>
>
> > […]
>
> Do we need a salt here? If not, how does it then impact opcache?
>
>
> > […]
>
> Recursion is / should not be affected by user input and thus is a slightly
> different topic.
>
> Regards, Niklas
>
>
> > […]
> soon)
> > […]

---

## #96050 — Rowan Collins — 2016-09-21T12:37:29+00:00

URL: https://externals.io/message/96007#96050 · In reply to: #96048

>What if we had some sort of configuration limit on collision length?

Previous discussions have come to the conclusion that the difference between normal collision frequency and sufficient for a DoS is so large that the only meaningful settings would be on or off. e.g. the proposed limit is 1000, and randomly inserting millions of rows produces about 12.

The problem with long running applications is not that they need to raise the limit, it's that they need to handle the error gracefully if they are in fact under attack. Because hash tables are so ubiquitous in the engine, there's no guarantee that that's possible, so an attacker would have the ability to crash the process with the limit turned on, or hang the CPU with the limit turned off.

Regards,

-- 
Rowan Collins
[IMSoP]

---

## #96053 — Niklas Keller — 2016-09-21T13:22:53+00:00

URL: https://externals.io/message/96007#96053 · In reply to: #96050

2016-09-21 14:37 GMT+02:00 Rowan Collins <rowan.collins@gmail.com>:

> On 21 September 2016 13:02:20 BST, Glenn Eggleton <geggleto@gmail.com>
> wrote:
> > […]
>
> Previous discussions have come to the conclusion that the difference
> between normal collision frequency and sufficient for a DoS is so large
> that the only meaningful settings would be on or off. e.g. the proposed
> limit is 1000, and randomly inserting millions of rows produces about 12.
>
> The problem with long running applications is not that they need to raise
> the limit, it's that they need to handle the error gracefully if they are
> in fact under attack. Because hash tables are so ubiquitous in the engine,
> there's no guarantee that that's possible, so an attacker would have the
> ability to crash the process with the limit turned on, or hang the CPU with
> the limit turned off.


Another suggestion by Markus Staab is to move the code into the SAPIs and
have SipHash in CLI and the current hash function in e.g. Apache's SAPI.

Since long running applications use only the CLI, it would be fine for them
and it wouldn't even need a compile flag.

Regards, Niklas

---

## #96058 — Tom Worster — 2016-09-21T13:51:32+00:00

URL: https://externals.io/message/96007#96058 · In reply to: #96041

> 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

---

## #96059 — Tom Worster — 2016-09-21T14:05:41+00:00

URL: https://externals.io/message/96007#96059 · In reply to: #96050

> 
> > […]
>
> Previous discussions have come to the conclusion that the difference between normal collision frequency and sufficient for a DoS is so large that the only meaningful settings would be on or off. e.g. the proposed limit is 1000, and randomly inserting millions of rows produces about 12.
>
> The problem with long running applications is not that they need to raise the limit, it's that they need to handle the error gracefully if they are in fact under attack. Because hash tables are so ubiquitous in the engine, there's no guarantee that that's possible, so an attacker would have the ability to crash the process with the limit turned on, or hang the CPU with the limit turned off.

Right. It seems like count-and-limit pushes the problem onto the user 
who then has to discriminate normal from malicious causes for rising 
counters and find appropriate actions for each.

Even a sophisticated user who understands hash collision counters may 
not welcome this since it adds complexity that's hard to test and 
involves questionable heuristics.

Tom

---

## #96060 — Nikita Popov — 2016-09-21T14:08:45+00:00

URL: https://externals.io/message/96007#96060 · In reply to: #96053

> 2016-09-21 14:37 GMT+02:00 Rowan Collins <rowan.collins@gmail.com>:
>
> > […]
> engine,
> > […]
> with
> > […]
>
>
> Another suggestion by Markus Staab is to move the code into the SAPIs and
> have SipHash in CLI and the current hash function in e.g. Apache's SAPI.
>
> Since long running applications use only the CLI, it would be fine for them
> and it wouldn't even need a compile flag.
>
> Regards, Niklas
>

Just so we're clear, switching to siphash is not just a matter of replacing
a hash function implementation. It requires larger changes [1] to support
non-trivial integer hashes which a) change the structure of HashTable
buckets and may have performance impact even if we continue using identity
hashing and b) will definitely lead to changes in the internal hashtable
API, so this may require changes in extensions. (Collision counting on the
other hand is fully transparent.)

Nikita

[1] https://github.com/php/php-src/compare/master...nikic:integerHash

---

## #96061 — Nikita Popov — 2016-09-21T14:23:11+00:00

URL: https://externals.io/message/96007#96061 · In reply to: #96059

> 
>
> > […]
>
> Right. It seems like count-and-limit pushes the problem onto the user who
> then has to discriminate normal from malicious causes for rising counters
> and find appropriate actions for each.
>
> Even a sophisticated user who understands hash collision counters may not
> welcome this since it adds complexity that's hard to test and involves
> questionable heuristics.
>
> Tom
>

Quoting a relevant part of the previous discussion:

> Lets [try] to quantify the probability of reaching the collision limit C
with a hashtable of size N and assuming a random hash distribution. The
upper bound for this should be (N choose C) * (1/N)^(C-1), with (1/N)^(C-1)
being the probability that C elements hash to one value and (N over C) the
number of C element subsets of an N element set. For large N and N >> C we
approximate (N choose C) to (e*N/C)^C / sqrt(2pi*C). As such our upper
bound becomes N * (e/C)^C / sqrt(2pi*C). Choosing N = 2^31 (largest
possible hashtable) we get for C = 20 probability 8.9E-10 and for C = 100
probability 2.3E-149. The patch uses C = 1000.

In other words, it is extremely unlikely that you hit the collision limit
by accident, with non-malicious data. So no, the user does not have to
discriminate normal from malicious causes. If the limit triggers, it's
malicious.

Nikita

---

## #96063 — Glenn Eggleton — 2016-09-21T14:49:17+00:00

URL: https://externals.io/message/96007#96063 · In reply to: #96061

This might be a bit off topic....

Given that you can set POST_REQUEST_SIZE in a production PHP application,
how likely is it really that an app will encounter a HashDos attack?

From what I gather this will require MBs to GBs of data in order to cause a
DoS.

From the web side, I think there are enough tools to prevent HashDos from
happening...

Would the issue then affect only CLI users?

Sorry, if this seems like a derail, I am pretty new to the internals list.

Cheers, Glenn



> 
>
> > […]
> 12.
> > […]
> raise
> > […]
> are
> > […]
> engine,
> > […]
> with
> > […]
>
> Quoting a relevant part of the previous discussion:
>
> > […]
> with a hashtable of size N and assuming a random hash distribution. The
> upper bound for this should be (N choose C) * (1/N)^(C-1), with (1/N)^(C-1)
> being the probability that C elements hash to one value and (N over C) the
> number of C element subsets of an N element set. For large N and N >> C we
> approximate (N choose C) to (e*N/C)^C / sqrt(2pi*C). As such our upper
> bound becomes N * (e/C)^C / sqrt(2pi*C). Choosing N = 2^31 (largest
> possible hashtable) we get for C = 20 probability 8.9E-10 and for C = 100
> probability 2.3E-149. The patch uses C = 1000.
>
> In other words, it is extremely unlikely that you hit the collision limit
> by accident, with non-malicious data. So no, the user does not have to
> discriminate normal from malicious causes. If the limit triggers, it's
> malicious.
>
> Nikita

---

## #96064 — Nikita Popov — 2016-09-21T15:00:11+00:00

URL: https://externals.io/message/96007#96064 · In reply to: #96063

> This might be a bit off topic....
>
> Given that you can set POST_REQUEST_SIZE in a production PHP application,
> how likely is it really that an app will encounter a HashDos attack?
>
> From what I gather this will require MBs to GBs of data in order to cause
> a DoS.
>
> From the web side, I think there are enough tools to prevent HashDos from
> happening...
>
> Would the issue then affect only CLI users?
>
> Sorry, if this seems like a derail, I am pretty new to the internals list.
>
> Cheers, Glenn
>

Again quoting previous thread:

> This DOS vulnerability is efficient: A 700kb payload can easily take 5
CPU seconds to process on PHP 7 and from there it goes up quadratically
(i.e. 1.4MB payload takes 20 seconds etc)

I don't remember exactly under what circumstances these numbers are
correct. I think the sizes refer to JSON payloads and the system is a
recent gen i5. So for the default post_max_size of 8M = approx 11*700kb we
get an expected execution time of 5*(11)^2 seconds, which is about 10
minutes. Of course, the execution time limit will trigger before that :)

So unless your post data size limit is very small or you perform additional
size validation on JSON data (and other data) you receive, this attack is
quite practical and not just a theoretical concern :)

Nikita

---

Next page: https://externals.io/message/96007.md?page=2
