Bug 750547 (CVE-2011-4885)

Summary: CVE-2011-4885 php: hash table collisions CPU usage DoS (oCERT-2011-003)
Product: [Other] Security Response Reporter: Jan Lieskovsky <jlieskov>
Component: vulnerabilityAssignee: Red Hat Product Security <security-response-team>
Status: CLOSED ERRATA QA Contact:
Severity: medium Docs Contact:
Priority: medium    
Version: unspecifiedCC: bmumbaik, d.busby, dkutalek, fche, jorton, kseifried, menthos, security-response-team, vvitek, wnefal+redhatbugzilla, zxvdr.au
Target Milestone: ---Keywords: Security
Target Release: ---   
Hardware: All   
OS: Linux   
Whiteboard:
Fixed In Version: php 5.3.9 Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2012-02-13 13:45:55 UTC Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: --- Target Upstream Version:
Embargoed:
Bug Depends On: 740734, 768025, 769754, 769755, 769756, 769758, 769761, 770823, 771527, 771533, 831137    
Bug Blocks: 750552, 770929    

Description Jan Lieskovsky 2011-11-01 14:52:19 UTC
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 15:06:58 UTC
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 13:07:16 UTC
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 06:37:02 UTC
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 07:04:16 UTC
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 07:05:39 UTC
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-22 04:21:24 UTC
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 16:05:48 UTC
(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 16:17:40 UTC
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 10:53:49 UTC
Created php tracking bugs for this issue

Affects: fedora-all [bug 770823]

Comment 28 Vincent Danen 2012-01-11 05:16:18 UTC
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 18:32:57 UTC
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 13:39:53 UTC
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 18:44:58 UTC
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 18:18:42 UTC
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