Boston Key Party 2015: Sullivan Square solution

ihateruby.py

# Preface:
#  I'm not putting this online because I think it's a particularly good
#  solution--it's buggy and thrown together. I'm instead uploading it because
#  of the sheer amount of time I spent on it. Making it public makes me feel
#  better for wasting 12 or so hours of my life on this problem, to not even
#  end up getting points for it. 6 of those were after getting the flag, but
#  uppercase instead of lowercase. A significant amount of time was also spent
#  trying to use the built in parser of rubinius to at least dump the rbc
#  instructions, but I have no idea how to write Ruby, and eventually decided
#  it would be easier to rewrite everything rather than do anything in Ruby.
#  It was.
#  I wasn't particularly fond of Ruby before I started this challenge.
#  Now, I hate it.

# There are 4 sections:
#  1. parse rbc files
#  2. parse dump
#  3. graph and print trie structure
#  4. decipher the flag

from string import ascii_lowercase, ascii_uppercase, digits

import pydot

# PART 1 ----------------------------------------------------------------------

def parserbc(s):
	lines = s.split("\n")[::-1]
	lines.pop()
	lines.pop()
	lines.pop()
	ops = list()
	while lines:
		res = parserbcOp(lines, 0)
		ops.append(res)
	return ops

def parserbcOp(lines, depth):
	op = lines.pop()
	#print ">"*depth,"op", op
	if op=="t":
		return True
	elif op=="f":
		return False
	elif op=="n":
		return None
	elif op=="I":
		return int(lines.pop(), 16)
	elif op=="d":
		lines.pop()
		return "some float"
	elif op=="s":
		#string shenanigans
		enc = parserbcOp(lines, depth+1)
		count = int(lines.pop())
		return lines.pop()
	elif op=="x":
		#like s but with :
		enc = parserbcOp(lines, depth+1)
		count = int(lines.pop())
		return ":" + lines.pop()
	elif op=="c":
		lines.pop()
		lines.pop()
		return "some object"
	elif op=="p":
		count = int(lines.pop())
		l = list()
		while count > 0:
			l.append(parserbcOp(lines, depth+1))
			count -= 1
		
		return l
	elif op=="i":
		count = int(lines.pop())
		l = list()
		l.append("instructions:")
		while count > 0:
			l.append(int(lines.pop()))
			count -= 1
		return l
	elif op=="E":
		count = int(lines.pop())
		return lines.pop()
	elif op=="M":
		lines.pop() # version == 1
		code = {}
		code["metadata"] = parserbcOp(lines, depth+1)
		code["primitive"] = parserbcOp(lines, depth+1)
		code["name"] = parserbcOp(lines, depth+1)
		code["iseq"] = parserbcOp(lines, depth+1)
		code["stack_size"] = parserbcOp(lines, depth+1)
		code["local_count"] = parserbcOp(lines, depth+1)
		code["required_args"] = parserbcOp(lines, depth+1)
		code["post_args"] = parserbcOp(lines, depth+1)
		code["total_args"] = parserbcOp(lines, depth+1)
		code["splat"] = parserbcOp(lines, depth+1)
		code["literals"] = parserbcOp(lines, depth+1)
		code["lines"] = parserbcOp(lines, depth+1)
		code["file"] = parserbcOp(lines, depth+1)
		code["local_names"] = parserbcOp(lines, depth+1)
		return code
	else:
		print "unknown op", op
		print "probably end of file--I wouldn't worry about it"

# PART 2 ----------------------------------------------------------------------
# This is from Ryex
#  Arctic Bird of Programming
#  Global Moderator
#  Chaos Ultimate
# http://forum.chaos-project.com/index.php?topic=13708.0
# Since it didn't work, and I had a hard time following what his code did
#  (why did most the functions have __r_ before them?), after 30 or so minutes
#  of trying to fix it I just gave up and rewrote it keeping the helpful
#  number parsing code
# This was also pretty helpful, if really not detailed enough:
#  jakegoulding.com/blog/2013/01/15/a-little-dip-into-rubys-marshal-format
#  For example, "The typecode is followed by the position of the object in the
#  cache table. This cache table is distinct from the symbol cache."
#  ... So how does it work? Fortunately, if you leave all the object links
#  blank you  can still get the structure.
# By the time I wrote this code I was thoroughly sick of Ruby.

TYPE_NIL = '0'
TYPE_TRUE = 'T'
TYPE_FALSE = 'F'
TYPE_FIXNUM = 'i'
TYPE_EXTENDED = 'e'
TYPE_UCLASS = 'C'
TYPE_OBJECT = 'o'
TYPE_DATA = 'd'
TYPE_USERDEF = 'u'
TYPE_USRMARSHAL = 'U'
TYPE_FLOAT = 'f'
TYPE_BIGNUM = 'l'
TYPE_STRING = '"'
TYPE_REGEXP = '/'
TYPE_ARRAY = '['
TYPE_HASH = '{'
TYPE_HASH_DEF = '}'
TYPE_STRUCT = 'S'
TYPE_MODULE_OLD = 'M'
TYPE_CLASS = 'c'
TYPE_MODULE = 'm'

TYPE_SYMBOL = ':'
TYPE_SYMLINK= ';'

TYPE_IVAR = 'I'
TYPE_LINK = '@'

def parseDump(s):
	b = list(s[::-1])
	b.pop()
	b.pop()
	return parseByte(b, list(), list(), 0)

def getNum(b):
	c = ord(b.pop())
	if c > 127:
		c -= 256
	if (c == 0):
		return 0
	if (c > 0):
		if (4 < c and c < 128):
			return (c - 5)
		result = 0
		for i in xrange(c):
			result |= ord(b.pop()) << (8 * i)
		return result
	if (-129 < c and c < -4):
		return (c + 5)
	c = -c
	result = -1
	for i in xrange(c):
		result &= ~(0xFF << (8 * i))
		result |= ord(b.pop()) << (8 * i)
	return result

def parseByte(b, parsedSymbols, parsedObjects, depth):
	# parsedObjects is never used
	objectType = b.pop()
	#print ">"*depth,"type:", objectType
	
	if objectType == TYPE_LINK:
		index = getNum(b)
		return "LINK" + str(index)
		'''
		# I have no clue how this is supposed to work
		if index >= len(parsedObjects):
			print "BAD link to index", index
			print len(parsedObjects), "objects", parsedObjects
			return "LINK " + str(index) + " out of " + str(len(parsedObjects))
		else:
			print "GOOD link to index", index, parsedObjects[index]
		'''
		return parsedObjects[index]
	elif objectType == TYPE_NIL:
		if None not in parsedObjects:
			parsedObjects.append(None)
		return None
	elif objectType == TYPE_TRUE:
		if True not in parsedObjects:
			parsedObjects.append(True)
		return True
	elif objectType == TYPE_FALSE:
		if False not in parsedObjects:
			parsedObjects.append(False)
		return False
	elif objectType == TYPE_FIXNUM:
		num = getNum(b)
		if num not in parsedObjects:
			parsedObjects.append(num)
		return num
	elif objectType == TYPE_BIGNUM:
		return "not implemented"
	elif objectType == TYPE_STRING:
		count = getNum(b)
		l = list()
		while count > 0:
			l.append(b.pop())
			count -= 1
		gotString = "".join(l)
		if gotString not in parsedObjects:
			parsedObjects.append(gotString)
		return gotString
	elif objectType == TYPE_ARRAY:
		length = getNum()
		# ??? 
		parsedObjects.append("arrayhere")
		l = list()
		while length > 0:
			result.append(parseByte(b, parsedSymbols, parsedObjects, depth+1))
			length -= 1
		if result not in parsedObjects:
			parsedObjects.append(result)
		return result
	elif objectType == TYPE_HASH:
		return "not implemented"
	elif objectType == TYPE_USERDEF:
		return "not implemented"
	elif objectType == TYPE_OBJECT:
		#print "parsedSymbols:", parsedSymbols
		objectName = parseByte(b, parsedSymbols, parsedObjects, depth+1)
		#print "name", objectName
		#if objectName not in parsedObjects:
		parsedObjects.append(objectName)
		
		count = getNum(b)
		attributes = {}
		while count > 0:
			key = parseByte(b, parsedSymbols, parsedObjects, depth+1)
			if key not in parsedObjects:
				parsedObjects.append(key)
			value = parseByte(b, parsedSymbols, parsedObjects, depth+1)
			if value not in parsedObjects:
				parsedObjects.append(value)
			attributes[key] = value
			count -= 1
		#print "attributes", str(attributes)
		return {objectName:attributes}
	elif objectType == TYPE_SYMBOL:
		count = getNum(b)
		l = list()
		while count > 0:
			l.append(b.pop())
			count -= 1
		symbol = ":" + "".join(l)
		if symbol not in parsedObjects:
			parsedObjects.append(symbol)
		if symbol not in parsedSymbols:
			parsedSymbols.append(symbol)
		return symbol
	elif objectType == TYPE_SYMLINK:
		index = getNum(b)
		if index >= len(parsedSymbols):
			print "bad symbol index", index
		return parsedSymbols[index]
	elif objectType == TYPE_IVAR:
		obj = parseByte(b, parsedSymbols, parsedObjects, depth+1)
		if obj not in parsedObjects:
			parsedObjects.append(obj)
		count = getNum(b)
		if count != 1:
			#print "IVAR with", count, "instance variables"
			while count > 0:
				iv = parseByte(b, parsedSymbols, parsedObjects, depth+1)
				if iv not in parsedObjects:
					parsedObjects.append(iv)
				count -= 1
		instanceVar1 = parseByte(b, parsedSymbols, parsedObjects, depth+1)
		if instanceVar1 not in parsedObjects:
			parsedObjects.append(instanceVar1)
		instanceVar2 = parseByte(b, parsedSymbols, parsedObjects, depth+1)
		if instanceVar2 not in parsedObjects:
			parsedObjects.append(instanceVar2)

		if instanceVar1 != ":E" or instanceVar2 not in (False, True):
			print "Nonstandard encoding"
		return obj
	else:
		print "bad objectType", objectType, ord(objectType)
		return "???"

# PART 3 ----------------------------------------------------------------------

def traverseTrie(t, depth, graph, key):
	t = t[':Trie::Node']
	if not t.get(":@char"):
		return graph
	cur = depth + "|" + t[":@char"]
	if "good" in str(t.get(":@value")):
		node = pydot.Node(cur, label=cur+"|"+key[t[":@char"]], style="bold")
	elif "LINK" in str(t.get(":@value")):
		node = pydot.Node(cur, label=cur+"|"+key[t[":@char"]])
	else:
		node = pydot.Node(cur, label=cur+"|"+key[t[":@char"]], style="dashed")
	graph.add_node(node)
	if t.get(":@left"):
		if t[":@left"][":Trie::Node"].get(":@char"):
			edge = pydot.Edge(
					cur,
					depth + "l|" + t[":@left"][":Trie::Node"][":@char"])
			graph.add_edge(edge)
		graph = traverseTrie(t[":@left"], depth+"l", graph, key)
	if t.get(":@mid"):
		if t[":@mid"][":Trie::Node"].get(":@char"):
			edge = pydot.Edge(
					cur,
					depth + "m|" + t[":@mid"][":Trie::Node"][":@char"])
			graph.add_edge(edge)
		graph = traverseTrie(t[":@mid"], depth+"m", graph, key)
	if t.get(":@right"):
		if t[":@right"][":Trie::Node"].get(":@char"):
			edge = pydot.Edge(
					cur,
					depth + "r|" + t[":@right"][":Trie::Node"][":@char"])
			graph.add_edge(edge)
		graph = traverseTrie(t[":@right"], depth+"r", graph, key)
	return graph

# PART 4 ----------------------------------------------------------------------

def decipher(ctxt, key):
	return ctxt + " -- " + "".join([key[c] for c in ctxt])

# main ------------------------------------------------------------------------

def main():
	for fn in ("trie", "trie_harder", "cipher"):
		with open(fn + ".rbc", "r") as f:
			s = f.read()
		with open(fn + ".txt", "w") as f:
			for op in parserbc(s):
				f.write(str(op))
				f.write("\n")

	with open("trie.dump", "r") as f:
		s = f.read()
	trie = parseDump(s)
	trie = trie[':Trie'][':@root']
	with open("triedump.txt", "w") as f:
		f.write(str(trie))

	# From trie.txt
	#  ':allocate', 'K', 'D', 'w', 'X', 'H', '3', 'e', '1', 'S', 'B', 'g', 'a',
	#  'y', 'v', 'I', '6', 'u', 'W', 'C', '0', '9', 'b', 'z', 'T', 'A', 'q',
	#  'U', '4', 'O', 'o', 'E', 'N', 'r', 'n', 'm', 'd', 'k', 'x', 'P', 't',
	#  'R', 's', 'J', 'L', 'f', 'h', 'Z', 'j', 'Y', '5', '7', 'l', 'p', 'c',
	#  '2', '8', 'M', 'V', 'G', 'i', ' ', 'Q', 'F'
	idk = "KDwXH3e1SBgayvI6uWC09bzTAqU4OoENrnmdkxPtRsJLfhZjY57lpc28MVGi QF"
	s = ascii_lowercase + ascii_uppercase + digits + ' '
	# This is what I used during the ctf.
	#s = ascii_uppercase + ascii_lowercase + digits + ' '
	# ...
	# Switching two string constants could have put my team into the top 15
	# cipher.txt contains
	#  'a', 'z', ':initialize', ':to_a', 'A', 'Z', ':+', '0', '9', ' ',
	# And when a-zA-Z0-9\  deciphered to valid code, it never occured to me
	#  that one part wouldn't be in the right order, but the rest would be.
	# ...

	# It looked pretty monoalphabetic substitution to me since the encrypt and
	#  decrypt functions are the exact same, so I tried this and it worked.
	key = dict(zip(idk,s))

	# pydot is pretty great
	graph = pydot.Dot(graph_type='graph')
	graph = traverseTrie(trie, "", graph, key)
	graph.write_png('trie.png') 

	# From the graph in trie.png
	print "paths:"
	for ctxt in ("WyXcXAFAp9F0Wc8FDHcveFypMWF288i",
			"WD6A01IvFSCF3IWFvIIDC",
			"WDwTFcqFHMqAF2FW8MX",
			"WDwM6WpVpvcA",
			"WyM0qFSVFyAF18Wp",
			"WyXcXAp9FWMXMW8FAp9WFW9DA",
			"WyXcXAFAp9F0g1MTXFciFA80",
			"WyXcXAFAp9F0gvpzF0Wc8XFvpiFD8cvGFKFvppD",
			"WD8wM9VHFciF9CHCFaabyF01cVFyHMvqFC688X",
			"KDwXH3e1SBgayvI6uWC09bzTAqU4OoENrnmdkxPtRsJLfhZjY57lpc28MVGi QF"):
		decipher(ctxt, key)
	print "\nSOLUTION:" + decipher("XcXFAp9F0Wc8FDHcveFypMWF288i", key)

main() # eh

SOLUTION:XcXFAp9F0Wc8FDHcveFypMWF288i -- d1d y0u tr13 be1ng m04r 2337