Skip to content

Instantly share code, notes, and snippets.

@Lense
Created March 3, 2015 03:35
Show Gist options
  • Save Lense/2955801424f4adc1c067 to your computer and use it in GitHub Desktop.
Save Lense/2955801424f4adc1c067 to your computer and use it in GitHub Desktop.
Boston Key Party 2015: Sullivan Square solution
# 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
@Lense
Copy link
Author

Lense commented Mar 3, 2015

SOLUTION:XcXFAp9F0Wc8FDHcveFypMWF288i -- d1d y0u tr13 be1ng m04r 2337

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment