Edit report at https://bugs.php.net/bug.php?id=70644&edit=1
ID: 70644
Comment by: nikic@php.net
Reported by: ondrej@php.net
Summary: trivial hash complexity DoS attack
Status: Open
Type: Bug
Package: Scripting Engine problem
PHP Version: 5.6.14
Block user comment: N
Private report: N
New Comment:
One way to potentially make the integer hashing feasible, is to introduce an intermediary step
between packed hashes and unpacked ones:
Packed hashes only work if the numeric array is both dense and sorted ascending by key. We could add
another level that works for dense numeric arrays in general, but does not require a certain key
order. In this case the data array would contain the elements in arbitrary order and the hash array
would map key to order. With that extra level, we'd only start hashing keys for sparse numeric
arrays.
Allowing integer hashes at all will require us to switch to a key union. This may negatively affect
array iteration.
Previous Comments:
------------------------------------------------------------------------
[2015-10-08 09:45:16] nikic@php.net
Here is an implementation for collision counting: https://github.com/php/php-src/compare/master...nikic:collisionCount
Collisions are counted during insert operations, if they exceed a certain level, you get a fatal
error. From some initial testing, this doesn't seem to have significant perf impact.
One problem is that this approach doesn't work with add_new, so I had to rewrite some code to
move away from it.
------------------------------------------------------------------------
[2015-10-07 16:39:52] nikic@php.net
Also, the idea about counting collisions during rehash won't work either. It won't be able
to distinguish between few collisions on many elements and many collisions on few elements. So for
size=8 both keys 0 1 2 3 8 9 10 11 and 0 1 2 3 8 16 24 would result in 4 collisions, but only the
latter kind would be problematic (for larger sizes of course). We'd have to do per-hash-slot
counts, which would no longer be cheap.
------------------------------------------------------------------------
[2015-10-07 16:24:04] nikic@php.net
Here's a branch for testing siphash (doesn't use a key, just perf experiment): https://github.com/php/php-src/compare/master...nikic:siphash
From a few quick tests, SipHash doesn't seem to have significant impact on our standard
benchmarks (though I didn't do instruction counts). On a synthetic benchmark (inserting English
dict in a hashtable) I got something like 10% slowdown.
So for string hashes, this is an option. The integer hash problem stays though...
------------------------------------------------------------------------
[2015-10-06 11:32:39] ondrej@php.net
Further investigation shows that at least in Python it was shown that FNV hashing is not enough to
protect against collision attacks and Python has converted everything to SipHash-2-4: https://www.python.org/dev/peps/pep-0456/
------------------------------------------------------------------------
[2015-10-06 11:26:04] ondrej@php.net
Looks like they has a same problem in Rust language and the solution was to use FNV hashing: https://github.com/rust-lang/rust/issues/10586https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
Perhaps that would a way to go for PHP as well?
------------------------------------------------------------------------
The remainder of the comments for this report are too long. To view
the rest of the comments, please view the bug report online at
https://bugs.php.net/bug.php?id=70644
--
Edit this bug report at https://bugs.php.net/bug.php?id=70644&edit=1