ACS 2023: expr

Expression

TL;DR

Multi-threaded flag checker designed to thwart Angr's symbolic execution. Subroutine functions can be exported via Headless Ghidra and flattened by converting it to sequential execution.

Challenge Overview

Expression (expr) is a simple flag checker that verifies if our user input matches the flag.

Taking a look at FUN_00104f60, the function takes in our user input as its 1st argument and spawns 101 separate threads to execute different subroutine functions.

We will now call this function asThread Pool Manager from this point onwards.

Within each subroutine function are specific conditions that we have to pass in order to release/unlock the mutex. If these conditions are not met, the program will hang indefinitely due to the mutex being locked.

Decoding all the values manually 101 times will be a pain in the ass, so it's pretty obvious that we had to rely on some kind of automated solver like Angr or z3. This challenge is a textbook scenario for applying Angr's Find Condition feature to search for a state that meets our arbitrary condition - In this case, we want the string "pass" to be printed out on stdout.

However, Angr in its current state does not support multi-threading program. Therefore, our plan is to recompile the program to force it to check our input sequentially.

Export Program

Firstly, we can select File -> Export Program from Ghidra to export the decompiled C code.

Or using Ghidra's headlessAnalyzer:

Cleaning Up

Within the decompiled code, most of the exported definitions such as eh_frame_hdr, fde_table_entry and more can be removed as they are not needed. The only components we need are:

1. Type Definition: Define data type aliases that are Ghidra-compatible, such as typedef unsigned int undefined4 , etc.

2. Subroutine Functions: Logical operations that verify our input, such as FUN_0010XXXX, etc.

3. Main Boilerplate: Program Entry Point/Main Function that handles user input before passing execution control to Thread Pool Manager.

4. Thread Pool Manager: The long list of if statements that invoke each subroutine function in a separate thread via pthread_create.

There are 2 ways to convert these subroutine functions from their multi-threaded form to sequential execution.

Recompilation

Method 1: Overriding Definitions

Redefine the signature for pthread_create. This only needs to be done once.

int pthread_create(pthread_t *thread, ulong *attr, long (*func_ptr)(long), char *arg) {
    return (*func_ptr)((long) arg);
}

Uncomment the mutex lock & unlock procedures for all 101 subroutine functions.

long FUN_001011d0(long param_1)

{
  uint uVar1;
  
  //pthread_mutex_lock((pthread_mutex_t *)&DAT_0010c070);
  uVar1 = *(uint *)(param_1 + 0x1b) >> 2 & 0x7ff;
  if (((uVar1 >> 2 ^ 0x557) + (uVar1 * 0x40 + 0x10c ^ (*(uint *)(param_1 + 0x14) & 0x7ff) >> 6) &
      0x7ff) == 0x79d) {
    //pthread_mutex_unlock((pthread_mutex_t *)&DAT_0010c070);
    return 0;
  }
  return 1;
}

We can keep the decode function intact, because pthread_create from now on will just act as a mask for all the subroutine functions.

Finally, compile the code with GNU Make:

100KB

override_definition.c

Open

Method 2: Replacing Functions

Once again, uncomment the mutex lock & unlock procedures for all 101 subroutine functions.

long FUN_001011d0(long param_1)

{
  uint uVar1;
  
  //pthread_mutex_lock((pthread_mutex_t *)&DAT_0010c070);
  uVar1 = *(uint *)(param_1 + 0x1b) >> 2 & 0x7ff;
  if (((uVar1 >> 2 ^ 0x557) + (uVar1 * 0x40 + 0x10c ^ (*(uint *)(param_1 + 0x14) & 0x7ff) >> 6) &
      0x7ff) == 0x79d) {
    //pthread_mutex_unlock((pthread_mutex_t *)&DAT_0010c070);
    return 0;
  }
  return 1;
}

Eliminate all occurrences of pthread_create by invoking the subroutine functions directly.

Recompile the C code with GNU Make:

39KB

replace_function.c

Open

Running Angr

With Angr's symbolic execution, we managed to get the flag after approximately 10 minutes.

Flag: ACS{y0u50lv3DtH33xpr35510N5!}

Final Script

For some reason, using this scaffold template from Angr CTF would always terminate the script halfway. As a workaround, I used this template instead which appears to be more optimized.

#!/usr/bin/env python3

import angr
import claripy
import logging

project = angr.Project("override_definition",load_options={"auto_load_libs": False}, main_opts={"base_addr": 0})
flag_chars = [claripy.BVS(f"c_{i}", 8) for i in range(29)]  # Flag length = 29
flag = claripy.Concat(*flag_chars)

logging.getLogger('angr').setLevel('INFO')
initial_state = project.factory.entry_state(stdin=flag)

# Printable characters only (including SPACE)
for f in flag_chars:
	initial_state.solver.add(f >= 0x20)
	initial_state.solver.add(f < 0x7f)

sm = project.factory.simulation_manager(initial_state)
sm.explore(find=lambda s: b"pass" in s.posix.dumps(1))

if sm.found:
	solution_state = sm.found[0]
	solution = solution_state.solver.eval(flag, cast_to=bytes)
	print(solution)
else:
    raise Exception('Could not find the solution')