CyberSpace CTF 2024 — Game with Rin
Nanakura Rin, a very skilled gamer, took one of the flags. You need to defeat her 200 times to get the flag back.
nc game-with-rin.challs.csc.tf 1337
We're given a Python server that looks like this:
Code (py):
1from basement_of_rin import NanakuraRin, flag, generate_graph
2
3import time
4from random import Random
5
6def Server(m):
7 print("Server> " + m)
8
9def Rin(m):
10 print("Rin> " + m)
11
12def check_subset(_subset, set):
13 subset = sorted(_subset)
14 assert len(subset) != 0
15 for i in range(len(subset) - 1):
16 subset[i] < subset[i + 1]
17 for x in subset:
18 assert x in set
19
20class disjoint_set:
21 def __init__(self, n):
22 self.n = n
23 self.p = [-1] * self.n
24 def root(self, u):
25 if self.p[u] < 0:
26 return u
27 self.p[u] = self.root(self.p[u])
28 return self.p[u]
29 def share(self, u, v):
30 return self.root(u) == self.root(v)
31 def merge(self, u, v):
32 u, v = self.root(u), self.root(v)
33 if u == v:
34 return False
35 if self.p[u] > self.p[v]:
36 u, v = v, u
37 self.p[u] += self.p[v]
38 self.p[v] = u
39 return True
40 def clear(self):
41 self.p = [-1] * self.n
42
43def check_tree(subset, V, edges):
44 assert len(subset) == V - 1
45 ds = disjoint_set(V)
46 for i in subset:
47 assert isinstance(i, int) and 0 <= i < len(edges)
48 u, v, w = edges[i]
49 assert ds.merge(u, v)
50
51def determine_the_winner(piles):
52 # https://en.wikipedia.org/wiki/Nim
53 # Rin-chan is perfect, so she'll always make the optimal move.
54 # You're perfect too, so you'll always make the perfect move as well.
55 # Let's fast-forward the game to the end :)
56 nim = 0
57 for x in piles:
58 nim ^= x
59 return "first" if nim != 0 else "second"
60
61class You:
62 def __init__(self, V, edges):
63 Server(f"{V = }")
64 Server(f"{edges = }")
65 def first_move(self):
66 Server("Please choose S")
67 return sorted(list(map(int, input("You> S = ").strip().split(" "))))
68 def read_first_move(self, S):
69 Rin(f"I choose S = {' '.join([str(i) for i in S])}")
70 def second_move(self):
71 Server("Please choose T")
72 return sorted(list(map(int, input("You> T = ").strip().split(" "))))
73
74Rin("Do you want this flag?")
75Rin("I'll consider giving it to you if you defeat me 200 times :)")
76
77time.sleep(0.5)
78
79Server("-----------------------------------------------------------------------------------------")
80Server("[Round Manual]")
81Server("1. The server generates a set of edges with integer weight on vertices 0 ~ V-1.")
82Server("2. You can either choose to go first or second.")
83Server("3. First player chooses a subset S of edges of size V-1 which forms a tree.")
84Server("( For the definition of tree, see https://en.wikipedia.org/wiki/Tree_(graph_theory) )")
85Server("4. Second player chooses a non-empty subset T of S.")
86Server("5. Add a pile consisting of w stones for each edge (u, v, w) in T.")
87Server("6. Winner of the round is the winner of the nim game on those set of piles.")
88Server("-----------------------------------------------------------------------------------------")
89
90time.sleep(0.5)
91
92Rin("GLHF!")
93
94time.sleep(0.5)
95
96for round_number in range(1, 201):
97 Server(f"Round {round_number}")
98
99 V, edges = generate_graph(round_number)
100 assert isinstance(V, int)
101 assert 30 <= V <= 200
102 assert len(edges) <= 300
103 for u, v, w in edges:
104 assert isinstance(u, int) and isinstance(v, int) and isinstance(w, int)
105 assert 0 <= u < V and 0 <= v < V and 0 <= w < 2**(V-1)
106
107 first, second = You(V, edges), NanakuraRin(V, edges)
108
109 Rin("Do you want to go [first] or [second]?")
110 resp = input("You> ").strip()
111 if resp not in ["first", "second"]:
112 Rin("That's not an option >:(")
113 exit(0)
114
115 if resp == "first":
116 Rin("Sure, you go first :D")
117 else:
118 Rin("Ok, I go first :D")
119 first, second = second, first
120
121 S = first.first_move()
122 second.read_first_move(S)
123 check_subset(S, [i for i in range(len(edges))])
124 check_tree(S, V, edges)
125
126 if resp == "first":
127 Rin("My turn!")
128 else:
129 Rin("Your turn!")
130
131 T = second.second_move()
132 check_subset(T, S)
133
134 if resp == "first":
135 Rin(f"I choose T = {' '.join([str(i) for i in T])}")
136
137 winner = determine_the_winner([edges[i][2] for i in T])
138
139 r = Random()
140
141 if winner != resp:
142 Rin(r.choice(["Git gud", "Noob", "Easy"]))
143 exit(0)
144
145 Rin(r.choice(["Not like this!", "You won :(", "Ouch!", "You got lucky this time."]))
146
147Rin("GG Well played!")
148Rin("I guess I have no choice but to give you the flag.")
149Rin(f"{flag}")On paper, the game works as follows:
- The server picks a
Vand generates random weighted edges between those nodes. - We choose whether to go first or second.
- Player 1 chooses a subset of size
V - 1that forms a tree. - Player 2 chooses a arbitrary (non-empty) subset of player 1's choice.
- This final subset is translated into Nim piles, and the player who wins Nim wins the round.
Unfortunately, there doesn't seem to be duplicate protection in the subset choosing: we can always go second, and pick the same edge twice to guarantee that XOR of the weights = 0 and we win Nim.
Here's a script that does just that:
Code (py):
1import pwn
2
3conn = pwn.remote('game-with-rin.challs.csc.tf', 1337)
4
5# Solve proof of work
6res = conn.recvuntil(b'Solution?')
7print(res)
8sol = input('Solution: ')
9conn.sendline(sol.encode())
10
11for i in range(200):
12 conn.recvuntil(b'Rin> Do you want to go [first] or [second]?')
13 conn.sendline(b'second')
14
15 conn.recvuntil(b'Rin> I choose S = ')
16 first = conn.recvline().decode().split(" ")[0]
17 conn.sendline(f'{first} {first}'.encode())
18
19 print(i, conn.recvline().strip().decode())
20
21print(conn.recvall().decode())Code:
1[x] Opening connection to game-with-rin.challs.csc.tf on port 1337
2[x] Opening connection to game-with-rin.challs.csc.tf on port 1337: Trying 34.47.157.234
3[+] Opening connection to game-with-rin.challs.csc.tf on port 1337: Done
4b'== proof-of-work: enabled ==\nplease solve a pow first\nYou can run the solver with:\n python3 <(curl -sSL https://goo.gle/kctf-pow) solve s.AE5X.AAD7HTl9L2wrq2RmljReSe+H\n===================\n\nSolution?'
5Solution: s.AAAO+qBXiJTTaK0jlC9QLDOQlE+eLqJ2cuvjB9Xh6+m49FO/xJpKU+hdTKqF+QKTIlF1pDhU7X3+uSJfkUocg6Pv49kIvWSbuFX7GJg5G4wf+XrZTZCKQcRZMNT9savz2AIKAE4vEYZ3Y5qrj/Uk769dgIGqoa1yC/pkhcRCtBMmS75pFUgsITcvUaJ0j0BZVuLgb+X35Q8uLdC0ktJFX2+O
60 Rin> Your turn!
71 Rin> Your turn!
82 Rin> Your turn!
9...
10196 Rin> Your turn!
11197 Rin> Your turn!
12198 Rin> Your turn!
13199 Rin> Your turn!
14[x] Receiving all data
15[x] Receiving all data: 33B
16[x] Receiving all data: 195B
17[+] Receiving all data: Done (195B)
18[*] Closed connection to game-with-rin.challs.csc.tf port 1337
19Server> Please choose T
20You> T = Rin> You got lucky this time.
21Rin> GG Well played!
22Rin> I guess I have no choice but to give you the flag.
23Rin> CSCTF{I_just_wanted_to_spend_time_with_you_baka!}