Reverse Engineering - Startrek 1 and 2 - USCG 2024
A series of two reverse engineering challenge developed by DrBHacking for Season IV of the U.S. Cyber Open.
Description
Part 1
You are a remote navigator directing Captain Kirk, who is commanding the USS Enterprise, and Captain Spock, who is commanding the USS Endeavour. Your mission is to guide them on a journey 100 galaxies away to an ancient, advanced civilization known as the “Architects” who have hidden a powerful artifact. This artifact, known as the “Quantum Key,” has the potential to unlock new dimensions, granting unparalleled knowledge and power to its possessor…
But your ships’ warp drives are limited and as you journey through the galaxies, you discover that some contain ancient portal mechanisms that can instantly transport you to another galaxy. These portals are unpredictable and may send you further ahead (Slipstream Portals) or behind (Wormhole Portals) your current position. Can you strategically navigate these worlds and accomplish your mission on limited fuel?
Part 2
The USS Enterprise receives a distress signal from a Federation research station on the remote planet of Xylophia-IV. The station’s scientists were conducting experiments on a newly discovered ancient alien artifact, but their transmissions suddenly ceased. Sensors indicate unusual energy fluctuations emanating from the planet’s surface. With the power of the Quantum Key unlocked, the Starships now have enhanced capabilities. They have more fuel capacity, and can do longer jumps! … But the universe has gotten bigger as well.
Captain Kirk and Captain Spock need your help again to navigate to the research station, determine the cause of the distress signal, and retrieve the ancient artifact.
Solution
Both Startrek 1 and 2 use the exact same solution with slightly different parameters. This writeup will use the parameters and source code for Startrek 1 for the majority of the writeup. Anywhere that the behavior or parameters of Startrek 2 differ from Startrek 1 will be noted.
Summary:
- Reverse engineering the
jumpfunction in the binary with Ghidra reveals how map data is stored in memory. - The third parameter of the
jumpfunction contains the map information. Further analysis ofmainreveals the total size of the map array. - Map data can be extracted from memory using GDB by breaking on the
jumpfunction. - The map data can be treated as a directed graph where each point or “galaxy” is a vertex, and edges are drawn from one galaxy to another in the positive direction. Additionally, the “wormholes” and “slipstreams” can be treated as edges.
- Using the directed graph, a BFS algorithm can be used to find the most efficent paths to the target galaxy.
- Once two valid paths are found using the BFS algorithm, the flag can only be aquired by using gdb to read register values shortly after the success method is printed.
Initial Analysis on jump and main
When run, the startrek binary will loop through two ships. Both ships start at 5 fuel and at position 000. Rerunning the binary multiple times shows that the jump distance on both ships is random. An additional noteable behavior is that the binary will sleep for 1 second at least once on every loop.
Ships in Startrek 2 start with 8 fuel.
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
┌[[email protected]]-[startrek-1]
└─ ▶ ./startrek
Captains Kirk and Spock both begin in Galaxy 000. Their ships' fuel levels are both at 100%. Good luck! If you help the Captains accomplish their mission, you will surely Live Long and Prosper!
Starship: 1 Current Galaxy: 000 Jumps Remaining: 5
Preparing the ship for the next jump...
Do you want to tell the Captain to alter his trajectory (y/n)?
n
Jumped 6 galaxies and landed on 006
Starship: 2 Current Galaxy: 000 Jumps Remaining: 5
Preparing the ship for the next jump...
Do you want to tell the Captain to alter his trajectory (y/n)?
n
...
Starship: 1 Current Galaxy: 016 Jumps Remaining: 1
Preparing the ship for the next jump...
Do you want to tell the Captain to alter his trajectory (y/n)?
n
Jumped 5 galaxies and landed on 021
This galaxy contained a wormhole, you were teleported to galaxy 003.
Starship: 2 Current Galaxy: 086 Jumps Remaining: 1
Preparing the ship for the next jump...
Do you want to tell the Captain to alter his trajectory (y/n)?
n
Jumped 4 galaxies and landed on 090
You failed to guide both ships to the correct world. The Architects will not relinquish the Quantum Key!
The startrek 2 binary adds an additional prompt at the very beginning asking to transfer fuel from ship 1 to ship 2.
Additional behavior includes allowing for a trajectory change. This is also random, and the heading input has no influence on the new trajectory.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
┌[[email protected]]-[startrek-1]
└─ ▶ ./startrek
Captains Kirk and Spock both begin in Galaxy 000. Their ships' fuel levels are both at 100%. Good luck! If you help the Captains accomplish their mission, you will surely Live Long and Prosper!
Starship: 1 Current Galaxy: 000 Jumps Remaining: 5
Preparing the ship for the next jump...
Do you want to tell the Captain to alter his trajectory (y/n)?
y
Choose a course heading for the ship, it must be a combination of a letter and a digit (ie. 'D9'):
D9
The Starship is now headed in direction D9
Do you wish to modify the trajectory any further (y/n)?
n
Jumped 4 galaxies and landed on 004
This galaxy contained a slipstream, you were teleported to galaxy 075.
Throwing this binary in Ghidra produces some pretty ugly decompilation, so instead of screenshots, below is the source code for startrek that I was able to derive from Ghidra decompilation, and observing behavior in GDB. This code is generalized, for the most part, for both Startrek 1 and 2 with differing paramters defined at the top. The one major differnce between the source code of Startrek 1 and 2 is that the second challenge allows fuel transfer.
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#define CHALLENGE 1 // 2 for Startrek 2
#define MAP_SIZE 100 // 1600 for Startrek 2
#define TARGET 100 // 1600 for Startrek 2
#define FUEL 5 // 8 for Startrek 2
#define NUM_SHIPS 2
#define MAX_JUMP 6 // 7 for Startrek 2
struct ship_info {
int id;
int loc;
int fuel;
int complete;
};
void jump(struct ship_info* ship, uint jump_distance, int* map) {
int portal_index;
if(jump_distance > 0 && jump_distance < MAX_JUMP + 1) {
int next_loc = ship->loc + jump_distance;
printf("Jumped %d galaxies and landed on %03d\n", jump_distance, next_loc);
portal_index = next_loc;
if(map[portal_index] == 0) {
if(map[MAP_SIZE + 1 + portal_index] != 0) {
next_loc = map[MAP_SIZE + 1 + portal_index];
map[MAP_SIZE + 1 + portal_index] = 0;
printf("This galaxy contained a wormhole, you were teleported to galaxy %03d.\n", next_loc);
} else {
next_loc = map[portal_index];
map[portal_index] = 0;
printf("This galaxy contained a slipstream, you were teleported to galaxy %03d.\n", next_loc);
}
ship->loc = next_loc;
}
} else {
puts("bad trajectory");
}
ship->fuel--;
return;
}
void main(int argc, char* argv[]) {
struct ship_info* ships[NUM_SHIPS];
int map[MAP_SIZE * 2 + 1];
memset(map, 0, MAP_SIZE * 2 + 1);
// Worm holes and slipstreams loaded into map
for(int i = 0; i < NUM_SHIPS; i++) {
ships[i]->id = i;
ships[i]->loc = 0;
ships[i]->fuel = FUEL;
}
#if CHALLENGE == 1
puts("Captains Kirk and Spock both begin in Galaxy 000. Their ships\' fuel levels are both at 100%. Good luck! If you help the Captains accomplish their mission, you will surely Live Long and Prosper!");
#elif CHALLENGE == 2
puts("Captain Kirk is holding the Quantum Key and has the power to transfer fuel cells to Captain Spock before the journey begins.\nHow many does he choose to transfer (if any)?\n");
int d;
scanf("%d", &d);
if(d < FUEL) {
ships[0].fuel - d;
ships[1].fuel + d;
}
#endif
srand(time(0))
while(ships[NUM_SHIPS]->fuel > 0) {
for(int i = 0; i < NUM_SHIPS; i++) {
printf("\nStarship: %d\tCurrent Galaxy: %03d\tJumps Remaining: %d\n", ships[i]->id, ships[i]->loc, ships[i]->fuel);
puts("Preparing the ship for the next jump...");
int next_jump = (rand() % MAX_JUMP) + 1;
sleep(1);
char c;
puts("Do you want to tell the Captain to alter his trajectory (y/n)? ");
scanf("%c", &c);
while(c == 'y') {
char heading[2];
puts("Choose a course heading for the ship, it must be a combination of a letter and a digi t (ie. \'D9\'): ");
scanf("%2s", &heading);
int new_jump = (rand() % MAX_JUMP) + 1;
sleep(1);
printf("The Starship is now headed in direction ");
printf(heading, new_jump * next_jump); // Format str vuln
putchar(0xa);
next_jump = new_jump;
puts("Do you wish to modify the trajectory any further (y/n)? ");
scanf("%c", &c);
}
jump(ships[i], next_jump, map);
if(target <= ships[i]->loc) {
ships[i]->fuel = 0;
ships[i]->complete = 0xbaadd00d;
}
}
}
int completed = 0;
for(int i = 0; i < NUM_SHIPS; i++) {
if(ships[i]->completed != 0) {
completed++;
}
}
if(completed == NUM_SHIPS) {
puts("The Architects are impressed by your Space Navigation skills. They have deemed Kirk and Spo ck worthy of the Quantum Key!");
// Decrypt flag
} else {
puts("You failed to guide both ships to the correct world. The Architects will not relinquish the Quantum Key!");
}
}
Based on the analysis and derived source code, the game appears to be a variation of chutes and ladders. Given this information, a simple BFS algorithm can be used to find the most efficent path to solve.
Originally, I thought that I could just set both ship locations to 100. Unfortunately, the binary was keeping track of moves in some way and using that as the key to decrypt the flag, forcing me to need to solve the chutes and ladders game.
Overcoming Jump Distance Randomness
The obvious first obstacle to using the right path is the randomness or dice roll mechanic. This behavior is controlled using the C Standard Library function rand(). There are three ways to bypass that randomness mechanism.
- Using the start time of the binary as the seed to
randto be able to predict the next value, then re-rolling the trajectory until a favorable number is landed on. - Taking advantage of a format string vulnerability in the re-roll functionality to get the value of the new trajectory, then re-rolling until a favorable number is landed on.
- Using LD_PRELOAD to overload the functionality of
randto only return the desired numbers, bypassing randomness altogether.
In my solution, I went with the third option because not only did it remove all randomness, but it also allowed me to bypass all calls to sleep by overloading the function definition.
Below is the code I used to overload rand and sleep functionality.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define _GNU_SOURCE
int count = 0;
int moves[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int rand(void) {
int r = moves[count]-1;
count++;
return r;
}
unsigned int sleep(unsigned int seconds) {
return 0;
}
The code above will return the exact order of moves provided in the moves array when rand is called.
Extracting Map Data Using GDB
The map data itself which defines the game board can be extracted from either Ghidra or GDB. I used GDB to extract map info because I felt it was the best option at the time. However, a custom struct can be created in Ghidra that allows map data to be easily extracted.
To extract map data from GDB, I wrote a GDB Python script that would automatically read the data from memory and put that data into a JSON format that I could easily paste in my solver.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gdb
MAP_SIZE = 100 # 1600 for Startrek 2
MAP = {'slipstreams': [], 'wormholes': []}
def get_section(addr: str):
for galaxy in range(MAP_SIZE+1):
jump = gdb.execute(f'x/wd {addr}+({galaxy}*4)', to_string=True)
jump = int(jump.strip().split(':')[-1].strip())
if jump != 0:
if jump < galaxy:
MAP['wormholes'].append((galaxy, jump))
if jump > galaxy:
MAP['slipstreams'].append((galaxy, jump))
map = int(gdb.execute('p $rdx', to_string=True).strip()[5:], 16)
get_section(hex(map))
get_section(hex(map + ((MAP_SIZE+1)*4)))
print(MAP)
The following two code blocks show the extracted map data for both Startrek 1 and 2.
1
2
3
4
5
6
7
8
9
gef➤ b jump
Breakpoint 1 at 0x1271
gef➤ r
Starting program: ./startrek1
...
gef➤ source ./extract-map.py
{'slipstreams': [(4, 75), (5, 15), (19, 41), (28, 50), (35, 96), (44, 82), (53, 94), (59, 95), (70, 91)], 'wormholes': [(21, 3), (31, 8), (47, 30), (52, 23), (76, 41), (81, 62), (88, 67), (98, 12)]}
1
2
3
4
5
6
7
8
9
gef➤ b jump
Breakpoint 1 at 0x1291
gef➤ r
Starting program: ./startrek2
...
gef➤ source ./extract-map.py
{'slipstreams': [(2, 181), (8, 206), (16, 1308), (18, 1370), (67, 791), (77, 489), (81, 735), (91, 1232), (104, 1116), (118, 810), (124, 683), (125, 900), (132, 1046), (139, 991), (140, 306), (156, 1479), (160, 1243), (208, 804), (209, 945), (236, 1337), (246, 878), (250, 1503), (270, 1281), (275, 1578), (279, 1312), (280, 1304), (284, 1198), (288, 1088), (291, 1192), (298, 664), (301, 1300), (322, 1115), (334, 1018), (369, 400), (370, 817), (376, 1412), (383, 676), (389, 1296), (399, 1572), (404, 1473), (410, 1424), (467, 1396), (476, 489), (499, 1024), (514, 532), (561, 1270), (568, 1506), (587, 728), (606, 997), (626, 1060), (634, 1421), (638, 651), (639, 651), (675, 787), (677, 1087), (678, 1088), (705, 1228), (717, 989), (725, 1546), (747, 888), (765, 1356), (773, 886), (779, 1567), (793, 1178), (795, 987), (818, 1276), (832, 1134), (841, 1311), (848, 1008), (856, 1043), (864, 1536), (865, 926), (884, 1501), (896, 953), (897, 1561), (916, 1020), (928, 1322), (946, 1156), (953, 1435), (954, 1234), (966, 1217), (978, 1261), (981, 1436), (986, 1085), (996, 1250), (1006, 1569), (1066, 1247), (1074, 1111), (1076, 1568), (1084, 1355), (1104, 1191), (1121, 1373), (1126, 1348), (1141, 1205), (1162, 1232), (1165, 1206), (1183, 1598), (1196, 1324), (1200, 1592), (1213, 1416), (1223, 1360), (1227, 1528), (1234, 1458), (1243, 1430), (1266, 1553), (1270, 1523), (1274, 1431), (1287, 1381), (1291, 1377), (1295, 1595), (1298, 1429), (1301, 1462), (1305, 1562), (1348, 1570), (1358, 1504), (1422, 1536), (1426, 1593), (1430, 1493), (1435, 1464), (1443, 1475), (1451, 1490), (1456, 1486), (1460, 1581), (1463, 1576), (1479, 1580), (1489, 1520), (1498, 1555), (1500, 1578), (1509, 1564), (1535, 1572), (1547, 1586), (1549, 1567), (1556, 1587), (1557, 1585)], 'wormholes': [(14, 2), (25, 10), (56, 37), (71, 3), (75, 17), (78, 66), (92, 25), (96, 78), (97, 43), (100, 19), (110, 12), (126, 85), (131, 55), (138, 3), (142, 87), (170, 118), (177, 67), (178, 99), (193, 101), (206, 90), (214, 32), (221, 45), (224, 43), (241, 205), (251, 216), (253, 221), (258, 95), (261, 63), (269, 233), (276, 266), (285, 199), (294, 76), (297, 16), (299, 156), (308, 264), (317, 248), (328, 241), (337, 162), (360, 206), (400, 201), (411, 39), (414, 368), (445, 398), (461, 383), (468, 88), (493, 159), (527, 364), (541, 517), (550, 517), (570, 541), (580, 335), (605, 580), (614, 195), (617, 435), (631, 410), (640, 475), (651, 199), (660, 377), (662, 400), (663, 537), (700, 595), (702, 176), (771, 483), (781, 759), (796, 34), (805, 487), (810, 155), (834, 41), (849, 59), (857, 438), (910, 623), (927, 167), (939, 916), (947, 836), (952, 287), (969, 548), (971, 366), (972, 266), (991, 514), (995, 139), (1017, 537), (1026, 27), (1030, 370), (1037, 277), (1046, 920), (1049, 462), (1072, 1032), (1088, 704), (1093, 690), (1095, 637), (1109, 673), (1111, 719), (1118, 242), (1124, 278), (1133, 675), (1146, 528), (1154, 1101), (1174, 778), (1202, 978), (1209, 275), (1210, 1168), (1226, 1131), (1236, 1077), (1238, 4), (1256, 487), (1263, 621), (1286, 650), (1297, 280), (1312, 94), (1353, 542), (1378, 450), (1379, 636), (1383, 648), (1408, 676), (1411, 511), (1433, 950), (1440, 873), (1447, 882), (1453, 1053), (1461, 425), (1470, 1192), (1482, 1242), (1490, 817), (1491, 225), (1503, 58), (1518, 996), (1521, 1045), (1531, 114), (1561, 1011), (1599, 552)]}
BFS Algorithm for Finding Valid Paths
As stated in the summary, the map data can be treated as a directed graph wherein each galaxy is a vertex, and each possible jump is an edge. Using this data structure for interpretting map data allows for the use of several path finding algorithms, of which, I used breadth first search. The code below shows my implementation of BFS for finding the most effective paths through the galaxy resulting in a generalized solution for both iterations of this challenge.
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
from pwn import *
MAP_SIZE = 100
MAX_JUMP = 6
FUEL = 5
jumps = {'slipstreams': [(4, 75), (5, 15), (19, 41), (28, 50), (35, 96), (44, 82), (53, 94), (59, 95), (70, 91)], 'wormholes': [(21, 3), (31, 8), (47, 30), (52, 23), (76, 41), (81, 62), (88, 67), (98, 12)]}
paths = {'spock': [[(0, 0)]], 'kirk': [[(0, 0)]]}
queue = []
for captain in paths:
queue.clear()
queue.append(0)
while len(queue):
current = queue.pop(0)
path = paths[captain].pop(0)
used = []
for i in range(1, MAX_JUMP + 1):
n = current + i
if n == MAP_SIZE:
paths[captain] = path + [(i, n)]
for k, l in enumerate(path):
if k < len(path) - 1:
d = l[1] + path[k+1][0]
if (r := next((c for c, t in enumerate(jumps['slipstreams']) if t[0] == d), None)) != None:
jumps['slipstreams'].pop(r)
if (r := next((c for c, t in enumerate(jumps['wormholes']) if t[0] == d), None)) != None:
jumps['wormholes'].pop(r)
queue.clear()
break
elif (j := next((t[1] for c, t in enumerate(jumps['slipstreams']) if t[0] == n), None)) != None:
used.append(i)
queue.append(j)
paths[captain].append(path + [(i, j)])
elif (j := next((t[1] for c, t in enumerate(jumps['wormholes']) if t[0] == n), None)) != None:
used.append(i)
queue.append(j)
paths[captain].append(path + [(i, j)])
else:
if len(used) > 0 and used[-1] == MAX_JUMP:
for k in range(MAX_JUMP, -1, -1):
if k not in used:
queue.append(current + k)
paths[captain].append(path + [(k, current + k)])
break
else:
queue.append(n)
paths[captain].append(path + [(i, n)])
print('FOUND PATHS')
for captain in paths:
print(f'{captain}:', [j[0] for j in paths[captain][1:]])
1
2
3
4
5
┌[[email protected]]-[startrek-1]
└─ ▶ python chutes-and-ladders.py
FOUND PATHS
spock: [4, 1, 6, 5, 4]
kirk: [5, 4, 6, 6, 6]
1
2
3
4
5
┌[[email protected]]-[startrek-2]
└─ ▶ python chutes-and-ladders.py
FOUND PATHS:
spock: [8, 3, 7, 4, 8, 8]
kirk: [8, 8, 4, 3, 8, 8, 8, 2, 5, 2]
These paths can be used with the overloaded rand function to pass in only the desired values resulting in the puzzle being solved.
Aquiring the Flag From GDB
Once both ships reach the target galaxy, the binary will print a success message, but no flag is output. In Startrek 1 the flag can be found in whole in the $rcx register at the end of the program. Startrek 2 however, differs in that the flag is only shown in parts in the $rax register.
To extract the flag from Startrek 1, the solution is as simple as setting a breakpoint at main+2685 and then reading the value of $rcx at the breakpoint.
To extract the flag from Startrek 2, a breakpoint needs to be set at main+5649. Once the breakpoint is hit, the flag will be shown eight bytes at a time in the $rax register. This means that for each eight bytes of the flag, a continue command needs to be sent to GDB to get the next portion of the flag.
Startrek 1 flag: USCGSIV{148c1252d_U_so1ved_it@Warp_Sp33d}
Startrek 2 flag: USCGSIV{[email protected]!}