The following description is provided:
Robots enjoy some strange games and we just can’t quite figure this one out. Maybe you will have better luck than us.
The game offers a choice between two hex strings asking for the “bigger” one. Anyway, it doesn’t appear to be a way to determine which one is bigger just by looking at the values.
The challenge consists in winning at this game for 75 times in a row.
0 $ nc ec2-23-21-19-72.compute-1.amazonaws.com 6969 You have gotten 0 of 75 Choice 1 = 68af489d11366a85e755d95f516c48c50f Choice 2 = 9795b347f0ceb9aa35f6127cdfb7145810 Which one is bigger? (1 or 2) 2 2 Correct! -------------------- You have gotten 1 of 75 Choice 1 = 77c99d06baea4f703316e683a25264e3ba Choice 2 = 2dcccbe6467658ed37b35167eb9f6e3318 Which one is bigger? (1 or 2) 1 1 Wrong :(
After several attempts, it’s possible to see some recurrent values. Indeed, it turns out to be a finite set of hex-encoded random 17-byte strings with a strict total ordering on them. We counted 500 different strings during our experiments.
The strategy for winning is to play while keeping track of the values and sorting them on a list. The following script succeeded in winning for 75 times in a row after about 3 hours.
#!/usr/bin/python import socket import re # order: small ----> big games =  save_list = True def recv_tillreturn(sock, times=1): """Receive times lines of data from a socket""" total_data= while times > 0: times -= 1 dat = "" while 1: char = sock.recv(1) if char == "\n": dat=dat+char;break else: dat=dat+char total_data.append(dat) return ''.join(total_data) def insert(c1, c2): """Insert a pair of ordered value in the games list, where c1 > c2.""" global games i_c1 = -1 i_c2 = -1 for i in range(len(games)): if games[i] == c1: i_c1 = i if games[i] == c2: i_c2 = i if i_c1 == i_c2 == -1: # c1 and c2 not found: insert them to the head of the list games.insert(0,c1) games.insert(0,c2) elif i_c1 != -1 and i_c2 == -1: # c1 found but not c2: insert c2 just before c1 games.insert(i_c1, c2) elif i_c1 == -1 and i_c2 != -1: # c2 found but not c1: insert c1 after c2 games.insert(i_c2 + 1, c1) else: # both c1 and c2 found: if they are already ordered in the list leave # them where they are, otherwise remove the old location of c1 and put # c1 after c2 if i_c2 > i_c1: games.remove(c1) games.insert(i_c2, c1) def isbigger(c1, c2): """Check whether c1 is bigger than c2.""" i_c1 = -1 i_c2 = -1 for i in range(len(games)): if games[i] == c1: i_c1 = i if games[i] == c2: i_c2 = i return i_c1 > i_c2 def main(): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.settimeout(3) s.connect(("ec2-23-21-19-72.compute-1.amazonaws.com", 6969)) while True: junk = recv_tillreturn(s, 1) c1 = recv_tillreturn(s, 1) c2 = recv_tillreturn(s, 1) print junk, print c1, print c2, c1 = c1.split() c2 = c2.split() if isbigger(c1, c2): guess = 1 else: guess = 2 s.send("%s\n" % guess) answer = recv_tillreturn(s, 4) print answer if "Correct" in answer: if guess == 1: insert(c1, c2) else: insert(c2, c1) else: if guess == 1: insert(c2, c1) else: insert(c1, c2) if save_list: slist = open("/tmp/the_game_list.txt", "w") slist.write(str(games)) slist.close() if __name__ == "__main__": main()
UPDATE: multi_play.py is a multithread version of the above script with other minor changes. By starting 50 parallel threads, it managed to complete the challenge in 1 minute and 30 seconds performing a total of 13000 requests. Not bad at all! 🙂
6 thoughts on “PlaidCTF 2012 write-up: The Game”
I do wonder though, if these are md5 sums of random integers or did the backend program have these values in an array upon which it just looked at the value of the array index and not really care about the md5? Also, I am curious how many iterations it took your script to get to 75/75?
I updated the script to run multiple threads and count the requests number 😉
To answer your questions:
1) “hex-encoded random 17-byte strings” is a quote taken from irc of one of the organizer, so no md5 hash involved in this challenge 🙂
2) this would be interesting to check. I said the script took 3h to get 75/75, but I didn’t mention that my connection has a not-so-good latency. I noticed there are other write-ups for this challenge, where authors claim that their scripts completed in <1h: it would be nice to compare all of them against a local game simulation.
Your solution is far more elegant than mine was. I suspect overall I took longer to do the whole challenge.
Someone in #pctf was saying they’d made a multi-threaded solution (after the CTF was closed) that connected several times. They were able to solve it in 4 minutes!
It was me (lavish is my nickname) 🙂 At the bottom of the post I put a link to the multi-threaded version, give it a try!
Comments are closed.