Bug 750547 - (CVE-2011-4885) CVE-2011-4885 php: hash table collisions CPU usage DoS (oCERT-2011-003)
CVE-2011-4885 php: hash table collisions CPU usage DoS (oCERT-2011-003)
Status: CLOSED ERRATA
Product: Security Response
Classification: Other
Component: vulnerability (Show other bugs)
unspecified
All Linux
medium Severity medium
: ---
: ---
Assigned To: Red Hat Product Security
impact=moderate,public=20111228,repor...
: Security
Depends On: 740734 768025 769754 769755 769756 769758 769761 770823 771527 771533 831137
Blocks: hashdos/oCERT-2011-003 750552
  Show dependency treegraph
 
Reported: 2011-11-01 10:52 EDT by Jan Lieskovsky
Modified: 2015-11-24 09:43 EST (History)
11 users (show)

See Also:
Fixed In Version: php 5.3.9
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2012-02-13 08:45:55 EST
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:


Attachments (Terms of Use)


External Trackers
Tracker ID Priority Status Summary Last Updated
PHP Bug Tracker 60655 None None None Never

  None (edit)
Description Jan Lieskovsky 2011-11-01 10:52:19 EDT
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
Comment 4 Jan Lieskovsky 2011-11-01 11:06:58 EDT
Acknowledgements:

Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
Comment 8 Tomas Hoger 2011-12-19 08:07:16 EST
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
Comment 10 Huzaifa S. Sidhpurwala 2011-12-20 01:37:02 EST
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.
Comment 11 Huzaifa S. Sidhpurwala 2011-12-20 02:04:16 EST
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)
Comment 12 Huzaifa S. Sidhpurwala 2011-12-20 02:05:39 EST
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.
Comment 13 Huzaifa S. Sidhpurwala 2011-12-21 23:21:24 EST
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.
Comment 18 Tomas Hoger 2011-12-28 11:05:48 EST
(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
Comment 19 Tomas Hoger 2011-12-28 11:17:40 EST
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
Comment 21 Huzaifa S. Sidhpurwala 2011-12-29 05:53:49 EST
Created php tracking bugs for this issue

Affects: fedora-all [bug 770823]
Comment 28 Vincent Danen 2012-01-11 00:16:18 EST
PHP 5.3.9 has been released with this fix:

http://www.php.net/archive/2012.php#id2012-01-11-1
Comment 29 errata-xmlrpc 2012-01-11 13:32:57 EST
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
Comment 30 Tomas Hoger 2012-01-12 08:39:53 EST
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
Comment 31 errata-xmlrpc 2012-01-18 13:44:58 EST
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
Comment 34 errata-xmlrpc 2012-01-30 13:18:42 EST
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

Note You need to log in before you can comment on or make changes to this bug.