Bug #70644 [Opn]: trivial hash complexity DoS attack

Edit report at https://bugs.php.net/bug.php?id=70644&edit=1 ID: 70644 Updated 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: Just got around to doing some microbenchmarks. For switching everything to siphash (incl integer hashes): SipHash Baseline Packed int insert: 16.9 mus +/- 0.3 mus 17.1 mus +/- 0.1 mus -1.0% Reverse int insert: 49.0 mus +/- 0.4 mus 17.3 mus +/- 0.2 mus +182.7% Reverse int insert x16 collisions: 54.0 mus +/- 1.1 mus 43.3 mus +/- 0.2 mus +24.6% Incrementing string insert: 62.6 mus +/- 0.7 mus 44.8 mus +/- 0.3 mus +39.6% This means unpacked integer hashtable is about 3x slower. The break-even point with the previous implementation is somewhere between 16x and 32x collisions per bucket. For very short strings w/o hash cache we have 40% slowdown. It's unlikely that this will be deemed acceptable even with more optimization work (like the semi-packed variant mentioned above). So we should probably go with the collision counting during insert. Previous Comments: ------------------------------------------------------------------------ [2015-10-08 22:52:53] nikic@php.net Just looked at the HHVM implementation. Looks like they are also doing collision counting during find-phase of insert operations: http://lxr.php.net/xref/OTHER_IMPLEMENT/hiphop-2.0/hphp/runtime/base/array/hphp_array.cpp#555 It took a while, but here's an implementation of using siphash for everything (including integers): https://github.com/php/php-src/compare/master...nikic:integerHash ------------------------------------------------------------------------ [2015-10-08 09:56:11] nikic@php.net 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. ------------------------------------------------------------------------ [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... ------------------------------------------------------------------------ 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