San Diego CTF 2024 — Raccoon Run
The annual UC San Diego Raccoon Run is happening right now!! Apparently there's an underground gambling ring going on there. Maybe you can make it big?
We're given a Python server that looks like this:
Code (py):
1import json
2from time import time
3import tornado
4import tornado.websocket
5import tornado.ioloop
6import random
7import asyncio
8import os
9from datetime import timedelta
10
11import tornado.web
12import tornado.gen
13
14PORT = 8000
15
16NUM_RACCOONS = 8
17FINISH_LINE = 1000
18TARGET_BET = 1000
19STEP_TIME = 0.25 # in seconds
20BETTING_TIME = 15 # in seconds
21
22FLAG = os.environ["GZCTF_FLAG"]
23
24active_betters = {}
25connections = {}
26connection_count = 0
27game = None
28
29class RaccoonRun:
30 def __init__(self):
31 self.raccoons = [0] * 8
32 self.finishers = []
33 self.can_bet = True
34 self.bet_end = 0
35
36 def step(self):
37 self.can_bet = False
38 random_int = random.getrandbits(32)
39 for i in range(NUM_RACCOONS):
40 self.raccoons[i] += (random_int >> (i * 4)) % 16
41 for (i, x) in enumerate(self.raccoons):
42 if x >= FINISH_LINE and i not in self.finishers:
43 self.finishers.append(i)
44 return (self.raccoons, self.finishers)
45
46 def game_over(self):
47 return len(self.finishers) >= NUM_RACCOONS
48
49class Gambler:
50 def __init__(self, account=10):
51 self.account = account
52 self.guess = None
53 self.bet_amount = 0
54
55 def bet(self, guess, bet_amount):
56 if self.validate_bet(guess, bet_amount):
57 self.guess = guess
58 self.bet_amount = bet_amount
59 return True
60 else:
61 return False
62
63 def validate_bet(self, guess, bet_amount):
64 if (type(guess) is not list):
65 return False
66 if not all(type(x) is int for x in guess):
67 return False
68 if len(guess) != NUM_RACCOONS:
69 return False
70 if (type(bet_amount) is not int):
71 return False
72 if (bet_amount < 0 or bet_amount > self.account):
73 return False
74 return True
75
76 # updates amount of money in account after game is over and bet comes through
77 # and then return an boolean indicating whether you won/lost
78 def check_bet(self, game_instance):
79 if game_instance.finishers == self.guess:
80 self.account += self.bet_amount
81 return True
82 else:
83 self.account -= self.bet_amount
84 return False
85
86 def reset_bet(self):
87 self.guess = None
88 self.bet_amount = 0
89
90def get_race_information(id):
91 return json.dumps({"type": "race_information", "can_bet": "true" if game.can_bet else "false", "raccoons": game.raccoons, "finishers": game.finishers, "account": active_betters[id].account})
92
93class RRWebSocketHandler(tornado.websocket.WebSocketHandler):
94 def open(self):
95 global game
96 global active_betters
97 global connections
98 global connection_count
99
100 self.better_id = connection_count
101 active_betters[self.better_id] = Gambler()
102 connections[self.better_id] = self
103 connection_count += 1
104 self.write_message(get_race_information(self.better_id))
105 if game.can_bet:
106 self.write_message(json.dumps({"type":"betting-starts","until":game.bet_end}))
107
108 def on_message(self, message):
109 try:
110 data = json.loads(message)
111 if "type" not in data:
112 self.write_message(json.dumps({"type": "response", "value": "invalid WebSockets message"}))
113 elif (data["type"] == "bet"):
114 if (game.can_bet):
115 if active_betters[self.better_id].bet(data["order"], data["amount"]):
116 self.write_message(json.dumps({"type": "response", "value": "bet successfully placed!"}))
117 else:
118 self.write_message(json.dumps({"type": "response", "value": "bet is invalid, failed to be placed"}))
119 else:
120 self.write_message(json.dumps({"type": "response", "value": "bet cannot be placed after the race starts, failed to be placed"}))
121 elif (data["type"] == "buy_flag"):
122 if (active_betters[self.better_id].account > TARGET_BET):
123 self.write_message(json.dumps({"type": "flag", "value": FLAG}))
124 elif (data["type"] == "state"):
125 self.write_message(json.dumps({"type": "response", "value": "bet" if game.can_bet else "race"}))
126 elif (data["type"] == "account"):
127 self.write_message(json.dumps({"type": "response", "value": active_betters[self.better_id].account}))
128 else:
129 self.write_message(json.dumps({"type": "response", "value": "invalid WebSockets message"}))
130 except json.JSONDecodeError:
131 self.write_message(json.dumps({"type": "response", "value": "invalid WebSockets message"}))
132
133 def on_close(self):
134 del active_betters[self.better_id]
135 del connections[self.better_id]
136
137def game_loop():
138 global game
139 print("Raccoons", game.raccoons)
140 print("Finishers", game.finishers)
141 for (id, connection) in connections.items():
142 connection.write_message(get_race_information(id))
143 game.step()
144 if game.game_over():
145 print("Raccoons", game.raccoons)
146 print("Finishers", game.finishers)
147 for (id, connection) in connections.items():
148 connection.write_message(get_race_information(id))
149 connection.write_message(json.dumps({"type":"result", "value": game.finishers}))
150 for (id, x) in active_betters.items():
151 if x.guess != None:
152 win = x.check_bet(game)
153 connections[id].write_message(json.dumps({"type": "bet_status", "value": f"you {'won' if win else 'lost'} the bet, your account now has ${x.account}"}))
154 x.reset_bet()
155 else:
156 connections[id].write_message(json.dumps({"type": "bet_status", "value": f"you didn't place a bet, your account now has ${x.account}"}))
157 print("Every raccoon has finished the race.")
158 print(f"Starting new game! Leaving {BETTING_TIME} seconds for bets...")
159 game = RaccoonRun()
160 game.bet_end = time() + BETTING_TIME
161 for (id, connection) in connections.items():
162 connection.write_message(get_race_information(id))
163 connection.write_message(json.dumps({"type":"betting-starts","until":game.bet_end}))
164 tornado.ioloop.IOLoop.current().add_timeout(timedelta(seconds=BETTING_TIME), game_loop)
165 else:
166 tornado.ioloop.IOLoop.current().add_timeout(timedelta(seconds=STEP_TIME), game_loop)
167
168if __name__ == "__main__":
169 tornado.ioloop.IOLoop.configure("tornado.platform.asyncio.AsyncIOLoop")
170 io_loop = tornado.ioloop.IOLoop.current()
171 asyncio.set_event_loop(io_loop.asyncio_loop)
172 game = RaccoonRun()
173 print(f"Starting new game! Leaving {BETTING_TIME} seconds for bets...")
174 game.bet_end = time() + BETTING_TIME
175 tornado.ioloop.IOLoop.current().add_timeout(timedelta(seconds=BETTING_TIME), game_loop)
176 application = tornado.web.Application([
177 (r"/ws", RRWebSocketHandler),
178 (r"/(.*)", tornado.web.StaticFileHandler, {"path": "./static", "default_filename": "index.html"})
179 ])
180 application.listen(PORT)
181 io_loop.start()At each step of the race, 4-bit chunks of a random 32-bit int are added to each raccoons position, continuing until all 8 raccoons cross the finish line (> 1000). While we can bet on the order of the raccoons to finish the race, we only win if our guess is exactly correct.
The main idea with this challenge is that because we're given the positions of the raccoons at each step, we can reconstruct the exact 32-bit integer used to reach that step. Feeding that integer into an RNG cracker, we can reverse engineer the RNG being used by the server to run the races, then simulate each race ahead of time to bet flawlessly and buy the flag.
Code (py):
1import numpy as np
2import websocket
3import json
4from randcrack import RandCrack
5
6
7WS_URL = "ws://127.0.0.1:64045/ws"
8TARGET_BET = 1000
9
10rc = RandCrack()
11raccoons = np.zeros(8, dtype=int)
12balance = 10
13
14start_processing = False
15stop_processing = False
16
17
18def on_message(ws, message):
19 global start_processing, stop_processing, balance, raccoons
20
21 print('Received message:', message, flush=True)
22 data = json.loads(message)
23
24 match data['type']:
25 # Reset race data
26 case 'bet_status':
27 raccoons = np.zeros(8, dtype=int)
28
29 case 'betting-starts':
30 start_processing = True
31 if not rc.state:
32 return
33
34 # If `rc.state` is populated, stop sampling random output
35 stop_processing = True
36
37 # If we have enough to buy the flag, do so
38 if balance > TARGET_BET:
39 ws.send(json.dumps({
40 "type": "buy_flag"
41 }))
42 return
43
44 # Otherwise, predict the winners and place a bet
45 r_state = [0] * 8
46 finishers = []
47 while len(finishers) != 8:
48 random_int = rc.predict_getrandbits(32)
49 for i in range(8):
50 r_state[i] += (random_int >> (i * 4)) % 16
51 if r_state[i] >= 1000 and i not in finishers:
52 finishers.append(i)
53
54 print(f"The bet is: {finishers}")
55 ws.send(json.dumps({
56 "type": "bet",
57 "order": finishers,
58 "amount": balance
59 }))
60 balance *= 2
61
62 case 'race_information':
63 # Ignore data if we've started the script in the middle of a race, or after we've reached a betting
64 # phase with populated `rc.state`.
65 if not start_processing or stop_processing:
66 return
67 if data['can_bet'] == "true":
68 return
69
70 # If we've populated `rc.state` before the end of a race, keep advancing the RNG.
71 if rc.state:
72 rc.predict_getrandbits(32)
73
74 new_states = np.array(data['raccoons'])
75 diffs = new_states - raccoons
76 raccoons = new_states
77
78 print(diffs, flush=True)
79 # print(''.join(reversed(list(map(lambda d: bin(d)[2:].zfill(4), diffs)))))
80
81 # Reverse random integer:
82 # self.raccoons[i] += (random_int >> (i * 4)) % 16
83 reconstructed = 0
84 for i, num in enumerate(diffs):
85 reconstructed += num << (i * 4)
86
87 # Mask signed integer back to unsigned for randcrack
88 reconstructed &= 0xffffffff
89
90 rc.submit(reconstructed)
91 print(f'{rc.counter}: {reconstructed}', flush=True)
92
93
94if __name__ == "__main__":
95 ws = websocket.WebSocketApp(WS_URL, on_message=on_message)
96 ws.run_forever()After about ~5 games of sampling the RNG and 7 games of betting, we can purchase the flag:
Code (bash):
1PS C:\Users\kevin\Downloads> python3 .\solve.py
2Received message: {"type": "race_information", "can_bet": "true", "raccoons": [0, 0, 0, 0, 0, 0, 0, 0], "finishers": [], "account": 10}
3Received message: {"type": "betting-starts", "until": 1715572315.2874234}
4Received message: {"type": "race_information", "can_bet": "true", "raccoons": [0, 0, 0, 0, 0, 0, 0, 0], "finishers": [], "account": 10}
5Received message: {"type": "race_information", "can_bet": "false", "raccoons": [9, 0, 5, 15, 12, 2, 11, 7], "finishers": [], "account": 10}
6[ 9 0 5 15 12 2 11 7]
71: 2066543881
8Received message: {"type": "race_information", "can_bet": "false", "raccoons": [21, 14, 8, 18, 25, 14, 25, 10], "finishers": [], "account": 10}
9[12 14 3 3 13 12 14 3]
102: 1053635564
11Received message: {"type": "race_information", "can_bet": "false", "raccoons": [21, 15, 23, 31, 35, 24, 32, 25], "finishers": [], "account": 10}
12[ 0 1 15 13 10 10 7 15]
133: 4155170576
14Received message: {"type": "race_information", "can_bet": "false", "raccoons": [22, 22, 23, 46, 38, 30, 47, 25], "finishers": [], "account": 10}
15[ 1 7 0 15 3 6 15 0]
164: 258207857
17Received message: {"type": "race_information", "can_bet": "false", "raccoons": [37, 23, 23, 56, 42, 39, 50, 33], "finishers": [], "account": 10}
18[15 1 0 10 4 9 3 8]
195: 2207555615
20Received message: {"type": "race_information", "can_bet": "false", "raccoons": [50, 32, 30, 57, 53, 54, 53, 38], "finishers": [], "account": 10}
21[13 9 7 1 11 15 3 5]
226: 1408964509
23Received message: {"type": "race_information", "can_bet": "false", "raccoons": [51, 33, 31, 71, 60, 58, 67, 38], "finishers": [], "account": 10}
24[ 1 1 1 14 7 4 14 0]
257: 239591697
26Received message: {"type": "race_information", "can_bet": "false", "raccoons": [57, 35, 44, 84, 63, 72, 81, 45], "finishers": [], "account": 10}
27[ 6 2 13 13 3 14 14 7]
288: 2128862502
29Received message: {"type": "race_information", "can_bet": "false", "raccoons": [71, 37, 48, 85, 77, 72, 81, 55], "finishers": [], "account": 10}
30[14 2 4 1 14 0 0 10]
319: 2685277230
32Received message: {"type": "race_information", "can_bet": "false", "raccoons": [75, 47, 63, 94, 87, 82, 87, 63], "finishers": [], "account": 10}
33[ 4 10 15 9 10 10 6 8]
3410: 2259328932
35Received message: {"type": "race_information", "can_bet": "false", "raccoons": [84, 57, 64, 108, 102, 94, 93, 66], "finishers": [], "account": 10}
36[ 9 10 1 14 15 12 6 3]
3711: 919593385
38Received message: {"type": "race_information", "can_bet": "false", "raccoons": [91, 64, 67, 116, 106, 96, 106, 69], "finishers": [], "account": 10}
39[ 7 7 3 8 4 2 13 3]
4012: 1025803127
41Received message: {"type": "race_information", "can_bet": "false", "raccoons": [102, 71, 68, 129, 115, 101, 119, 76], "finishers": [], "account": 10}
42[11 7 1 13 9 5 13 7]
4313: 2103038331
44Received message: {"type": "race_information", "can_bet": "false", "raccoons": [111, 73, 80, 135, 123, 114, 130, 91], "finishers": [], "account": 10}
45[ 9 2 12 6 8 13 11 15]
4614: 4225264681
47Received message: {"type": "race_information", "can_bet": "false", "raccoons": [119, 84, 95, 143, 131, 119, 137, 104], "finishers": [], "account": 10}
48[ 8 11 15 8 8 5 7 13]
4915: 3612905400
50...
51Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1036, 1052, 1078, 1060, 1042, 975, 931, 1044], "finishers": [3, 2, 0, 1, 4, 7], "account": 640}
52Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1048, 1057, 1082, 1070, 1043, 981, 944, 1045], "finishers": [3, 2, 0, 1, 4, 7], "account": 640}
53Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1055, 1066, 1095, 1080, 1056, 984, 954, 1057], "finishers": [3, 2, 0, 1, 4, 7], "account": 640}
54Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1057, 1071, 1103, 1080, 1059, 984, 955, 1060], "finishers": [3, 2, 0, 1, 4, 7], "account": 640}
55Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1063, 1073, 1111, 1094, 1061, 999, 955, 1061], "finishers": [3, 2, 0, 1, 4, 7], "account": 640}
56Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1075, 1078, 1120, 1095, 1070, 1003, 967, 1066], "finishers": [3, 2, 0, 1, 4, 7, 5], "account": 640}
57Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1087, 1087, 1121, 1098, 1083, 1003, 967, 1077], "finishers": [3, 2, 0, 1, 4, 7, 5], "account": 640}
58Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1098, 1092, 1136, 1111, 1091, 1006, 973, 1091], "finishers": [3, 2, 0, 1, 4, 7, 5], "account": 640}
59Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1111, 1101, 1140, 1122, 1104, 1014, 983, 1102], "finishers": [3, 2, 0, 1, 4, 7, 5], "account": 640}
60Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1115, 1116, 1152, 1136, 1117, 1026, 993, 1107], "finishers": [3, 2, 0, 1, 4, 7, 5], "account": 640}
61Received message: {"type": "race_information", "can_bet": "false", "raccoons": [1129, 1117, 1163, 1143, 1117, 1029, 1005, 1108], "finishers": [3, 2, 0, 1, 4, 7, 5, 6], "account": 640}
62Received message: {"type": "result", "value": [3, 2, 0, 1, 4, 7, 5, 6]}
63Received message: {"type": "bet_status", "value": "you won the bet, your account now has $1280"}
64Received message: {"type": "race_information", "can_bet": "true", "raccoons": [0, 0, 0, 0, 0, 0, 0, 0], "finishers": [], "account": 1280}
65Received message: {"type": "betting-starts", "until": 1715572927.6933398}
66Received message: {"type": "flag", "value": "SDCTF{m3rs3nn3_tw15t3r_15_5cuff3d_b300818768b0}"}