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.

6 thoughts on “PlaidCTF 2012 write-up: The Game”

  1. Awesome!

    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?

  2. Ehya!

    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.

    Bye!

  3. 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!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.