This writeup outlines a solution for Locking Mechanism and also my thought process in solving it. This was my first time doing a CTF and my very first solve ever.
We're given a Dockerized Rust application, but I decided to build the code directly on my machine since I already had Cargo
installed and up to date. I'm not that well-versed in Rust yet (I solved a few Advent of Code problems in it), but I know
enough to poke around. The first thing I tried was to just cargo build and cargo run the application and see what happens.
It didn't halt, so upon looking at the code it looked like it was expecting an input of comma-separated integers.
In the file I noticed that there was a list of 104 integers, particularly this:
et flag = vec![
236, 213, 246, 206, 213, 171, 145, 141, 90, 153, 48, 22, 228, 116, 29, 247, 246, 87, 5, 82,
122, 158, 10, 231, 194, 190, 144, 5, 157, 110, 71, 83, 217, 109, 211, 221, 182, 242, 62,
255, 152, 72, 133, 194, 162, 238, 181, 228, 158,
];
From this I guessed that the program is probably expecting an input of numbers between 0 and 103. I verified this by inputting 104 and having it bomb. I'd also noticed that order of numbers didn't affect the corresponding output printed to the terminal, so I'd additionally guessed that I'm supposed to input a permutation of the numbers 0 through 103.
Next, I'd tried inputting the numbers 0 through 103 in order. It still didn't halt. So I started putting and moving around
print statements in the code. Doing so made me realize that the program was spawning one thread for each input, and waiting
for all threads to finish execution before proceeding (what this join is doing here):
for child in children {
let _ = child.join();
}
So this meant that the threads were not finishing execution, some of them were probably blocked by something. This is when
I decided to look more deeply at the body of create_thread, since presumably this is where all the action's happening.
I could see locks and waiting conditions in there, so that suggested to me that maybe the threads needed to execute in a
particular order for them all to finish execution.
That's when I scrolled down and look at key_config (not going to paste here, too long). Each element had a vector of one
or two elements, with the exception of one vector, which had none. That suggested to me that this must be a starting
point in a graph that's encoding dependencies among the threads. Indeed, key_config describes which threads must run first
before a given thread can execute to completion. The index corresponding to the vector with no elements is the starting point:
the thread that kicks off the whole thing and is waiting for no others before it can execute to completion. The graph of
dependencies among threads would have to be a directed graph without cycles (a directed acyclic graph), otherwise there would
be no possible input for which this program would halt.
With this hypothesis, I decided that I should probably take key_config, and parse it and populate a directed graph, and also
verify that the constructed graph is acyclic. I don't know Rust that well, so I wrote a Python script to create this graph.
I was also lazy, so I used ChatGPT to write me code that would parse out the numbers directly from a copy/paste from the Rust
code:
def extract_numbers_from_list(text):
# Define the regex pattern to match numbers within a list
pattern = r'\[(.*?)\]'
# Find the first match of the pattern in the text
match = re.search(pattern, text)
if match:
# Extract the content inside the square brackets
list_content = match.group(1)
# Extract individual numbers from the list content
numbers = re.findall(r'\b\d+\b', list_content)
# Convert the matched strings to integers and return
return [int(num) for num in numbers]
else:
return []
Using this function, along with networkx, I built a directed graph:
edge_list = []
dag = nx.DiGraph()
node_set = set()
for vertex2, line in enumerate(raw_rust_code.strip().split("\n")):
inbound = extract_numbers_from_list(line)
for vertex1 in inbound:
dag.add_edge(vertex1, vertex2)
node_set.add(vertex1)
After building the directed graph, I double checked that it was a DAG with nx.is_directed_acyclic_graph(dag), which returned
True. This told me that I was definitely on the right path. I then printed out a topological sort
of the nodes with the following:
print(list(nx.topological_sort(dag)))
A topological sort on a DAG is a linear ordering of its nodes which is consistent with the partial order that the DAG defines. You can think of it as "projecting" the DAG onto the real number line in such a way that preserves all edges' directionality.
The printed out topological sort is a permutation of the numbers 0 through 103, which I then copy/pasted as the input into the original Rust program. It took about 5-10 seconds for the Rust program to halt with this input, but it did, and it printed out the flag right before halting.
While I didn't know much of Rust to solve this challenge, I think the fact that I'd studied all kinds of weird concurrency problems as part of my PhD went a long way in helping me quickly make the leaps in logic to solve this one.
wow, DAGs come to rescue once again. lol