Capturing the flag with ChatGPT: solving DiceCTF 2023 rev/time-travel
I was recently invited to play the latest edition of DiceCTF. It was a last-minute invite, so I just played the last two hours of the event. With most of the team focused on the remaining web challenges, I decided to tackle one of the reversing challenges. I chose the rev/time-travel challenge.
As shown above, two files were provided, and the challenge statement read: “This flag calculator has been running for a while…”. The time_travel file was a standard x64 ELF executable, and the input.bin file was a 166404 bytes data file.
I loaded time_travel into Ghidra and spent some time doing basic renaming and reviewing the program’s decompiled version. The pseudocode of the main function resembled something like the code below:
The code reads a 166404 bytes file, loads it into a data buffer, enters a 64 iterations loop, and, for each iteration, creates an 18x18 matrix (a list of lists, a long ** variable, etc.), then fills it with data from the data buffer. The matrix is then fed to the FUN_008 function and ends up in a loop that never ends.
The question now was — What is FUN_008 supposed to do, and why is it taking forever to run?
FUN008 and its supporting functions read something like the following Ghidra decompiled code.
I couldn’t figure out right away what the code was doing, so I decided to ask ChatGPT for some help.
The AI promptly answered with a sweet surprise.
Based on the answer, I discovered FUN_008 was doing nothing more than calculating the determinant of a given matrix. As the provided matrix size was 18, choosing a non-optimal algorithm might result in underflow/overflow problems or incur an O^n complexity. At least, that is what I remember from the Linear Algebra classes I took more than ten years ago 👴, so don’t quote me on that.
Once the problem was clear, thanks to ChatGPT, I chose a step-by-step approach relying on the battle-hardened numpy python package. More specifically, the numpy.linalg.det function, which computes the determinant of an array via LU factorization using the LAPACK routine. My solution takes the following steps:
- Dump the matrices from the input.bin file
- Load the matrices into a python script and use numpy to calculate the determinants
- Feed the determinants back into the original time_travel loop to output the flag.
The solution is composed of two files, a C program, and a python script.
Using the code and instructions provided above, I got the flag.
