Type: pwn
Points: 151
Solves: 79
The challenge is a contract tracing system. The server plays the part of the contract tracing app which keeps a record of all IDs it has come into contact with. The IDs are 16 byte strings represented as UUIDs. It listens on a TCP socket for connections from the health authority, which sends lists of infected IDs. The server then checks whether any IDs it has recorded are infected.
The challenge is to force the server to disclose its IDs - one in particular will be the flag CTF{???????????}
.
Since it never transmits the IDs, we need to use a side-channel attack to disclose the flag.
The first problem when connecting is that there's no response from the server, whatever you send to it.
rlwrap nc tracing.2020.ctfcompetition.com 1337
Luckily, the challenge rust code builds easily with cargo build
, so you can run it and see the debug messages.
Unfortunately, I still couldn't reach the line debug!("Received {} IDs", count);
until I found out that you can hangup
just one side of a TCP connection.
You can shutdown just the client->server side, and still receive data back from the server.
In python you can use sock.shutdown(socket.SHUT_WR)
and this makes the server continue past the await
.
When sent a list of IDs via the TCP socket, the server first builds a binary search tree (BST). For each ID the server has recorded, it searches for it within the BST.
Let's imagine the IDs are single bytes rather than 16 bytes. If the server receives infected IDs 25,20,30,15,27,23,55,41,67,29,24,21,10,17,26 you will end up with this beautiful balanced BST:
25
______/ \______
/ \
20 30
/ \ / \
15 23 27 55
/ \ / \ / \ / \
10 17 21 24 26 29 41 67
If the server wants to check whether 28 exists within the BST, it walks down from the root.
- 28 > 25 (right)
- 28 < 30 (left)
- 28 > 27 (right)
- 28 < 29 (left, not found)
For a balanced binary search tree the lookup takes time O(log(n))
. However, the server builds a binary search tree which isn't necessarily
balanced. The resulting tree depends on the order which the IDs are received.
If the IDs are received in the order 10,15,17,20,21,23,24,25,26,27,29,30,41,55,67 then the BST will be super unbalanced:
10
\
15
\
17
\
20
...
A lookup for 8 will only require comparison with the root (8 < 10) since there's nothing on the left.
A lookup for 70, will require comparisons with each item of the tree (70 > 10, 70 > 15, 70 > 17) giving the worst case
lookup of O(n)
.
Since we, playing the role of the evil health authority, control the infected IDs sent to the server, we control the shape of the BST. By forcing a very unbalanced BST, the lookup takes much longer if the ID is on one side of the root node than the other.
If we guess a possible alphabet of !#$+-0123456789:<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ^_abcdefghijklmnopqrstuvwxyz
, then
to determine the character after CTF{
we start in the middle with letter Q: bisection method.
Send the root CTF{Q!!!!!!!!!!}
followed by 7000 IDs as far to the right as possible to produce a tree like:
CTF{Q!!!!!!!!!!}
CTF{zzzzzzzzzzz}
CTF{zzzzzzzzzzy}
CTF{zzzzzzzzzzx}
CTF{zzzzzzzzzzw}
CTF{zzzzzzzzzzv}
CTF{zzzzzzzzzzu}
...
Then shutdown the write side of the connection and time the duration until the server closes the connection.
def run(root, prefix, suffix, n, increase=True):
assert len(root) == 16
print(root, prefix, n, increase)
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('tracing.2020.ctfcompetition.com', 1337))
sock.send(root.encode())
attempts = ...
for attempt in attempts:
sock.send(attempt)
sock.shutdown(socket.SHUT_WR)
data = sock.recv(4)
start = time.time_ns()
while data:
data = sock.recv(1)
end = time.time_ns()
sock.close()
timing = end - start
print(timing)
return timing
If the flag is anywhere to the right of the root, the server will have to search all the way through the 7000 IDs. If the flag is anywhere to the left of the root, the lookup will complete after just one comparison with the root.
Then make the BST weighted to the left and compare the timings. If the right-weighted tree lookup took much longer, the
first character of the flag is between Q
and z
: we set the midpoint to h
.
At some point later we have determined that the flag starts CTF{1Bi
and that the next character is within qrstuvwxy
.
We send a right-weighted tree and it responds in 0.02ms.
CTF{1Biu!!!!!!!}
CTF{1Bi y zzzzzzz}
CTF{1Bi y zzzzzzy}
CTF{1Bi y zzzzzzx}
CTF{1Bi y zzzzzzw}
CTF{1Bi y zzzzzzv}
CTF{1Bi y zzzzzzu}
And the left-weighted tree responds in 88.6ms.
CTF{1Biuzzzzzzz}
CTF{1Biq!!!!!!!}
CTF{1Biq!!!!!!#}
CTF{1Biq!!!!!!$}
CTF{1Biq!!!!!!+}
CTF{1Biq!!!!!!-}
CTF{1Biq!!!!!!0}
So we guess that the character after CTF{1Bi
is within qrstu
(to the left).
There were some issues with getting accurate timings, especially when the midpoint was the correct letter, but with a
bit of messing around we get the flag CTF{1BitAtATime}
.
This was a fun challenge that just requires a little computer science.