PHP Challenge 2015 Solution

Solution for our little PHP security challenge

Introduction

Five days ago we released a little PHP security challenge on our website for people to test their knowledge about PHP security and its latest known peculiarities. If you haven't checked it out yet, you should stop reading at this point and have a look at the actual challenge. The task during that challenge was to create an input that makes the released code accept you as an admin user.

We started this challenge to raise awareness about a recently discovered problem in the PHP engine that has been fixed in the latest updates of PHP 5.5 and PHP 5.6 and meanwhile also of PHP 5.4. However it was first not considered a security problem and therefore not backported. We stumbled over this while reading the Changelog and commit messages of PHP for the last months. We do this because we create a PHP vulnerability feed that takes into consideration that the PHP team does not always mark security relevant problems as security problems. Often because the developer fixing the issue just did not see the security impact, or considered it "just a segmentation fault".

So in order to successfully solve this challenge it was required to understand PHP, think a little bit like an attacker and be up to date with the latest fixes that went into PHP.

But now let's start with solving the challenge.

Step 1 - MD5 Password Hashing

When you look through the code of the challenge, one of the first things you will see, is the following snippet of code that apparently defines a list of users.

<?php

$users = array(
        "0:9b5c3d2b64b8f74e56edec71462bd97a" ,
        "1:4eb5fb1501102508a86971773849d266",
        "2:facabd94d57fc9f1e655ef9ce891e86e",
        "3:ce3924f011fe323df3a6a95222b0c909",
        "4:7f6618422e6a7ca2e939bd83abde402c",
        "5:06e2b745f3124f7d670f78eabaa94809",
        "6:8e39a6e40900bb0824a8e150c0d0d59f",
        "7:d035e1a80bbb377ce1edce42728849f2",
        "8:0927d64a71a9d0078c274fc5f4f10821",
        "9:e2e23d64a642ee82c7a270c6c76df142",
        "10:70298593dd7ada576aff61b6750b9118"
);

$valid_user = false;

$input = $_COOKIE['user'];
$input[1] = md5($input[1]);

The code above reveals that there are 11 users that seem to be numbered 0 to 10. We also see these numbers accompanied by some hexadecimal strings that are 32 characters long. Further down we see the usage of PHP's md5() function on some user input from the cookie. This hints that the hexadecimal strings in the $users array are passwords that are MD5 hashed. This is a very bad idea because advanced cracking techniques like pre calculated rainbow tables for MD5 hashes exist that allow for fast recovery of passwords behind the hashes, if they are not too obscure or too long. However we did not expect people to have a working setup to brute force MD5 hashes in order to crack this challenge, instead we expected them to do the next best thing and throw these hashes at e.g. Google.

But we had chosen the passwords for the different users in a way that Googling for them would not result in matches, except for the hash 06e2b745f3124f7d670f78eabaa94809 of user 5. This was to highlight that when there is a hashdump of MD5 password hashes available there is always a number of users with harder to crack passwords and always a number of users with quite weak passwords. In our case the password of user 5 was "hund" which is the german word for dog. While the objective is to be able to login as admin and this password will only open access to user 5 it is the first step to solve the challenge.

For those interested we have selected really long and strong passwords for the other users and we did not expect anyone to break them. Part of them were even random and we do not know them anymore. However the password of the admin user 0 is actually still known and it is: "orewgfpeowöfgphewoöfeiuwgöpuerhjwfiuvugeröwhdböcp9ueiwrbcvzeiwuböochineworöcern". The likelihood of finding this password in a word list or to find it by brute forcing is kinda slim.

So there had to be another solution for this challenge. Let's join the journey to find it.

Step 2 - Understanding the code piece by piece

When you look at the code of the challenge you can split it into the following parts:

Part 1: Defining the users

In this part of the code a list of users with their MD5 password hashes is defined. It also initializes the $valid_user flag to false.

<?php

$users = array(
        "0:9b5c3d2b64b8f74e56edec71462bd97a" ,
        ...
);

$valid_user = false;

Part 3: Checking password against all users

This part of the code traverses the list of all registered users and checks if they match the requested login. The check is made by exploding the user id and password hash into an array and then comparing the array against the login array with the identical operator. Usage of the identical operator is the right thing todo, because all security relevant comparisons should use the identical operator === in PHP. In case of a match the user id from the cookie is written into the $uid variable and the value of 0 is added to force a conversion into an numerical data type. In addition to that the flag "$valid_user" is set to true.

<?php

foreach ($users as $user)
{
        $user = explode(":", $user);
        if ($input === $user) {
                $uid = $input[0] + 0;
                $valid_user = true;
        }
}

If you read the code above carefully you might have seen that after a valid user is detected in the comparison the code continues to compare against the other user accounts instead of stopping at this point. This is of course a bug, but in this particular case it does not lead to any exploitable defect.

Part 4: Handling (in)valid user logins

Once the comparison loop is finished the script immediately exits with an error message if no valid user could be detected. In case of a valid user however there are two cases: the user id 0 is reserved for the admin and any other user id is considered a normal user. One thing that sticks out here is that the comparison of the user id against 0 uses the equality operator == instead of the identical operator ===. This is bad coding style, because all security relevant comparisons should use the identical operator. However as we will see later the usage of the wrong operator is just another red herring.

<?php
if (!$valid_user) {
        die("not a valid user\n");
}

if ($uid == 0) {

        echo "Hello Admin How can I serve you today?\n";
        echo "SECRETS ....\n";

} else {
        echo "Welcome back user\n";
}

Step 3 - What do we know by now?

We know by now that challenge takes a cookie names 'user' as input that is an array and contains 2 elements: a user id and a password. We also know that the user 5 has the password "hund". This means we are now able to log into the challenge as user 5 easily by submitting the cookie.

Cookie: user[0]=5;user[1]=hund;

At this point we also know that the user comparison uses the identical operator === for the initial comparison and later on the equality operator == for comparing the user id. However usage of the == is just a red herring and when you look at the possible data flows of the code you will see that whenever we hit the "==" operator it already went to through the identical operator check.

And at this point many people who tried the challenge got stuck, because they did not have knowledge of a recently discovered (and fixed) problem inside PHP. However 20-30 people actually solved the challenge on their own, because they spotted a problem being mentioned in PHP's changelog that unfortunately was not marked as a security problem.

Changelog

The PHP Changelog and the NEWS file that come with every new release, often contains interesting information, because they list the problems that have been fixed often including a link to the original bug report including sometimes test cases. Unfortunately there is no guarantee that this information is complete, because sometimes people fixing bugs do not document these fixes and sometimes fixes that are documented (or not) are not recognized as security fixes. This is still a problem for companies having to support older releases and wondering what they need to backport. This is also why we check the fixes every month and offer such a feed to interested customers. However to be fair PHP.net got way better in documenting the changes when you compare this with only a few years ago.

To get back to our challenge let us have a quick look at a snippet of the Changelog of the latest release of PHP (at the time of the challenge):

Version 5.6.11

10 Jul 2015

- Core:

 - Fixed bug #69768 (escapeshell*() doesn't cater to !).
 - Fixed bug #69703 (Use __builtin_clzl on PowerPC).
 - Fixed bug #69732 (can induce segmentation fault with basic php code).
 - Fixed bug #69642 (Windows 10 reported as Windows 8).
 - Fixed bug #69551 (parse_ini_file() and parse_ini_string() segmentation fault).
 - Fixed bug #69781 (phpinfo() reports Professional Editions of Windows 7/8/8.1/10 as "Business").
 - Fixed bug #69740 (finally in generator (yield) swallows exception in iteration).
 - Fixed bug #69835 (phpinfo() does not report many Windows SKUs).
 - Fixed bug #69892 (Different arrays compare indentical due to integer key truncation).  <------ THIS SOUNDS INTERESTING
 - Fixed bug #69874 (Can't set empty additional_headers for mail()), regression from fix to bug #68776.

In the list above one line in particular sounds interesting. It says that bug #69892 has something todo with different arrays comparing identical (although they are not) due to an integer key truncation bug. This sounds scary and one has to immediately wonder why a bug in the identical compare operator like this was not marked as a security bug. However let us look at the actual bug report and the example.

Bug #69892 - Different arrays compare indentical(sic!) due to integer key truncation

The bug report comes with a very easy example of what is broken:

[2015-06-20 14:29 UTC] nikic@php.net
Description:
------------
var_dump([0 => 0] === [0x100000000 => 0]); // bool(true)

on all versions: http://3v4l.org/Sjdf8

Problem in zend_hash_compare()

The actual integer truncation problem occurs in zend_hash_compare() inside Zend/zend_hash.c, as you can see from the following code:

ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
{
        Bucket *p1, *p2 = NULL;
        int result;
        void *pData2;

        ...

        while (p1) {
                if (ordered && !p2) {
                        ...
                }
                if (ordered) {
                        if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
                                result = p1->h - p2->h;                <------------ POSSIBLE TRUNCATION
                                if (result!=0) {
                                        HASH_UNPROTECT_RECURSION(ht1);
                                        HASH_UNPROTECT_RECURSION(ht2);
                                        return result;
                                }

The problem in the code above is that numerical indices got compared by subtracting their values from each other, which are stored in the h element of the bucket data type. A difference is then detected if the result is 0 or not. Unfortunately the h element of the structure bucket is defined as unsigned long, which is usually 64bit on 64bit systems, but the result variable is only a 32bit int data type. Therefore the comparison is not only true if the values of h are identical but every time the result of the subtraction has all zero lower 32 bits. Therefore the key 0 and the key 4294967296 and many other keys are considered identical.

Step 4 - How does that help us?

Once you know about the bug in the identical operator for array comparison you will realize that it might help you solving the challenge. So remind yourself that you know the password of user 5 and that the array you need to compare against looks like this.

user[0]=5
user[1]=06e2b745f3124f7d670f78eabaa94809

Furthermore we know that the final user id is read from the element 0 of the array. We also know that we do not want this to be 5 but 0 instead. So knowing about the bug in PHP we need to make our array look like:

user[4294967296]=5
user[1]=06e2b745f3124f7d670f78eabaa94809

The result of this change is that the array comparison using the identical operator === will claim the arrays are identical, but when the value or user[0] is read it is actually unintialized and by adding a 0 to it, it becomes the user id of the admin.

Of course in the previous examples we do not have direct control over the value of user[1], because it passes through MD5 first. So the actual cookie value that we have to send to login as the admin is:

Cookie: user[4294967296]=5;user[1]=hund;

And this is the correct and expected solution to this challenge.

Training Advertisement

If this challenge was of interest to you and you speak german please check out our upcoming web security training in Cologne next month.

Stefan Esser