php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Sec Bug #72433 Use After Free Vulnerability in PHP's GC algorithm and unserialize
Submitted: 2016-06-16 14:37 UTC Modified: 2016-06-23 12:51 UTC
From: 3v0n1d3 at gmail dot com Assigned: dmitry
Status: Closed Package: *General Issues
PHP Version: 5.5.36 OS: *
Private report: No CVE-ID: 2016-5771
Password:
Status:
Package:
Bug Type:
Summary:
From: 3v0n1d3 at gmail dot com
New email:
PHP Version: OS:

 

 [2016-06-16 14:37 UTC] 3v0n1d3 at gmail dot com
Description:
------------
A critical use after free vulnerability was discovered when PHP's garbage collection algorithm interacts with other specific PHP objects.
This vulnerability has wide reaching effects like allowing the exploitation of unserialize to gain remote code execution on a target system.

While analyzing PHP's unserialize function we have found some serious flaws in PHP's internal GC algorithm.
Those flaws can be exploited in a local or even remote context e.g. over PHP's unserialize function.

The vulnerability in this report does not affect PHP 7.
Please refer to our second report to see another vulnerability that affects all PHP versions >= 5.3.0.

The POC clearly shows that we can abuse the garbage collector to free a target array.
At this point an attacker can craft a fake zval object and exploit the PHP process by taking over the EIP/RIP.
Since this has been done already several times (c.f. [3]) we will leave out any POC exploit at this point.

Short description of PHP's GC.
--------------------
The GC algorithm is supposed to clean up zvals with cyclic references (c.f. [1]).

Every time a zval is destructed the GC algorithm gets involved and checks if this zval is a possible root candidate i.e. an array or object.
If this is the case this zval is added to a root buffer (this buffer basically keeps track of potential zvals with cyclic references).
This step is repeated until either
a) gc_collect_cycles() is called manually
or 
b) more than GC_ROOT_BUFFER_MAX_ENTRIES (defined in the head section of 'Zend/zend_gc.c') zvals have been stored in the root buffer.
   This step will also automatically invoke a call to gc_collect_cycles.

gc_collect_cycles will then apply a marking algorithm.
This algorithm can be divded into the following steps:
1) gc_mark_roots(TSRMLS_C);
   Apply gc_mark_grey to all elements in the root buffer:
   1.1) Traverse all its children in a recursive fashion.
   1.2) Decrement every visited zval's reference count by 1 and mark it grey.
2) gc_scan_roots(TSRMLS_C);
   Apply gc_mark_white to all elements in the root buffer that have a ref count of 0.
   1.1) Traverse all its children in a recursive fashion.
        Apply gc_mark_white again if the ref count is 0, else apply gc_mark_black on this zval recursively.
3) gc_collect_roots(TSRMLS_C);
   Restore the refcount of all elements and put all white nodes into a list to free.
4) Finally, free all elements that have been marked white.
--------------------

Unfortunately, this algorithm can be tricked into decrementing specific entries multiple times, although those entries have already been marked grey.
Please consider the following scenario:

We initialize an ArrayObject with a reference to another array (this can be easily done in e.g. an unserialize context).
Once the GC algorithm tries to access the elements inside this ArrayObject it will execute ('Zend/zend_gc.c', 'gc_mark_grey' method):
HashTable *props = get_gc(pz, &table, &n TSRMLS_CC);

This method is supposed to call the gc method of the object in question (in our case the gc method of our ArrayObject).
However, in this case the ArrayObject class does not have an own gc method (this method was first introduced in PHP-7.1.0alpha1 c.f. [2]).

In case an object does not have a gc method, its "get_properties" method will be invoked instead.
Hence, 'spl_array_get_properties' will be called instead.

This method will retrieve all elements inside the internal array (intern->array).
Since this array is a reference the method will return the hash table of any target array.

By abusing those circumstances it is possible to decrement the reference counters of all elements in one specific array multiple times.
If done properly this element and all its children will be marked white and will be freed by the gc algorithm although there still exist dangling pointers.


Please note:
Calling "gc_collect_cycles()" manually is not necessary.
The garbage collection can also be invoked during the unserialization process making this vulnerability remotely exploitable.
This vulnerability was successfully exploited over remote in a local setup.

Further, please consider that using "unserialize" is optional. This bug is very likely to be exploitable in other scenarios, too.

Suggested fix:
Make sure that 'ext/spl/spl_array.c' gets a proper gc method (like was done for PHP 7 c.f. [2]).


This bug was very difficult to find since it involves several components interacting together in a relatively sophisticated way.
Due to complexity reasons a lot of details and further description are left out in this report.
Hence, we intend to do a thorough and detailed writeup about this vulnerability once it gets acknowledged in another context.

Thank you for your consideration.
Please feel free to ask for more technical details if necessary.

References:
[1] http://php.net/manual/de/features.gc.collecting-cycles.php
[2] https://github.com/php/php-src/commit/4e03ba4a6ef4c16b53e49e32eb4992a797ae08a8
[3] https://hackerone.com/reports/73235



Test script:
---------------
<?php
// Fill any potential freed spaces until now.
$filler = array();
for($i = 0; $i < 100; $i++)
	$filler[] = "";
// Create our payload and unserialize it.
$serialized_payload = 'a:3:{i:0;r:1;i:1;r:1;i:2;C:11:"ArrayObject":19:{x:i:0;r:1;;m:a:0:{}}}';
$free_me = unserialize($serialized_payload);
// We need to increment the reference counter of our ArrayObject s.t. all reference counters of our unserialized array become 0.
$inc_ref_by_one = $free_me[2];
// The call to gc_collect_cycles will free '$free_me'.
gc_collect_cycles();
// We now have multiple freed spaces. Fill all of them.
$fill_freed_space_1 = "filler_zval_1";
$fill_freed_space_2 = "filler_zval_2";
var_dump($free_me);

Expected result:
----------------
Array with three elements: 2 references and one ArrayObject

Actual result:
--------------
string(13) "filler_zval_2"

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2016-06-17 02:39 UTC] 3v0n1d3 at gmail dot com
Adding missing sections.
Affected Versions:
------------------------
Affected are all PHP versions >= PHP 5.3.0 and < PHP 7.

Credits:
------------------------
This vulnerability was discovered by Ruslan Habalov and Dario Wei├čer.
 [2016-06-21 04:28 UTC] stas@php.net
-Assigned To: +Assigned To: dmitry
 [2016-06-21 04:28 UTC] stas@php.net
Fix in security repo as 3f627e580acfdaf0595ae3b115b8bec677f203ee and in https://gist.github.com/efc065a5685d9305cf900f862c80cb1a

Please verify.
 [2016-06-21 04:28 UTC] stas@php.net
-PHP Version: 5.6.23RC1 +PHP Version: 5.5.36
 [2016-06-21 06:54 UTC] stas@php.net
-Status: Assigned +Status: Closed
 [2016-06-21 06:54 UTC] stas@php.net
The fix for this bug has been committed.

Snapshots of the sources are packaged every three hours; this change
will be in the next snapshot. You can grab the snapshot at
http://snaps.php.net/.

 For Windows:

http://windows.php.net/snapshots/
 
Thank you for the report, and for helping us make PHP better.


 [2016-06-21 20:05 UTC] 3v0n1d3 at gmail dot com
Thank you for your fast reply and fast fix of this issue.
The patch is exactly right.
 [2016-06-23 12:51 UTC] kaplan@php.net
-CVE-ID: +CVE-ID: 2016-5771
 [2016-07-25 11:56 UTC] uskokovic at gmail dot com
If I run the testscript with zend.enable_gc=1 (which is the default) I can verify vulnerability:
$ php -d zend.enable_gc=1 testscript
string(13) "filler_zval_2"

but with zend.enable_gc=0 it seems OK:
$ php -d zend.enable_gc=0 testscript
array(3) {
  [0]=>
  *RECURSION*
  [1]=>
  *RECURSION*
  [2]=>
  object(ArrayObject)#1 (1) {
    ["storage":"ArrayObject":private]=>
    *RECURSION*
  }
}

Does setting zend.enable_gc=0 efects only test script or does it disable this vulnerability?

Does setting zend.enable_gc=0 in php.ini (and disabling the gc_enable function) seem like a reasonable workaround until updating to non-vulnerable version of PHP?
 [2016-10-11 04:20 UTC] lisycy at gmail dot com
zend.enable_gc=1 is necessary.
this bug was showing a gc implement bug
 
PHP Copyright © 2001-2017 The PHP Group
All rights reserved.
Last updated: Tue Aug 29 15:01:52 2017 UTC