DEV Community: Gal

GoogleCTF 2021 | Weather - A Virtual Machine Written in Printf

Gal — Mon, 19 Jul 2021 15:03:58 +0000

I heard it's raining flags somewhere, but forgot where... Thankfully there's this weather database I can use.

Running the binary prints out a prompt asking for a city to fetch weather data for. Sadly, the flag is not "none" so I guess we should just give up and call it a day.

$ ./weather
Welcome to our global weather database!
What city are you interested in?
London
Weather for today:
Precipitation: 1337mm of rain
Wind: 5km/h W
Temperature: 10°C
Flag: none

Overview

First things first, open IDA.
We have 46 functions, half of them "unreachable" from main and all look very similar referencing the same memory and have a similar execution tree shape.

Additionally, one function (we called it configure_custon_print_functions) references all of those "unreachable" functions, passing them as a reference to register_prinf_function.

configure_custon_print_functions is called on init (before main) and by putting a breakpoint at the functions it registers we can see some of them are executed in a normal execution flow.

configure_custon_print_functions

register_prinf_function

From the GNU manual

12.13.1 Registering New Conversions

The function to register a new output conversion is register_printf_function, declared in printf.h.

Function: int register_printf_function (int spec, printf_function handler-function, printf_arginfo_function arginfo-function)

For example, to register a handler for %Y we would call register_printf_function

int y_custom_handler(FILE *stream, const struct printf_info *info, const void *const *args) {
    // here we would implement our custom formatting
}
void main(){
    printf_arginfo_function args;
    register_printf_function('Y', y_custom_handler, &args);
}

The struct print_info stores metadata about the format string, for example %52Y would set print_info->width = 52 and %52.3Y will set both width and print_info->perc = 3.

Disassembling main we can see that the last printf which is responsible for printing Flag: none is printed using a special printf function which is assigned the letter %F . To my surprise , the F handler itself calls fprintf another time, this time with a new format string %52C%s.

As most "unreachable" functions were used while registering the custom printf functions we can assume they will be called eventually by printf, for that reason we started reversing these functions. Just to make sure they are all called, we made a Frida script to trace the execution of these functions and indeed most of them were called.

a VM?

Reversing the functions we discovered most of them were almost identical, doing the same checks at the beginning, after which each handler did a different operation at the end. On top of that, the only handler that called fprintf recursively was C

Tip: Looking in HexRays decompiled c, rather than assembly helped us understanding which handler is what operation much faster.

We found that the following handlers were registered:

M assignment
S addition
O subtraction
X multiply
V divide
N modulu
L shift left
R shift right
E xor
I and
U or
C conditional recursive jump

Each of the above commands takes the printf_info metadata and deduces from it the source and destination memory regions. There are two possible memory regions: one is just a linear memory we called "stack" and the second points to the start of the format string.

'%52C%s',0
'%3.1hM%3.0lE%+1.3lM%1.4llS%3.1lM%3.2lO%-7.3C',0
'%0.4096hhM%0.255llI%1.0lM%1.8llL%0.1lU%1.0lM%1.16llL%0.1lU%1.200llM%2.1788llM%7C%-0.0C',0

.data:0000000000005080 ; char a52cS[]
.data:0000000000005080 a52cS           db '%52C%s',0
.data:0000000000005087 a31hm30le13lm14 db '%3.1hM%3.0lE%+1.3lM%1.4llS%3.1lM%3.2lO%-7.3C',0
.data:00000000000050B4 a04096hhm0255ll db '%0.4096hhM%0.255llI%1.0lM%1.8llL%0.1lU%1.0lM%1.16llL%0.1lU%1.200l'
.data:00000000000050B4                 db 'lM%2.1788llM%7C%-6144.1701736302llM%0.200hhM%0.255llI%0.37llO%020'
.data:00000000000050B4                 db '0.0C',0

C - Compare Instruction

the compare instruction is implemented in the printf custom %C handler. This instruction has four modes:
1) lower-than jump
2) greater-than jump
3) equal-zero jump
4) always jump.
If the jump is taken, fprintf is called again (which makes it recursive) with a new format string. This format string is calculated by taking printf_info->width as an offset from the original format string.

So the format string %52C%s is actually the instruction

jump 52
# do 52 stuff...
printf(%s) # the regular %s

Knowing how the different instructions are implemented we can now write a python script to convert the format string to a "toy" assembly language that will be easier to read. We ended up writing a VM able to compile format strings to code, dump the assembly and emulate the memory mapping.

Stage 1

Disassembling the format string we can see the following assembly. We start at 0, jump to 52 where the first character of our input is loaded onto the "stack". We then jump to address 7 where we loop until a counter is zero or more.

The code at address 7 is a function that takes three arguments: character, offset to decode from and length. This function will use the first argument (our inputs first character) as a key to decrypt the data at offset 200. By "chance", this is the same memory that is checked against in the last compare of block 52 and also the address where we jump in case the compare is positive.

========== 0 ==========
C.always 52
printf(%s)

# memsmoc
========== 7 ==========
(M) stack[(int) 3] = a52[stack[(int) 1]]
(E) stack[(int) 3] ^= stack[(int) 0]
(M) a52[stack[(int) 1]] = stack[(int) 3]  # decrypt fromat_string[200 + index]
(S) stack[(int) 1] += 4                   # increase 
(M) stack[(int) 3] = stack[(int) 1]
(O) stack[(int) 3] -= stack[(int) 2]      # counter -= 
(C) C.lt 7 stack[(int) 3] < 0             # while counter < 0

========== 52 ==========
stack[(int) 0] = a52[4096]       # user input
stack[(int) 0] &= 255            # first letter of user input

stack[(int) 1] = stack[(int) 0]  # copy the first letter
stack[(int) 1] <<= 8
stack[(int) 0] |= stack[(int) 1]

stack[(int) 1] = stack[(int) 0]
stack[(int) 1] <<= 16
stack[(int) 0] |= stack[(int) 1]  # c

stack[(int) 1] = 200           # func_7(c, 200, 1788)
stack[(int) 2] = 1788
C.always 7

at52[6144] = 1701736302         # "none"
stack[(int) 0] = a52[200]       # get first char from format_string[200]
stack[(int) 0] &= 255
stack[(int) 0] -= 37            # fromat_string[200] == '%'
C.eq 200 stack[(int) 0] == 0    # check if decrypted stage two successfully

As this function takes into account only the first character we can try all ascii characters until one of them proves to be the correct answer (one where the jump of the last compare is taken). After trying some inputs we found that 'T' was a valid input 🎊

Stage 2

Executing the VM with the input of 'T' the conditional jump is taken and the new code at 200 is executed flawlessly. We can now dump it out to human readable assembly

the main code for stage 2

========== 200 ==========
stack[(int) 4] = 5000
stack[(int) 0] = 13200
C.always 337                  # this loops 400~ times

stack[(int) 0] = 0
C.always 500                  # loop over input and mangle it

C.always 1262                 # validate mangled input using xor

C.eq 653 stack[(int) 0] == 0  # check if output of 1262 is zero
                              # if so, 653 decrypts winning print command (using original input as key)

Writing the same code in c would result in

int func_200() {
    func_337(5000, 13200);

    mangle_input();               // func_500;
    if (validate_input() == 0) {  // func_1262
        // print_flag is a calculation over input so one 
        // cannot just execute print_flag without the correct input
        print_flag();             // func_653
    }
}

Mangling Input

Nothing smart here, just go line by line and reverse the assembly to python.
It took me time to realize the key to this function is it's recursive manner. Basically, it decreases some input number by different rules, counting how much iterations it takes until this number turns to zero, returning the number of iterations in stack[0].

Our result "decompiled code" looks something like this

# 500:
def mangle_loop(input_s):
    output = [0 for x in range(len(input_s))]

    for i in range(len(input_s)):
        c = input_s[i]
        c = ord(c) ^ (stage_two_main[i * 2] & 0xff)
        c += do_470(i + 1) + 1
        c = c & 0xff
        output[i] = c

    return output


def do_470(var_0):
    var_1 = var_0 - 1
    var_1 -= 1

    if var_1 == 0: # 397
        return 0

    if var_1 < 0:
        return var_0 - 2

    # var_1 > 0 :428
    var_1 = var_0 % 2

    if var_1 == 0: # :405
        var_0 = var_0 // 2
    if var_1 > 0:
        var_0 *= 3
        var_0 += 1

    var_0 = do_470(var_0)
    return var_0 + 1

Reversing the Input Validation

We know how to transform our input in the exact same way function 500 does.
We know that the result of function 1262 is stored in stack[0]
The last condition of at the end of function 200 is the last check executed and it looks like we are failing it. Any input we had manually tried did not match the condition.

All of the above convinced us that if 1262 would return 0, our jump to 653 would print out the flag.

Summing up, 1262 is a validation function that:

takes as an input the mangled bytes from our input string
returns the result on stack[0] where 0 means the validation was successful

The begginning of code at 1262

========== 1262 ==========
stack[(int) 0] = 0                     # result = 0

stack[(int) 1] = 0
stack[(int) 1] += 4500                 # mangled user input offset
stack[(int) 1] = a52[stack[(int) 1]]   # var1 = mangled[0]
stack[(int) 2] = 0
stack[(int) 2] += 1374542625
stack[(int) 2] += 1686915720
stack[(int) 2] += 1129686860           # var2 = (int) (1374542625 + 1686915720 + 1129686860)
stack[(int) 1] ^= stack[(int) 2]       
stack[(int) 0] |= stack[(int) 1]       # result |= var1 ^ var2

This code snippet is repeated for every 4 characters from 0 to 24, each time with a different value in var2. We know the first letter is 'T' so breaking the first 4 letters should be possible using simple brute force on the remaining 3 letters. We did just that and got the first 4 letters: "TheN" 🥳 .

Continuing from here we should have used z3 to create constraints and solve this efficiently but we were lazy, so instead we just continued brute forcing 4 letters a time. This took around 3 hours using 1 cpu core in python.

The brute forcing code is simple: try any combination of 4 ascii letters, send them to mangle_function and then xor the result with the appropriate value (from 1262). A valid result is one where mangle(input[i:i+4])) ^ magic == 0

pseudo brute force code

import itertools

def brute():
    start = '0'
    end = 'z'
    magic = ctypes.c_int(1374542625 + 1686915720 + 1129686860).value

    for i in itertools.product(range(ord(start), ord(end) + 1), repeat=4):
        s = ''.join([chr(x) for x in i])
        out_mem = mangle_input(s)
        result = arr_to_int(out_mem)

        if result ^ magic == 0:
            print('found input!', s)

Flag: CTF{curs3d_r3curs1ve_pr1ntf}

The full vm, brute-force and annotated assembly can be found at:

bitterbit / ctf

CTF Writeups

https://github.com/bitterbit/ctf/blob/master/google-ctf-qual-2021/weather

How Fuzzing with QEMU (and AFL) Works

Gal — Sat, 05 Jun 2021 13:03:18 +0000

Whats a Fuzzer?

A fuzzer now-days is a automated testing tool to find security bugs. It does so by generating many inputs to be executed until on of them crashes the target program. In other words the objective is to crash a program, but how can we guide the fuzzer in the right direction?

AFL added to the objective a notion of code coverage: Any input that reaches an area in the code that was unreachable before is interesting. Even if it did not crash the program we can mutate that input to get even more coverage, we call this feedback. Over the past years coverage had proved to be a great feedback mechanism, but collecting it was not simple if one did not own the source code of the target binary.

Enter QEMU Fuzzing

AFL originally used compile time instrumentation to insert assembly instructions at the beginning of each basic block. Basic Block is a group of assembly instructions that are always executed one after the other. When executed, these snippets would write a byte to a shared memory area where the fuzzer can observe and determine which basic blocks had been reached.

This method works well if you have the source code and can compile it with your custom instrumentation, but what if you are fuzzing a closed source binary? One cool example of fuzzing closed source binaries would be: Effective Fuzzing Qmage.

QEMU to the rescue. QEMU is an emulator that can emulate many cpu architectures, for example it can run Android (arm) on your PC (x86) or run Windows on your iPad UTM.

By patching QEMU, TriforceAFL and AFL++ managed to get coverage feedback out of any binary that QEMU can run. How cool is that?!

So How does it Work?

QEMU user-mode is a "sub" tool of QEMU that allows emulating just the userspace (in contrast to the normal mode where both the user-mode and the kernel are emulated). This is done by forwarding any syscalls from the target program to the host machine. The main benefits are improved performance and less complex environment, but it sacrifices on the portability. AFL++ fork of QEMU uses this mechanism while adding coverage tracking and optional performance optimizations.

Example of running arm linux binaries on a x86 host

$ /AFLplusplus/afl-qemu-trace /fuzz/bin/harness <<< aaaaaaaaaaaaaaaaaa
[harness] starting main. main at: 0x550000b848
[harness] should_backtrace. argc=1
[harness] input:
  0000  61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61  aaaaaaaaaaaaaaaa

Getting the Coverage

QEMU writes the coverage feedback data to shared memory, this way both QEMU and the fuzzer can write and inspect the coverage data. The fuzzer is responsible for allocating the shared memory and cleaning it after each run, while is responsible for filling the memory with the coverage data. When the fuzzer starts QEMU, it passes the shared memory file descriptor to QEMU using the __AFL_SHM_ID environment variable and maps the memory to its own process using shmat. Then whenever the QEMU Virtual Machine executes a basic block, it marks the block as reached by writing to this shared memory. This is implemented by the INC_AFL_AREA macro.

After QEMU exits, the fuzzer can look at the shared memory for any bytes that are different from zero. The offset from the start of the map is the ID of the visited basic-block and the more bytes that are different from zero, the more basic blocks our target has hit.

A redacted version of code from afl++ qemu related to the shared memory

// qemuafl/imported/config.h
#define SHM_ENV_VAR "__AFL_SHM_ID"

// accel/tcg/cpu-exec.c
void afl_setup(void) {
  char *id_str = getenv(SHM_ENV_VAR);
  if (id_str) {
    shm_id = atoi(id_str);
    afl_area_ptr = shmat(shm_id, NULL, 0);
    if (afl_area_ptr == (void *)-1) exit(1);
  }
}

// accel/tcg/translate-all.c
void HELPER(afl_maybe_log)(target_ulong cur_loc) {
  register uintptr_t afl_idx = cur_loc ^ afl_prev_loc;
  INC_AFL_AREA(afl_idx);
  afl_prev_loc = cur_loc >> 1;
}

// qemuafl/common.h
#define INC_AFL_AREA(loc) afl_area_ptr[loc]++

Sample rust code for running QEMU and getting coverage from it

fn main() {
  let shm_id = create_shmem();
  env::set_var("__AFL_SHM_ID", format!("{}", shm_id));
  run_target_in_qemu();

  let afl_area_ptr = get_shmem(shm_id);
  let mut cov: Vec<u8> = Vec::new();

  for i in 0..0xffff {
    let value;
    unsafe {
      value = *afl_area_ptr.add(i);
    }
    if value != 0 {
      println!("coverage at cov[{}] = {}", i, value);
    }
  }
  close_shmem(shm_id);
}

Full example here https://github.com/bitterbit/fuzzer-qemu/blob/fb9170ba1f2723592844ee368fcc33ef25b04f39/src/src/main.rs

AFL ForkServer

Jann Horn introduced the idea of a fork-server to AFL. In the fork-server mode, instead of running the target from the beginning for each test case, we let the code arrive at a key point where we fork. Then each time the QEMU exits the father process forks again. This can be thought of a cheap snapshot mechanism.

In this setup we have a fuzzer, qemu-father and qemu-child, the fuzzer and the qemu-father communicate using pipes while the child is re-spawned after each test case. Each time the child is done the father can fork again to create another child. This helps avoid running the "setup" code each time we want to run our target, which helps improve performance.

In practice the communication between the fuzzer and the qemu-father is made out of two pipes, both are created by the fuzzer and given constant file descriptor ids using dup2 so the qemu-father can easily find and open them. The control pipe is used by the fuzzer to control the qemu-father and the the Status pipe is used by the qemu-father to update the fuzzer that he is alive.

Name	Owner	R/W	ID
CTL (Control)	qemu	Read	198
CTL (Control)	fuzzer	Write	n/a
ST (Status)	qemu	Write	199
ST (Status)	fuzzer	Read	n/a

While cracking at the fork-server mode, one might ask why not just "rewind" the Virtual Machine back to the starting point instead of forking again? This is exactly what I was thinking and haply there is a special mode that does exactly that: Persistent Mode.

Persistent Mode?

Persistent mode can help improve the performance of your fuzzer even more. It does so by reducing the amount of "boilerplate" code that has to be run in order to run our code, much like the fork-server mechanism but to a higher extreme. So how does it work?

Every fuzzer needs to run a target multiple times, each time with a different input and record the coverage.
Instead of re-executing QEMU for each test case, we can select a key/main function which we will run in a loop and instead of closing the VM each time the target exits, we jump right back to this main function. In other words whenever the targets main function returns, instead of returning to the caller we just jump again to the beginning of our main function.

This introduces new problems:
1) How can we know what coverage belongs to which input?
2) If we are just running the same code again, why would the input be different?

Communication between Child and Father

AFL uses the two communication pipes just like in the fork server mode. The fuzzer creates new pipes before starting the QEMU process and using dup2 makes sure that each pipe has it's predefined file descriptor so QEMU can know to use them.

Our setup looks something like this

 ________             _____________             ____________
| fuzzer | ---(1)--- | QEMU father | ---(2)--- | QEMU child |
 --------             -------------             ------------

1) communicate using status and control pipes
2) communicate using STOP and CONT signals

We have the fuzzer communicating with the QEMU father using the control and status pipes. Previously using the fork-server mode a new child was created for each test case, making it easy for the father to know the status and passing the updates up to the fuzzer using the pipes.

In the persistent mode, the child does not quit so we need another mechanism to let the father know what the status of the child. This is done with STOP and CONT unix signals.

For each instruction emulated by QEMU (by the disas_a64_insn on arm64) the current program counter (pc) is compared to the address of our main function, If they are equal we prepare the VM for a new test case and wait for the father to signal us to continue.

This function trace done each time the child resets itself

disas_a64_insn checks for pc_curr == afl_persistent_addr
afl_persistent_loop is called and calls
afl_persistent_iter.
After all this is done, a SIGSTOP is raised and the execution is paused until the father sends back a SIGCONT.

To sum it up, when the child is done with a test case it raises a STOP and then when the father is done preparing the next test case it sends back a CONT signal to the child. The fathers implementation can be found inside afl_forkserver.

/* Special handling for persistent mode: if the child is alive but
    currently stopped, simply restart it with SIGCONT. */

kill(child_pid, SIGCONT);
child_stopped = 0;

In persistent mode, the father is responsible for bridging between the fuzzer and the child QEMU process. Below is sample code to run a fuzzer with QEMU in persistent mode.

Sample code to run QEMU in persistent mode

fn main() {
  let control_pipe = Pipe::new("control_pipe".to_owned());
  let status_pipe = Pipe::new("status_pipe".to_owned());

  control_pipe.dup_read(FORKSRV_FD);
  status_pipe.dup_write(FORKSRV_FD + 1);

  let child = Command::new("./qemuafl")
  .arg("./harness")
  .arg("./input_file")
  .env("AFL_QEMU_PERSISTENT_ADDR", "<address-of-main>")
  //.env...
  .spawn().unwrap();

  status_pipe.read_i32();
  info!("[+] forkserver is alive!");

  loop {
    control_pipe.write_i32(0);  
    debug!("[+] sent alive signal to child");

    let child_pid = status_pipe.read_i32();
    assert!(child_pid >= 0);
    debug!("[+] child pid {}", child_pid);

    let status = status_pipe.read_i32();
    debug!("[+] status={}", status);

    // each time we reach this point we know a testcase was 
    // fully executed. We may want to read the coverage shared mem
    // and write a new file to the input file.
    prepare_new_testcase();
  }
}

I hope you found this useful! my twitter DMs are open at @galtashma .

Sources: