Last November, I participated to the 9447 CTF, a Jeopardy-style competition. One of the reverse engineering challenge was named “danklang”.

Contestants were given a script written in a weird language named “danklang”. A quick search on the web and you find out that this language appears to be a subset of greentext, a language inspired by dank memes. The flag is the result of running this script with 13379447 as input.

Here is an excerpt of the code:

>wewlad fail(memes, calcium)
        >be dank like :^)
        >implying calcium < memes
                >implying memes % calcium is 0
                        >be dank like :^(
                >or not
                        >wew fail(memes, calcium + 1)
                        >be dank like wew
                >done implying
        >done implying
        >tfw dank

Looks weird huh? So let’s translate it to a saner language so we can get an idea of what this function actually does:

def fail(memes, calcium):
    dank = True
    if calcium < memes:
        if memes % calcium == 0:
            dank = False
        else:
            dank = fail(memes, calcium+1)
    return dank

Since the greentext interpreter is not able to compute the flag, the first step to solve this challenge is obviously to translate the whole script into a saner programming language. Here is a version translated to python.

Considering you had a look at the code snippet above, you probably noticed the recursion. In fact, there is no loop in the whole code and pretty much everything is based on recursions! And everyone knows that Python does not like recursive functions. Actually, if you try to run the Python script, you will hit this error rather quickly: RecursionError: maximum recursion depth exceeded in comparison. So obviously, the next step into solving the challenge is to optimize this piece of code so it can deliver a result (the flag).

My first attempt started with a rewrite in Go because, well, Go is a nice language and it performs better than Python, so why not? I then started to optimize the code but then figured out that I had to deal with very large numbers so I switched back to Python. If you ever attempted to use math/big, you can easily understand why: it’s a pain to write code using math/big. Python abstracts dealing with large numbers very well and CTFs are supposed to be fun!

In order to optimize the code, the first step is understanding what it’s actually doing. The code snippet I shared above is actually a primality test. Hence, I rewrote it so it can perform better:

def fail(memes):
    if memes%2 == 0:
        return False
    limit = int(math.sqrt(memes))+1
    for i in range(3, limit, 2):
        if memes%i == 0:
            return False
    return True

I could probably have used something more sophisticated, like the Miller-Rabin primality test but for all intent and purposes, this simple function was enough.

As I started rewriting functions that do no call any other, the next step was to optimize dootdoot:

def dootdoot(memes, seals):
    doritos = 0
    if seals <= memes:
        if seals == 0:
            doritos = 1
        else:
            if seals == memes:
                doritos = 1
            else:
                doritos = dootdoot(memes-1, seals-1)
                doritos += dootdoot(memes-1, seals)
    return doritos

This function actually computes the binomial coefficient. So let’s rewrite it in a way such that we avoid recursion:

def dootdoot(n, k):
    res = 1
    if k > n-k:
        k = n-k
    for i in range(0, k):
        res *= n-i
        res = res // (i+1)
    return res

So now, what about brotherman?

def brotherman(memes):
    hues = 0
    if memes != 0:
        if memes < 3:
            hues = 1
        else:
            hues = brotherman(memes-1) + brotherman(memes-2)
    return hues % 987654321

Well, this is simply a variant of fibonacci capped to 987654321. So, let’s implement a memoized version:

memo = [0]*13379447
memo[0] = 1
memo[1] = 1
for i in range(2,13379447):
    memo[i] = (memo[i-2]+memo[i-1]) % 987654321

def brotherman(n):
    return memo[n-1]

Now, we see that epicfail, such, and bill are mutually recursive. The solution chosen here consists of rewriting these three functions using a state machine.

def epicfail(memes):
    wow = 0
    next = "epicfail"
    for n in range(memes, 1, -1):
        if next == "epicfail":
            if fail(n):
                wow += 1
                next = "bill"
            else:
                next = "such"
        elif next == "such":
            dd = dootdoot(n, 5)
            if dd%7 == 0:
                next = "bill"
                wow += 1
            else:
                next = "epicfail"
            wow += dd
        else: # next == "bill"
            bm = brotherman(n)
            if bm%3 == 0:
                next = "such"
                wow += 1
            else:
                next = "epicfail"
            wow += bm
    return wow+1

So there, we have it! The scripts takes a little while to complete but then you get the flag: 9447{2992959519895850201020616334426464120987}.