id: 23
lang: en
date: 2014-06-30
title: NdH2k14 choucroute CTF write up
category: CTF, Security
licence0: This article is released under the *CC BY-SA* licence.
licence1: Illustrations of the CBC mode in the *public domain*.

*[CTF]: Capture the flag
*[ECB]: Electronic codebook
*[CBC]: Cipher feedback
*[AES]: Advanced Encryption Standard
*[SQL]: Structured Query Language
*[JSON]: JavaScript Object Notation
*[IV]: Initialisation Vector


Overview
========

Last weekend, I was at the [Nuit du Hack](http://www.nuitduhack.com/), 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][DL code and exploit].

[DL code and exploit]: /media/ndh2k14_choucroute_exploit.zip


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
    <?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
    <?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
    <?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:

 1. Decrypt the cookie with RIJNDAEL (AES) in CBC mode;
 2. 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:

 - [ECB: you're doing it wrong](https://r.rogdham.net/16);
 - [iCTF secretvault write up](https://r.rogdham.net/22).

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][WP-CBC]).

![CBC: encryption](/media/cbc_encryption.png)

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](/media/cbc_decryption.png)


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).

[WP-CBC]: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Cipher-block_chaining_.28CBC.29


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
    <?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:

 1. 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;
 2. 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](/media/cbc_decryption.png "CBC decryption again for your
convinience")

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](/media/ndh2k14_choucroute.png)


Conclusion
==========

A working exploit together with the `index.php~` file are [available for
download][DL code and exploit]. 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!