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:
Looks weird huh? So let’s translate it to a saner language so we can get an idea of what this function actually does:
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:
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
This function actually computes the binomial coefficient. So let’s rewrite it in a way such that we avoid recursion:
So now, what about
Well, this is simply a variant of fibonacci capped to
987654321. So, let’s
implement a memoized version:
Now, we see that
bill are mutually recursive. The
solution chosen here consists of rewriting these three functions using a
So there, we have it! The scripts takes a little while to complete but then
you get the flag: