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 PHP Version: 5.6.14 Block user comment: N Private report: N New Comment: 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... Previous Comments: ------------------------------------------------------------------------ [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. ------------------------------------------------------------------------ [2015-10-06 07:26:50] phpmpan at mpan dot pl Note: there already exists a PHP extension for SipHash [1]. Unfortunely of unknown licence, but it is based on public domain version [2], which also may be used as a quick fix. Both of them linked from Aumasson's website. [1] <https://github.com/jedisct1/siphash-php> [2] <https://github.com/floodyberry/siphash> ------------------------------------------------------------------------ [2015-10-05 15:34:49] ondrej@php.net Description: ------------ As reported here: https://bugs.debian.org/800564 by brian m. carlson: Applies to all PHP versions. PHP uses the DJB "times 33" hash to hash strings in its hash tables, without the use of any secret key. Hash values are therefore the same between multiple invocations. As a result, it's trivial to precompute a set of values that all hash to the same bucket and cause positively abysmal performance. If a script accepts untrusted hash keys, such as from JSON input, it is subject to a DoS attack. PHP implemented the max_input_vars option, but this is not effective in the general case, especially in the era of JSON-laden POST requests. Perl, Python, and Ruby have all addressed their CVEs properly, but PHP has not and as a result is still vulnerable. Cloning my example repository[0] and running "php scripts/exploited.php < example/1048576.json" demonstrates the problem very quickly. The similar Perl and Python scripts are not vulnerable to this attack. A JSON file containing only 65536 entries takes PHP 5.6 22 seconds to process. A new CVE should probably be allocated and the bug should be fixed correctly this time, probably by seeding a key from /dev/urandom and using SipHash-2-4 or the like. Python had CVE-2012-1150 and CVE-2013-7040. Ruby had CVE-2011-4815. I can't find a CVE for Perl's 2003 fix, if one exists. The fix, which went into 5.8, was incomplete and was addressed by CVE-2013-1667. [0] https://github.com/bk2204/php-hash-dos Test script: --------------- https://github.com/bk2204/php-hash-dos ------------------------------------------------------------------------ -- Edit this bug report at https://bugs.php.net/bug.php?id=70644&edit=1