CySCA 2017: Python: Abstract Syntax Treat writeup

cysca-2017-ast.md

Python: Abstract Syntax Treat

Writeup by @auscompgeek.

Disclaimer: I did not participate in CySCA 2017. I simply saw this challenge (and a number of people struggling over it) and found it interesting. As such, I do not have the full description of the challenge.

Competitors were provided with a file tree.py. I have attached it for prosperity.

Before attempting to solve this challenge, it should be noted (from the shebang line) that this is a Python 2 program.

Step 1: Interpret the AST

The provided Python program contains a dump of a Python AST of another Python program.

Thankfully, there's a PyPI package called astor that can take an AST and dump corresponding Python source code.

How did I know about astor in the first place though? Let's take a tangent for a second.

I have an interest in languages that run on top of other language implementations (e.g. Scala runs on the Java VM). I know of a couple of other languages that run on CPython: dg (a Haskell-inspired language which targets CPython bytecode) and hy (a Lisp that compiles to Python). hy happens to generate an AST to compile down to Python, and uses astor to allow for dumping generated Python source.

#!/usr/bin/python2.7
from ast import *
import astor

tree = Module(...)  # entire AST text dump goes here

print astor.to_source(tree)

Running this with astor 0.5, however, results in an error:

Traceback (most recent call last):
  File "/home/seedbox/ctf/trees.py", line 59, in <module>
    print(astor.to_source(m))
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 40, in to_source
    generator.visit(node)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 493, in visit_Module
    self.visit(stmt)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 189, in visit_FunctionDef
    self.body(node.body)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 99, in body
    self.visit(stmt)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 159, in visit_Assign
    self.visit(node.value)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 48, in newfunc
    func(self, node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 455, in visit_Lambda
    self.write(': ', node.body)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 73, in write
    self.visit(item)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 363, in visit_Call
    self.write(write_comma, arg)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 73, in write
    self.visit(item)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 462, in visit
    self.write(left, node.elt)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 73, in write
    self.visit(item)
  File "/usr/lib/python2.7/site-packages/astor/misc.py", line 161, in visit
    return visitor(node)
  File "/usr/lib/python2.7/site-packages/astor/codegen.py", line 366, in visit_Call
    self.conditional_write(write_comma, '*', node.starargs)
AttributeError: 'Call' object has no attribute 'starargs'

Interestingly enough, ast.Call objects have starargs and kwargs fields in Python < 3.5, however, if they're not specified, the attributes don't exist on the objects, but the compiler doesn't care.

Luckily, the git version of astor does not have this bug. (I initially patched the PyPI version of astor myself, but upon looking into this, I discovered that CPython 3.5 removed these fields in implementing PEP 448, so astor had to be fixed for this change.)

Installing the git version of astor and running our script results in the following code:

def main(value):
    convert = lambda *nums: ''.join(chr(x) for x in nums)
    lib = convert(104, 97, 115, 104, 108, 105, 98)
    attr = convert(109, 100, 53)
    method = convert(100, 105, 103, 101, 115, 116)
    if getattr(getattr(__import__(lib), attr)(value), method)()[::-1
        ] != 'CN\x9f\x1e\xa0\x0e{\x8a\x86\xc4\x8f\xf7\xe6\xf5d\x1d':
        raise ValueError('Wrong value!')

Yay, more obfuscated Python code!

Step 2: Deobfuscating the source

The lib, attr, and method names are simply given as ASCII numbers. Simple to decode, but they've given us the code to do that, so let's just reuse it.

>>> convert = lambda *nums: ''.join(chr(x) for x in nums)
>>> convert(104, 97, 115, 104, 108, 105, 98)
'hashlib'
>>> convert(109, 100, 53)
'md5'
>>> convert(100, 105, 103, 101, 115, 116)
'digest'

Hence, the if condition is basically:

hashlib.md5(value).digest()[::-1] != 'CN\x9f\x1e\xa0\x0e{\x8a\x86\xc4\x8f\xf7\xe6\xf5d\x1d'

The digest() method returns the hash as a bytestring. Notice that the bytestring is also reversed before comparison. So this code is looking for a value whose MD5 hash is:

>>> 'CN\x9f\x1e\xa0\x0e{\x8a\x86\xc4\x8f\xf7\xe6\xf5d\x1d'[::-1].encode('hex')
'1d64f5e6f78fc4868a7b0ea01e9f4e43'

Step 3: Reverse the MD5 hash

Google is your friend.

tree.py

#!/usr/bin/python2.7
import ast
import os


# A text dump of a Python AST.
# This will be parsed into a Python program, then run.

tree = """Module(body=[FunctionDef(name='main', args=arguments(args=[
Name(id='value', ctx=Param(), lineno=1, col_offset=9)], vararg=None,
kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='convert',
ctx=Store(), lineno=2, col_offset=4)], value=Lambda(args=arguments(
args=[], vararg='nums', kwarg=None, defaults=[]), body=Call(
func=Attribute(value=Str(s='', lineno=2, col_offset=28), attr='join',
ctx=Load(), lineno=2, col_offset=28), args=[GeneratorExp(elt=Call(
func=Name(id='chr', ctx=Load(), lineno=2, col_offset=36), args=[
Name(id='x', ctx=Load(), lineno=2, col_offset=40)], keywords=[], lineno=2,
col_offset=36), generators=[comprehension(target=Name(id='x', ctx=Store(),
lineno=2, col_offset=47), iter=Name(id='nums', ctx=Load(), lineno=2,
col_offset=52), ifs=[])], lineno=2, col_offset=36)], keywords=[], lineno=2,
col_offset=28), lineno=2, col_offset=14), lineno=2, col_offset=4),
Assign(targets=[Name(id='lib', ctx=Store(), lineno=3, col_offset=4)],
value=Call(func=Name(id='convert', ctx=Load(), lineno=3, col_offset=10),
args=[Num(n=104, lineno=3, col_offset=18), Num(n=97, lineno=3,
col_offset=23), Num(n=115, lineno=3, col_offset=27), Num(n=104, lineno=3,
col_offset=32), Num(n=108, lineno=3, col_offset=37), Num(n=105, lineno=3,
col_offset=42), Num(n=98, lineno=3, col_offset=47)], keywords=[], lineno=3,
col_offset=10), lineno=3, col_offset=4), Assign(targets=[Name(id='attr',
ctx=Store(), lineno=4, col_offset=4)], value=Call(func=Name(id='convert',
ctx=Load(), lineno=4, col_offset=11), args=[Num(n=109, lineno=4,
col_offset=19), Num(n=100, lineno=4, col_offset=24), Num(n=53, lineno=4,
col_offset=29)], keywords=[], lineno=4, col_offset=11), lineno=4,
col_offset=4), Assign(targets=[Name(id='method', ctx=Store(), lineno=5,
col_offset=4)], value=Call(func=Name(id='convert', ctx=Load(), lineno=5,
col_offset=13), args=[Num(n=100, lineno=5, col_offset=36),
Num(n=105, lineno=5, col_offset=41), Num(n=103, lineno=5, col_offset=46),
Num(n=101, lineno=5, col_offset=51), Num(n=115, lineno=5, col_offset=56),
Num(n=116, lineno=5, col_offset=61)], keywords=[], lineno=5,
col_offset=13), lineno=5, col_offset=4), If(test=Compare(
left=Subscript(value=Call(func=Call(func=Name(id='getattr',
ctx=Load(), lineno=6, col_offset=8), args=[Call(func=Call(func=Name(
id='getattr', ctx=Load(), lineno=6, col_offset=16), args=[Call(
func=Name(id='__import__', ctx=Load(), lineno=6, col_offset=24), args=[
Name(id='lib', ctx=Load(), lineno=6, col_offset=35)], keywords=[], lineno=6,
col_offset=24), Name(id='attr', ctx=Load(), lineno=6, col_offset=41)],
keywords=[], lineno=6, col_offset=16), args=[Name(id='value', ctx=Load(),
lineno=6, col_offset=47)], keywords=[], lineno=6, col_offset=16),
Name(id='method', ctx=Load(), lineno=6, col_offset=55)], keywords=[],
lineno=6, col_offset=8), args=[], keywords=[], lineno=6, col_offset=8),
slice=Slice(lower=None, upper=None, step=Num(n=-1, lineno=6, col_offset=67))
, ctx=Load(), lineno=6, col_offset=8), ops=[NotEq()], comparators=[Str(
s='CN\x9f\x1e\xa0\x0e{\x8a\x86\xc4\x8f\xf7\xe6\xf5d\x1d', lineno=7,
col_offset=15)], lineno=6, col_offset=8), body=[Raise(type=Call(
func=Name(id='ValueError', ctx=Load(), lineno=8, col_offset=14),
args=[Str(s='Wrong value!', lineno=8, col_offset=25)], keywords=[], lineno=8,
col_offset=14), inst=None, tback=None, lineno=8, col_offset=8)], orelse=[],
lineno=6, col_offset=4)], decorator_list=[], lineno=1, col_offset=0)])
"""

def main(user_input):
    """
    Welcome to the Python AST challenge!

    Read a text dump of a Python Abstract Syntax Tree (AST).
    Once you know what the program does, supply the correct value.
    """

    code_obj = compile(tree, '<ast>', 'eval')
    namespace = ast.__dict__.copy()
    compiled_ast = eval(code_obj, namespace)
    executable = compile(compiled_ast, '<code>', 'exec')
    namespace = {}
    # exec executable in namespace
    namespace['main'](user_input)
    return os.environ.get('FLAG', 'flag')