Hilltop CTF 2020 - Tornado

Given a website that seems like a file-sharing utility.

Judging by the web interface, the goal of this challenge is supposed to open the Flag folder. But if we tried to click on that folder, the web asks for an email address and a MagicHash.

Notice that there’s also a link to request the MagicHash. Upon clicking the link, we were redirected to http://192.81.210.234:10003/request.php.

We need to submit an email address to get the MagicHash. Submitting a random or unrecognized email will make the server responded with an error message, but that also gave us hint about the correct email; admin@tornado.corp.

After sending the request with admin@tornado.corp email, the web told us that the MagicHash has been sent to the email.

Since we don’t have access to that email, we need to think of other ways to get the MagicHash. More information can be found by examining the leaked source code of the website.

The challenge provided us three source code files: functions.php, include.php, and requests.php.

Below is a detailed examination of what we can find from each file.

Examining Request.php

This file is the source code of the page where we request a MagicHash. From there, we know that there is no email being sent at all. The input was sanitized using mysqli_real_escape_string() function, so it’s unlikely that this challenge is about SQL Injection.

Also, a function named generateMagicHashToken() is called. And if the supplied email can be found in the database, both the email and the generated token will be stored in a table named magic_hashes.

Examining Functions.php

This file contains some functions that are used to run the website. There are four functions:

throwSeed() In the leaked source code, this function is redacted. We can guess that this function is supposed to generate some value for the random’s seed.
```
 function throwSeed() {
     // REDACTED. This is some sophisticated algorithm.
 }
```
generateMagicHashToken() This function calls mt_rand() function, which is used to generate random value via the Mersenne Twister Random Number Generator, five times. After that, this function will construct a string token out of those five random values, separated by - token, and finally generates a SHA1 string with value from another mt_rand() call.
```
 function generateMagicHashToken() {
     for($i=0; $i < 5; $i++) {
         $token[$i] = mt_rand();
     }
     $token = base64_encode(implode("-", $token) . "-" . sha1(mt_rand()));
     return $token;
 }
```
Simply put, this is the structure of the generated token:
```
 mt_rand() + "-" + mt_rand() + "-" + mt_rand() + "-" + mt_rand() + "-" + mt_rand() + "-" + sha1(mt_rand())
```
createSession() Judging by the name, this function is used to generate a token for a session or cookie. The website uses a cookie called secure-session, with base64-encoded string as the value.

The decoded value of the cookie would be something like this:
```
 0dc397a9409687ba6e70f4dfe9f334a9fdbc81f7102912384.757827708d738b098366f3731261a9d6fbea3eb68a3f749ec
```
And this is the structure of the generated token:
```
 sha1(<implode of 13 mt_rand() values>) + mt_rand() + "." + mt_rand() + sha1(<implode of 226 mt_rand() values>)
```
So from the decoded value of the cookie, we would know that:
1. The 14th mt_rand() call will generate 102912384, since this number appears after 40-characters long of SHA1 string and right before the dot (.)
2. The 227th mt_rand() call will generate 757827708, since this value appears right after the dot (.) and before the 40-characters long of SHA1 string.
displayMessage() This is a helper function that prints error or success messages. This has nothing to do with the challenge, only for aesthetic reasons.

Examining Include.php

This file confirms our guesses about some functions in functions.php. throwSeed() is used to supply a seed value to mt_srand() value. And secure-session cookie’s value is coming from createSession() function.

This challenge is based on this research from Ambionics Security. The goal is to predict the seed that was supplied to mt_srand() in include.php file, to generate the MagicHash token of our own. It’s a good thing to read and even understand how the attack work; but for the sake of simplicity, I will summarize it.

Here are the steps:

Obtain a value generated by a mt_rand() call, let’s say it’s value x.
Obtain another value generated by the 227th mt_rand() call after the x. Let’s say it’s value y.
Get the scrambled state from these values.
XOR those states and deduce the initial state 228.
Get the seed by working back from s228 to s0, which are

If you are confused, the crystal clear explanation can be found on the link when I refer to the research above, or here. They also provide the POC script of the attack that you can use. To use the script, we simply need two mt_rand() values (the x and y), and also we need to know how many times the mt_rand() has been called before we get the x value. The answer is 14; because the only visible mt_rand() result that we have is the 14th and the 227th (unless you can completely break SHA1).

And for that we implemented a Python script to get the cookie from the website, extract the x and y values, and guess the seed from the two values (adapted from Charles Fol (@cfreal_)’s art of work):

#!/usr/bin/env python3.7

import requests
import base64
import os
# from urllib import unquote # for python2
from urllib.parse import unquote # for python3
from subprocess import Popen, PIPE

"""
Source code adopted from Charles Fol (@cfreal_) (https://www.ambionics.io/blog/php-mt-rand-prediction)
"""

#!/usr/bin/env python3.7
# Charles Fol
# @cfreal_
# 2020-01-04 (originally la long time ago ~ 2010)
# Breaking mt_rand() with two output values and no bruteforce.
#

"""
R = final rand value
S = merged state value
s = original state value
"""

import random
import sys

N = 624
M = 397

MAX = 0xffffffff
MOD = MAX + 1


# STATE_MULT * STATE_MULT_INV = 1 (mod MOD)
STATE_MULT = 1812433253
STATE_MULT_INV = 2520285293

MT_RAND_MT19937 = 1
MT_RAND_PHP = 0


def php_mt_initialize(seed):
    """Creates the initial state array from a seed.
    """
    state = [None] * N
    state[0] = seed & 0xffffffff;
    for i in range(1, N):
        r = state[i-1]
        state[i] = ( STATE_MULT * ( r ^ (r >> 30) ) + i ) & MAX
    return state


def undo_php_mt_initialize(s, p):
    """From an initial state value `s` at position `p`, find out seed.
    """
    # We have:
    # state[i] = (1812433253U * ( state[i-1] ^ (state[i-1] >> 30) + i )) % 100000000
    # and:
    # (2520285293 * 1812433253) % 100000000 = 1 (Modular mult. inverse)
    # => 2520285293 * (state[i] - i) = ( state[i-1] ^ (state[i-1] >> 30) ) (mod 100000000)
    for i in range(p, 0, -1):
        s = _undo_php_mt_initialize(s, i)
    return s


def _undo_php_mt_initialize(s, i):
    s = (STATE_MULT_INV * (s - i)) & MAX
    return s ^ s >> 30


def php_mt_rand(s1):
    """Converts a merged state value `s1` into a random value, then sent to the
    user.
    """
    s1 ^= (s1 >> 11)
    s1 ^= (s1 <<  7) & 0x9d2c5680
    s1 ^= (s1 << 15) & 0xefc60000
    s1 ^= (s1 >> 18)
    return s1


def undo_php_mt_rand(s1):
    """Retrieves the merged state value from the value sent to the user.
    """
    s1 ^= (s1 >> 18)
    s1 ^= (s1 << 15) & 0xefc60000
    
    s1 = undo_lshift_xor_mask(s1, 7, 0x9d2c5680)
    
    s1 ^= s1 >> 11
    s1 ^= s1 >> 22
    
    return s1

def undo_lshift_xor_mask(v, shift, mask):
    """r s.t. v = r ^ ((r << shift) & mask)
    """
    for i in range(shift, 32, shift):
        v ^= (bits(v, i - shift, shift) & bits(mask, i, shift)) << i
    return v

def bits(v, start, size):
    return lobits(v >> start, size)


def lobits(v, b):
    return v & ((1 << b) - 1)


def bit(v, b):
    return v & (1 << b)


def bv(v, b):
    return bit(v, b) >> b


def php_mt_reload(state, flavour):
    s = state
    for i in range(0, N - M):
        s[i] = _twist_php(s[i+M], s[i], s[i+1], flavour)
    for i in range(N - M, N - 1):
        s[i] = _twist_php(s[i+M-N], s[i], s[i+1], flavour)


def _twist_php(m, u, v, flavour):
    """Emulates the `twist` and `twist_php` #defines.
    """
    mask = 0x9908b0df if (u if flavour == MT_RAND_PHP else v) & 1 else 0
    return m ^ (((u & 0x80000000) | (v & 0x7FFFFFFF)) >> 1) ^ mask


def undo_php_mt_reload(S000, S227, offset, flavour):
    #define twist_php(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
    # m S000
    # u S227
    # v S228
    X = S000 ^ S227
    
    # This means the mask was applied, and as such that S227's LSB is 1
    s22X_0 = bv(X, 31)
    # remove mask if present
    if s22X_0:
        X ^= 0x9908b0df

    # Another easy guess
    s227_31 = bv(X, 30)
    # remove bit if present
    if s227_31:
        X ^= 1 << 30

    # We're missing bit 0 and bit 31 here, so we have to try every possibility
    s228_1_30 = (X << 1)
    for s228_0 in range(2):
        for s228_31 in range(2):
            if flavour == MT_RAND_MT19937 and s22X_0 != s228_0:
                continue
            s228 = s228_0 | s228_31 << 31 | s228_1_30

            # Check if the results are consistent with the known bits of s227
            s227 = _undo_php_mt_initialize(s228, 228 + offset)
            if flavour == MT_RAND_PHP and bv(s227, 0) != s22X_0:
                continue
            if bv(s227, 31) != s227_31:
                continue
            
            # Check if the guessed seed yields S000 as its first scrambled state
            rand = undo_php_mt_initialize(s228, 228 + offset)
            state = php_mt_initialize(rand)
            php_mt_reload(state, flavour)
            
            if not (S000 == state[offset]):
                continue
            
            return rand
    return None

def solve(_R000, _R227, offset, flavour):
    # Both were >> 1, so the leftmost byte is unknown
    _R000 <<= 1
    _R227 <<= 1
    
    for R000_0 in range(2):
        for R227_0 in range(2):
            R000 = _R000 | R000_0
            R227 = _R227 | R227_0
            S000 = undo_php_mt_rand(R000)
            S227 = undo_php_mt_rand(R227)
            seed = undo_php_mt_reload(S000, S227, offset, flavour)
            if seed:
                return seed

TARGET = "http://192.81.210.234:10003/"

req = requests.Session()

def getSample():
    res = req.get(TARGET)
    cookies = req.cookies.get_dict()
    token = unquote(cookies['secure-session'])
    decoded = base64.b64decode(token).decode()
    key, backup = decoded.split('.')
    shakey, salt = key[:40], key[40:]
    backup_salt, shabackup = backup[:len(backup) - 40], backup[len(backup[:len(backup) - 40]):]
    return (salt, backup_salt)

first, second = getSample()
print(first, second)
guessed_seed = solve(int(first), int(second), 13, 1)
print("Guessed Seed: %s" % guessed_seed) # we guessed the seed!

After we get the seed, we can recreate the MagicHash of our own. We just need to re-run everything that the web does, given the fact that we have some of the source code. Here’s the PHP script to do that, adapted from the given source code:

#!/usr/bin/env php
<?php

mt_srand((int)$argv[1]); # get seed from argv

function createSession() {
    for($i=0; $i < 13; $i++) $key[$i] = mt_rand();
    $salt = mt_rand(); # 1st printed value
    for($i=0; $i < 226; $i++) $backup[$i] = mt_rand();
    $backup_salt = mt_rand(); #2nd printed value
    $token = base64_encode(sha1(implode("", $key)) . $salt . "." . $backup_salt . sha1(implode("", $backup)));
    return $token;
}

function generateMagicHashToken() {
    for($i=0; $i < 5; $i++) $token[$i] = mt_rand();
    $token = base64_encode(implode("-", $token) . "-" . sha1(mt_rand()));
    return $token;
}
createSession(); # emulate calling mt_rand() to create session.
$token = generateMagicHashToken();
echo $token;

Just remember that the createSession() function is always called first before the web generates the MagicHash token (calling generateMagicHashToken()). If you don’t call the createSession() before generating the MagicHash, the token might be invalid since you’ll lack 242 mt_rand() calls before generating the token.

Here’s my MagicHash token guessed by the PHP script:

After that, if you haven’t, request a MagicHash from the web.

And use the guessed MagicHash to unlock the Flag directory.

And there’s the flag.

But, once again, the value in the comment column is a base64-encoded string. Decode it and you shall get the flag.

The Flag

Flag is HilltopCTF{Pl0tTw1st:n0t-so-Rand00m-3h}