Rusty Rev 2 - Hacker's Odyssey CTF

Link to archived challenge

Description

Looks like they’ve gotten smarter: this time the flag is locked behind a hash function! You might need the dark art of optimization for this one.

I’m sure you’ll figure it out. Can’t promise you won’t be cursed in the process though :P

Players are given two files to download: flag-checker and flag-checker-arm64.

There are also three hints available:

1. This challenge can be solved similarly to Rusty Rev 1 - but you’ll want to optimize your script.
2. Don’t forget the flag format:
   1. starts with clubeh{
   2. ends with }
   3. contains only printable ASCII characters
3. A well-optimized script should be able to get the flag in under 3 minutes.
   You may have better luck with the x86-64 binary compared to the arm64 one.

Note: using the x86-64 binary should work fine on any device, and will likely be easier to work with than the ARM64 binary.

Analysis

This challenge is very similar to Rusty Rev 1.
I’ll be assuming you’ve already read that writeup to understand the premise of this challenge.
The main difference is the flag-checking logic, which is significantly more complicated.

As before, basic static analysis will reveal the flag length: 0x34 (52) bytes.

Solution

This solution also uses angr, whose documentation you can find here.
The section on optimizing symbolic execution is especially relevant here, along with this cheat sheet.

Here’s a cleaned-up version of my solve script:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import angr
import claripy


FLAG_LEN = 52  # determined via static analysis
FLAG_PREFIX = b"clubeh{"


def check_found(state: angr.SimState) -> bool:
	return b"Flag is correct" in b''.join(state.posix.stdout.concretize())


def solve(exe: str):
	# initialize angr project - auto_load_libs is disabled to speed up 
	proj = angr.Project(exe, auto_load_libs=False)

	# create symbolic variable to represent our input
	flag_str = claripy.Concat(
		# hardcoding the prefix here is slightly faster than adding constraints later
		claripy.BVV(FLAG_PREFIX),
		claripy.BVS("flag_sym", 8 * (FLAG_LEN - len(FLAG_PREFIX))),
	)

	# create initial program state
	state = proj.factory.entry_state(
		args = [exe, flag_str],  # CLI arguments
		add_options = {
			# fill uninitialized memory with zeros
			angr.options.ZERO_FILL_UNCONSTRAINED_REGISTERS,
			angr.options.ZERO_FILL_UNCONSTRAINED_MEMORY,
		},
	)

	# constrain flag characters, assuming the flag only uses `a-z0-9_{}`
	for c in flag_str.chop(8):
		state.solver.add(claripy.Or(
			claripy.And(c >= ord('0'), c <= ord('9')),
			claripy.And(c >= ord('_'), c <= ord('}')),
		))

	# create a new SimulationManager from the initial state
	simgr = proj.factory.simulation_manager(state)

	# enable threading for faster execution
	simgr.use_technique(angr.exploration_techniques.threading.Threading())

	# search for a state where the flag is correct
	simgr.explore(find=check_found)

	assert len(simgr.found) > 0, "failed to locate any matching states!"

	# concretize up to 3 valid solutions (if there are multiple)
	results = simgr.found[0].solver.eval_upto(flag_str, cast_to=bytes, n=3)

	print(f"Results: {results}")


if __name__ == "__main__":
	solve("./flag-checker")

This script has a few changes:

1. Updated flag length.
2. The beginning of the flag is constrained to clubeh{.
3. Each byte of the flag is constrained to certain ASCII character ranges. These ranges exclude uppercase letters and most punctuation marks.
   Using the full range of ASCII printable characters (0x20 to 0x7e) works too, it’s just slower.
4. The Threading technique is enabled, which can help when angr spends a lot of time in native dependencies (like z3).

A few notes on optimization:

1. Further tightening the character constraints actually increased the execution time in my testing.
2. Using pypy often helps, but when I tried it here, it quickly used over 4GB of RAM and OOMed.
3. Profiling shows that 80% of time is spent in z3 - and most of that is spent copying z3 solver states.
   This is likely why adding more constraints slows down execution: the solver states became larger and thus took longer to clone.

This script takes about 30 seconds to finish on my desktop, with peak memory usage around 560MB (Ryzen 5600X, CPython 3.11.1, angr 9.2.37).