---
description: Expression
---

# ACS 2023: expr

## 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.&#x20;

## Challenge Overview

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FpmXkjWTF0cE7bWCdEzZq%2Fimage.png?alt=media&#x26;token=1d4bb1f4-80d7-4424-a838-3bbf06cc1ea6" alt=""><figcaption></figcaption></figure>

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.&#x20;

{% hint style="info" %}
We will now call this function as`Thread Pool Manager` from this point onwards.
{% endhint %}

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FwmfosG5SXeJwSsx3M9Ug%2Fimage.png?alt=media&#x26;token=9ddcd791-bdfc-4fad-80f2-78e411656d47" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FEOkiegNNBAdPdOzw97Sf%2Fimage.png?alt=media&#x26;token=6bdc9f85-5e15-411f-8b29-99514ee74af6" alt=""><figcaption></figcaption></figure>

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.&#x20;

## Export Program

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2F2Ebr16W6WtVKB7fg4yNg%2Fimage.png?alt=media&#x26;token=cb2530a8-6af0-4ace-89bf-fa0e8641aff4" alt=""><figcaption></figcaption></figure>

Or using Ghidra's `headlessAnalyzer`:

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2F6cTbhHiGAjLix5O6vjOm%2Fimage.png?alt=media&#x26;token=9d737683-2172-4170-926f-ae464fe82eb1" alt=""><figcaption></figcaption></figure>

## 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`.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FdQd1J5KJ1LIep6ROHJVH%2Fimage.png?alt=media&#x26;token=7d85b444-bed7-43ba-8486-3d5e6b02cbfd" alt=""><figcaption></figcaption></figure>

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.

```c
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.

```c
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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2F9CzLO9SWA6GbOooMrBhF%2Fimage.png?alt=media&#x26;token=1ffc6836-eae8-40c3-92b2-ba2e174be76a" alt=""><figcaption></figcaption></figure>

Finally, compile the code with `GNU Make`:

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FTyucpoiJSfb8wQdamQKF%2Fimage.png?alt=media&#x26;token=22833403-677f-48cc-abf3-424cdaed64a0" alt=""><figcaption></figcaption></figure>

{% file src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FO94BDzmjJGAy8KDVrCOg%2Foverride_definition.c?alt=media&token=799833fa-4259-4347-a401-4fd175230003" %}

### Method 2: Replacing Functions

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

```c
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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FPjtbYmgsjRWAnzOqxeNH%2Fimage.png?alt=media&#x26;token=fd416332-29bc-4891-a9fa-138d8577bcfa" alt=""><figcaption></figcaption></figure>

Recompile the C code with `GNU Make`:&#x20;

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FwpimyQhZt1iCMcQay4Hx%2Fimage.png?alt=media&#x26;token=9b0de9de-6913-4a2e-8f89-46fdc3a56c7a" alt=""><figcaption></figcaption></figure>

{% file src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FpYsPrGyHXyvHGeQsyiGO%2Freplace_function.c?alt=media&token=0e54f31f-d8f3-47b3-a192-e5293bea490c" %}

## Running Angr

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FHmtGce42fOjaXivCpala%2Fimage.png?alt=media&#x26;token=e8a1c153-a30a-4a12-b70e-2e99f1980a14" alt=""><figcaption></figcaption></figure>

**Flag:** ACS{y0u50lv3DtH33xpr35510N5!}

## Final Script

{% hint style="warning" %}
For some reason, using this scaffold [template](https://github.com/jakespringer/angr_ctf/blob/master/02_angr_find_condition/scaffold02.py) from Angr CTF would always terminate the script halfway. As a workaround, I used this [template](https://github.com/angr/angr-examples/blob/master/examples/csaw_wyvern/solve.py) instead which appears to be more optimized.
{% endhint %}

```python
#!/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')
```
