NdH2k14 choucroute CTF write up

Jun 30 2014

Overview

Last weekend, I was at the Nuit du Hack, which is a security event near Disneyland Paris mixing conferences, workshops, and much more, including some wargames and CTF.

This article is about the “choucroute” challenge on the public CTF. Even though no team managed to solve it in due time, I still worked after the deadline was over and solved it the next day (actually, a few hours of sleep later).

The entry point of the challenge was a webpage where you could basically buy some sauerkraut online, using a coupon if you have some. The flag was supposed to appear after the payment processing, but unfortunately, this very service seemed to be on strike, leaving us with nothing to eat and no flag to score.

As for many web challenges, you are looking for the regular vulnerabilities: SQL injection, upload forms and so on. Soon, you will figure out that an old version of the index.php file is available at the address /index.php~.

The index.php~ together with the exploit described in this article are available for download.

Code analysis

The PHP file has all the logic inside, except for the value of a secret key and what happens during the payment step, or if that step is not needed. Those points were replaced by TODO comments, leaving us to believe that we only need to reach that step with a non-positive $to_pay variable.

Some coupons are hard-coded in the source code, but proper sanitisation ensures that the amount to pay is always strictly positive.

More work is obviously needed to solve the challenge, but before anything else, let us patch the PHP file so that we know when we would have got the flag, by adding some echo statements:

<?php
if ($to_pay > 0) {
    echo "\n\n<p>HANDLE PAYMENT</p>\n\n";
} else {
    echo "\n\n<p>SEND CHOUCROUTE</p>\n\n";
}?>

To reach this point, a POST request has to been made, with a special cookie:

<?php } elseif (isset($_POST['buy'])) {
    $values = decode_cookie($_COOKIE['bucket']);
    if ((! isset($values['to_pay'])) || (! isset($values['security_check'])) || (! isset($values['quantity'])))
        die('<script type="text/javascript">window.location.href="index.php?go";</script>');

    $to_pay = $values['to_pay'];
    $quantity = $values['quantity'];
    if (hash('md5', $quantity . '|' .  $to_pay) !== $values['security_check'])
        die('<script type="text/javascript">window.location.href="index.php?go";</script>');
    // proceed
?>

In fact, everything comes to the decode_cookie function, which is reproduced below:

<?php
function decode_cookie($cookie)
{
    global $supa_secret_key;

    $cookie = base64_decode($cookie);
    $iv = substr($cookie, 0, 16);
    $encrypted = substr($cookie, 16);

    if ((strlen($iv) < 16) || (strlen($encrypted) % 16 != 0))
    {
        return array(
            'email' => 'e-mail',
            'coupon' => 'coupon',
            'invalid_coupon' => false,
            'quantity' => 1
        );
    }

    $decrypted = mcrypt_decrypt(MCRYPT_RIJNDAEL_128, $supa_secret_key, $encrypted, MCRYPT_MODE_CBC, $iv);
    if (strpos($decrypted, "\x00") !== FALSE)
        $decrypted = substr($decrypted, 0, strpos($decrypted, "\x00"));

    $values =  json_decode($decrypted, true);
    if (json_last_error() !== JSON_ERROR_NONE)
    {
        return array(
            'email' => 'e-mail',
            'coupon' => 'coupon',
            'invalid_coupon' => false,
            'quantity' => 1
        );
    }
    return $values;
}
?>

As you can see, the main two actions implemented by this fonctions are:

Decrypt the cookie with RIJNDAEL (AES) in CBC mode;
JSON-decode that value and returns it.

Cipher feedback mode

I have written about an other block cipher mode, ECB in several posts in the past:

In a nutshell, ECB is a very weak block cipher mode. However, the present challenge uses CBC, which is quite stronger. Indeed, there is a feedback added: the ciphertext of the previous block is used for the computation of the next block. As usual, a picture makes things easier to understand (if you prefer, feel free to read the Wikipedia article).

CBC: encryption

As you can see, an initialisation vector (IV) is used to replace the “previous ciphertext” on the very first block.

As far as decryption is concerned, just reverse all the steps:

CBC: decryption

For our attack, we control all the cipher blocks as well as the initialisation vector. We can think of two attacks right away:

Altering the IV allows us to fully control the first 16 bytes of the JSON data;
We can fully control any plaintext block in the chain by changing the previous ciphertext block, but this will introduce a plaintext block full of garbage as a result.

However, both ideas are not applicable here: if we take a valid cookie and try to modify it, we need to alter the values of no less than two keys: to_pay and security_check. The problem is that the last one would be at the very end of the cookie, and is 32 bytes long (the MD5 value is hex-encoded). In other words, we need to be able to choose more than 32 consecutive bytes (we have to get the JSON key right as well as the JSON syntax correct).

Decryption oracle

We are all here to do what we are all here to do.
— The Oracle, Matrix Reloaded, 2003

Go and see the oracle

A closer look at the decode_cookie function reveals some interesting points:

Before the JSON-decoding, the value is cut just before the first null byte;
If the JSON-decoding fails, we have some default values being returned.

Now, look at the first step of the website:

<?php if (isset($_GET['go'])) {
    $values = decode_cookie($_COOKIE['bucket']);
    ?>
    <form name="wurst" method=post action="index.php">
    <!-- skip -->
    <input type="text" name="email" value="<?php
        if (isset($values['email'])) {
            echo htmlentities($values['email']);
        }
    ?>" placeholder="e-mail">
    <!-- skip -->
<?php } ?>

As you can see, the value of the email input can either:

come from the email field as returned by the decode_cookie function;
be left empty if the email key is not present in this return value.

In other words, we have access to an oracle which can tell us if the decrypted cookie is a valid JSON value (in which case, the email value in the input field is either empty or comes from the JSON output) or not (and we receive the default value, e-mail). This is a powerful oracle, which will allow us to decrypt any ciphertext block.

Getting the first byte

Indeed, to decrypt a ciphered block, let's send it in the cookie together with an IV of our choice. We will recover the plaintext block one byte at a time.

For the first byte, we want to have an empty value for JSON to decode, which means that the first decrypted byte will be the null byte (remember, the code will cut the decrypted string right before the first null byte). To do so is not too difficult:

We iterate over all the 256 possible values for the first byte of the IV;
We choose the other 15 bytes to be \x00
Each time, we ask the oracle if the decrypted plaintext is a valid JSON value.

Two cases can occur:

The first decrypted byte is \x00, and so the decrypted value is cut to the empty string before being JSON-decrypted, and we have found the first byte of the IV we were looking for;
The first decrypted byte is not \x00, but the decrypted value (once cut after the first \x00) is still valid JSON value.

The second case could occur for example if the first two decrypted bytes are 0\x00 (a zero followed by the null byte). Indeed, it will become the string 0 with is a valid JSON value. This is quite a problem, since we do not know in which case we are. However, it is enough to check all the positive matches by doing the same process again, but this time choosing the last 15 bytes of the IV to be \xff. There will be only one remaining solution, which gives us the first byte of the output from the cipher block.

Getting more bytes

We take a similar approach to get the second byte. Everything is about choosing the right IV for the job. This time, we are aiming to find a plaintext starting with the following two bytes: 0\x00. Again, we will take all possible values for the second byte of the IV, and all \x00 for the 14 rightmost bytes (and \xff for the double check).

All is left to choose is the very first byte of the IV. Looking back at the illustration of the CBC decryption, there is nothing but a simple XOR between the output of the block cipher and the returned plaintext. Moreover, we have already found in the previous step the first byte output from the block cipher. As a result, it is enough to XOR the first byte from the previous IV with the byte we aim to obtain (i.e. 0).

This allows us to get the next 14 bytes of the plaintext, by looking for the strings 0\x00, 00\x00, …, 0000000000000\x00.

The final byte

The final byte is a little bit more tricky. Indeed, if we look for the plaintext made of 15 zeros followed by the null byte, we will have many valid JSON candidates. Indeed, strings such as 0000000000000004 are valid JSON values as well. The reason why this was not happening before is because of the cut at the first null byte. This time, we can not use this trick because we can not control the byte 17, as there are only 16 bytes in a block.

Instead, we will look at the string { }, for which only the character } is a valid ending as long as JSON is concerned.

Exploit

At this point, we have everything we need, since we are able to decrypt any block of ciphertext. The only thing left to do is to choose the JSON value we want to have, and create the corresponding value to store in our cookie.

I chose the following JSON value: {"auth": "Rogdham", "quantity": "1", "to_pay": 0, "security_check": "3baf8cec88b311ae39cfdace853cee96"} (without the spaces), but there are several possible choices here. Just make sure that the MD5 matches the value you choose for the quantity and to_pay fields, and choose a to_pay value which is no more that 0 (this is the whole point of the exploit!). Here, I have chosen a JSON value which is exactly 6 blocks long (using a dummy auth key-value as padding), which makes our life easier.

CBC: decryption

So, first, we choose the last block of ciphertext as we wish. Let's call it C5. Thanks to the oracle, we are able to get the corresponding plaintext M5, with M5=decrypt(C5). Now, before we have the corresponding plaintext block P5 as the output of the CBC mode, M5 is XORed with C4. We don't have C4, but we know what we want for P5 (cfdace853cee96"}). Hence, we deduce C4=XOR(M5,P5) or directly C4=XOR(decrypt(C5),P5).

Likewise, we recover C3=XOR(decrypt(C4),P4), …, C0=XOR(decrypt(C1),P1) and finally IV=XOR(decrypt(C0),P0).

At that point, we concatenate IV, C0, …, C5, which gives us the value of the cookie to use. If no mistake were made in the process, this gives us the flag of the challenge as shown below (since I solved the challenge after the deadline, it gives a choucroute-related message instead).

Exploit in action

Conclusion

A working exploit together with the index.php~ file are available for download. Feel free to try it, but keep in mind that it has been written half asleep, so do not be too hard on it.

Even though this challenge has not been solved during the CTF competition, it is pretty neat indeed. Many thanks to its creator as well as the NdH team in general for such a cool event!

One final thought: I love the fact that we use a decryption oracle to encrypt some data!