PlaidCTF 2012 write-up: The Game

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.
23.22.16.34:6969

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()[3]
		c2 = c2.split()[3]
		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()

Key: d03snt_3v3ry0n3_md5

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! 🙂

Author: Marco Squarcina

Computer Science student and an Open Source enthusiast. My main interests are computer security (especially mandatory access control systems), Linux systems administrations and audio applications. View all posts by Marco Squarcina