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"