Julian Wälde and Alexander Klink reported a flaw in the hash function used in the implementation of the PHP arrays. PHP arrays are implemented using the hash table that maps keys to values: http://www.php.net/manual/en/language.types.array.php A specially-crafted set of keys could trigger hash function collisions, which degrade hash table performance by changing hash table operations complexity from an expected/average O(1) to the worst case O(n). Reporters were able to find colliding strings efficiently using equivalent substrings or meet in the middle techniques. As PHP automatically pre-fills certain arrays (such as $_POST, $_GET, or $_COOKIE) with data from the HTTP request before executing a script, a remote attacker could use this flaw to make PHP use excessive amount of CPU time by sending a POST request with large amount of parameters which hash to the same value. This problem is similar to the issue that was previously reported for and fixed in e.g. perl: http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf
Acknowledgements: Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
Upstream patches that add max_input_vars configuration directive to limit the number of parameters that will be parsed to $_GET, $_POST and $_COOKIE arrays from the HTTP requests: http://svn.php.net/viewvc?view=revision&revision=321003 http://svn.php.net/viewvc?view=revision&revision=321040
Mitigations: ============ Reporter mentioned that two PHP config variables can mitigate the effect of the attack. 1. post_max_size http://www.php.net/manual/en/ini.core.php#ini.post-max-size This limits the size of the data which can be sent in a POST request. This is effective in controlling this attack to some extent. When running the reproducer I see the following lines in the log file. [Tue Dec 20 01:25:11 2011] [error] [client 10.0.0.1] PHP Warning: Unknown: POST Content-Length of 34000000 bytes exceeds the limit of 8388608 bytes in Unknown on line 0 If anything exceeds post_max_size, $_POST and $_FILES will be empty. However a downside is that, since this value affects file upload as well, the value of this configuration directive is often increased to accommodate upload of larger files. The default value of 8M allows attacker to trigger this attack. 2. max_input_time http://www.php.net/manual/en/info.configuration.php#ini.max-input-time This sets the maximum time in seconds a script is allowed to parse input data, like POST and GET parameters. Setting this to a lower value (10s in my case) shows the following in the log files: [Tue Dec 20 02:04:51 2011] [error] [client 10.0.0.1] PHP Fatal error: Maximum execution time of 10 seconds exceeded in Unknown on line 0 Following which PHP stops processing the script and CPU usage goes back to normal. The default value is 60, due to which the script execution will get killed after 60 seconds.
I am able to successfully reproduce this on rhel-6 and rhel-5 (both php and php53). On both of these, the above mitigations work. In case of rhel-4, php sets memory_limit in php.ini as 8M as opposed to 128M in the case of other rhels. This results in php being killed before the 60 second execution limit is reached, with the following error in the logs. Allowed memory size of 8388608 bytes exhausted (tried to allocate 51 bytes)
This issue affects the version of php as shipped with Red Hat Enterprise Linux 4, 5 and 6. This issue affects the version of php53 as shipped with Red Hat Enterprise Linux 5. This issue affects the version of php as shipped with Fedora release 15 and 16.
Upstream has reported an issue in the patches described in comment #8: These patches may have a problem - throwing fatal error during request startup may lead to unexpected behavior later. I'll try to resolve it ASAP.
(In reply to comment #13) > Upstream has reported an issue in the patches described in comment #8: > > These patches may have a problem - throwing fatal error during request > startup may lead to unexpected behavior later. I'll try to resolve it > ASAP. These concerns seem to be addressed in: http://svn.php.net/viewvc?view=revision&revision=321335
This issue was presented today on 28C3: http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html Details were posted to full-disclosure: http://seclists.org/fulldisclosure/2011/Dec/477
oCERT advisory: http://www.ocert.org/advisories/ocert-2011-003.html n.runs advisory (copy of the full-disclosure post): http://www.nruns.com/_downloads/advisory28122011.pdf 28C3 slides and recording: http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf http://www.youtube.com/28c3#p/u/22/R2Cq3CLI6H8 Another good write-up of the issue: http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/
Created php tracking bugs for this issue Affects: fedora-all [bug 770823]
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html
PHP 5.3.9 has been released with this fix: http://www.php.net/archive/2012.php#id2012-01-11-1
This issue has been addressed in following products: Red Hat Enterprise Linux 5 Red Hat Enterprise Linux 6 Via RHSA-2012:0019 https://rhn.redhat.com/errata/RHSA-2012-0019.html
PHP bug tracking proposed addition of limit or randomization to help in json and unserialize use cases: https://bugs.php.net/bug.php?id=60655
This issue has been addressed in following products: Red Hat Enterprise Linux 5 Via RHSA-2012:0033 https://rhn.redhat.com/errata/RHSA-2012-0033.html
This issue has been addressed in following products: Red Hat Enterprise Linux 4 Via RHSA-2012:0071 https://rhn.redhat.com/errata/RHSA-2012-0071.html