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

From: ondrej Operating system: PHP version: 5.6.14 Package: *Encryption and hash functions Bug Type: Bug Bug description:trivial hash complexity DoS attack 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 bug report at https://bugs.php.net/bug.php?id=70644&edit=1 -- Try a snapshot (PHP 5.4): https://bugs.php.net/fix.php?id=70644&r=trysnapshot54 Try a snapshot (PHP 5.5): https://bugs.php.net/fix.php?id=70644&r=trysnapshot55 Try a snapshot (trunk): https://bugs.php.net/fix.php?id=70644&r=trysnapshottrunk Fixed in SVN: https://bugs.php.net/fix.php?id=70644&r=fixed Fixed in release: https://bugs.php.net/fix.php?id=70644&r=alreadyfixed Need backtrace: https://bugs.php.net/fix.php?id=70644&r=needtrace Need Reproduce Script: https://bugs.php.net/fix.php?id=70644&r=needscript Try newer version: https://bugs.php.net/fix.php?id=70644&r=oldversion Not developer issue: https://bugs.php.net/fix.php?id=70644&r=support Expected behavior: https://bugs.php.net/fix.php?id=70644&r=notwrong Not enough info: https://bugs.php.net/fix.php?id=70644&r=notenoughinfo Submitted twice: https://bugs.php.net/fix.php?id=70644&r=submittedtwice register_globals: https://bugs.php.net/fix.php?id=70644&r=globals PHP 4 support discontinued: https://bugs.php.net/fix.php?id=70644&r=php4 Daylight Savings: https://bugs.php.net/fix.php?id=70644&r=dst IIS Stability: https://bugs.php.net/fix.php?id=70644&r=isapi Install GNU Sed: https://bugs.php.net/fix.php?id=70644&r=gnused Floating point limitations: https://bugs.php.net/fix.php?id=70644&r=float No Zend Extensions: https://bugs.php.net/fix.php?id=70644&r=nozend MySQL Configuration Error: https://bugs.php.net/fix.php?id=70644&r=mysqlcfg