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: *Encryption and hash functions +Package: Scripting Engine problem PHP Version: 5.6.14 Block user comment: N Private report: N New Comment: 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. Previous Comments: ------------------------------------------------------------------------ [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/10586 https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function Perhaps that would a way to go for PHP as well? ------------------------------------------------------------------------ [2015-10-06 07:39:09] nikic@php.net The main problem with switching to SipHash is that hashtables in PHP very often use integer keys. While we could probably start using SipHash for string keys (we need to test the performance impact here), I don't think it is realistic for integer keys. I don't know if there's some alternative, very cheap cryptographic hash for that case. The simplest "solution" to this problem I can think of is to keep track of collisions and bail out if some function of the number of collisions and hashtable elements becomes too large. It would likely be enough to count collisions only during rehashes and check them at the end of the operation, so there should be no performance concerns here. ------------------------------------------------------------------------ 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