== Demonstration

Run time php scripts/exploited.php < example/1048576.json >/dev/null. This script just reads in a JSON file and prints it out. If you'd like a smaller file, just run perl scripts/minimize.pl 65536 < example/1048576.json >test.json and use test.json instead. That produces a still pathological, but much smaller (1 MiB), file.

== FAQ

What is this?:: This is a straightforward proof of concept DoS against PHP. By uploading a specially-crafted JSON file to a PHP script accepting it, PHP performs so much time inserting items into the hash that it can't do anything else.

How does it work?:: PHP, like Perl, Python, and Ruby, provides hash tables, or associative arrays, that map strings (and sometimes other values) into arbitrary values. These hash tables are implemented by hashing the key with some hash function, and inserting it into the hash table's underlying array based on the bottom bits of that result. The performance of the hash table is dependent on the assumption that the hash values will be evenly distributed. + PHP, unlike Perl, Python, and Ruby, uses a hash function that computes the same value every time. As a consequence, it's possible to precompute a large number of keys where the hash values all have the relevant bits set to 0. Consequently, PHP has to perform an O(n) lookup on each insertion, access, and deletion, instead of an average case O(1).

Why aren't other languages affected?:: Perl, Python, and Ruby all use a per-invocation secret key to manipulate their hash functions so that on different invocations the same strings will hash differently. As a result, any attack on a given invocation of a program will likely not succeed on subsequent invocations. It's also nearly impossible to precompute values that will affect all invocations of those programs.

What versions of PHP are affected?:: This has been tested on PHP 7.0.0~rc3-3 as shipped by Debian. PHP 5.6 (Debian's 5.6.13+dfsg-2) is as well. From looking at the source code of PHP 5.5, it is likely affected as well. All versions of PHP using the DJB "times 33" hash should be affected.

How do I know if my PHP app is vulnerable?:: If your PHP app accepts JSON or YAML input from the user, or accepts untrusted input and inserts that input as keys in a hash, your application is likely vulnerable. An example JSON file with 1048576 entries is in the example directory. You can upload part or all of this file to your application and see how it performs. + On a 2.8 GHz Core i7, a JSON file containing 65536 entries takes the scripts/exploited.php script 5.358 seconds to process with PHP 7. With twice as many entries, it takes 21 seconds to process. PHP 5.6 performs much worse: the smaller file itself takes 22 seconds.

How do I attack other people's systems with this?:: You don't. That's unethical; shame on you.

How did you discover this?:: I looked at the source code, implemented the PHP hash function in C (after prototyping in Perl), and tested.

Why attack PHP?:: These types of attacks have been known for some time. PHP has had CVEs allocated against it in the past for these types of attacks, but the only fix provided was the max_input_vars setting. However, in the world of RESTful web frameworks and JSON-laden POST requests, this setting is ineffective. Other languages have taken this issue as serious security issue, and so should PHP. This is an issue that should be properly fixed in the interpreter.

How do I test this for myself?:: Run php scripts/exploited.php < example/1048576.json. This script just reads in a JSON file and prints it out.

I want to sue you or make legal threats.:: First of all, that's not a question. Second, threatening people doing security work is a bad idea and is bad publicity for your company. Finally, I will publish any legal threats or correspondence from lawyers or the authorities publicly. I regret that I had to add this section, but this is the world we live in.