Tags: obfuscated decompile brainfuck 

Rating: 0

**Description**

> We managed to exfiltrate an android application from Wooble's employee. He called himself the magician, and, as per what we have read, left a secret to find for anyone who could discover it. We struggled with this for a while, and now we want to leave this one to you. Good luck.

**Files provided**

- [book.apk](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-08-HackIT-CTF/files/book.apk)

**Solution**

First we need to decompile the APK; we can use an [online tool](http://www.javadecompilers.com/apk) to do this.

We can ignore a lot of third-party libraries and stuff for visual presentation and focus on these two classes:

- [hackit.secretkeeper.altair.MainActivity](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-08-HackIT-CTF/files/magician-main.java)
- [hackit.secretkeeper.altair.Magix](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-08-HackIT-CTF/files/magician-magix.java)

In `MainActivity` we see what happens to whatever we type into the text box:

```java
// output view
TextView textView = (TextView) MainActivity.this.findViewById(C0323R.id.textView1);

// input
EditText editText = (EditText) MainActivity.this.findViewById(C0323R.id.editText1);

// "encryptor" from the website?
JSONObject jSONObject = new JSONObject(MainActivity.this.run("encryptor"));

// create a string from encryptor + input
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(jSONObject.getString("p"));
stringBuilder.append(editText.getText());

// use Magix to do "magic" on the created string using the "encryptor" result
String encode = URLEncoder.encode(
new Magix(100000, new ByteArrayInputStream(
stringBuilder.toString().getBytes(StandardCharsets.UTF_8)
)).doMagic(jSONObject.getString("result")),
"utf-8"
);

// send the magic output to the website as ?spell=<output>
MainActivity mainActivity = MainActivity.this;
StringBuilder stringBuilder2 = new StringBuilder();
stringBuilder2.append("?spell=");
stringBuilder2.append(encode);

// get result from the JSON output of the website
textView.setText(new JSONObject(mainActivity.run(stringBuilder2.toString())).getString("result"));
```

First things first, `MainActivity.this.run(url)` requests data from a web site located at `http://185.168.131.121/`. If we look at the "encryptor" URL ourself, we get this result:

```json
{
"result": "dzdakazzlzlkkkoczzzakkklzzzoczzzllllllllaokkkkkaozzlkkaozzozlkczzaozzzzlkkckkkkczzzaokkklzzzckkaozlkaozozlzzzzzczaozzzzzlzzckkkkkkkkczzaokklzzczzzaozzlkkczazaokozckaozlkcczaaockkkaozlzokkczaoklzclzlllllllaokaozzllkkczzaokklzzckckaozzzzlkkkkczzckkkczzzzzyaockkkkkkkkkkdc",
"p": "\u0010"
}
```

Now let's have a look at `Magix`. The core is the `doMagic` function, which we can summarise as:

```java
protected void doMagic(char c, char[] cArr) throws Exception {
switch (c) {
case 'a':
// ... if data at data pointer is zero, continue after the matching `c`
case 'c':
// ... jump back to matching `a`
case 'd':
// ... read a byte from user input and write at data pointer
case 'k':
// ... decrease data pointer (move to the left)
case 'l':
// ... increase value at data pointer
case 'o':
// ... decrease value at data pointer
case 'y':
// ... output byte at data pointer
case 'z':
// ... increase data pointer (move to the right)
}
}
```

Familiar at all?

This is a [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck) interpreter, with 100000 8-bit cells of memory, errors on out-of-bounds data access, and a modified character set:

| Brainfuck | `Magix` | Function |
| --- | --- | --- |
| `>` | `z` | increase data pointer (move to the right) |
| `<` | `k` | decrease data pointer (move to the left) |
| `+` | `l` | increase value at data pointer |
| `-` | `o` | decrease value at data pointer |
| `.` | `y` | output byte at data pointer |
| `,` | `d` | read a byte from user input and write at data pointer |
| `[` | `a` | if data at data pointer is zero, continue at the matching `c` |
| `]` | `c` | jump back to matching `a` |

We can try to reverse engineer what the "encryptor" code does, but reversing Brainfuck code is a very painfull process. Instead, we can write our own interpreter and see what it does for various inputs and outputs.

Whatever string we give the encryptor, we get one of the same length, but the characters are all replaced. However, the same character in the input always corresponds to the same character in the output. And even better, the code is actually a symmetric cipher, so:

```
encryptor("\u0010" + encryptor("\u0010" + someText)) == someText
```

(The `\u0010` byte is added by the application prior to encoding.)

Whatever we encrypt then gets sent to the website, but for a lot of inputs the website simply responds with "bad wolf". With some luck, however, we can get an input like:

```
input: "l"
encoded: "|"
website output: "||||||||||q\x7Fs"
decoded: "llllllllllaoc"
```

The code doesn't really do anything, but it's interesting that it increases the value at the data pointer to 10, i.e. the newline character. That made me think that when we run the code output by the website, it prints out the output of the command we tried.

The codes that the website accepts are actually only valid `Magix` codes, i.e. Brainfuck programs. So if our `Magix` code gets executed by the server, we can try out some options to get the flag:

- dump (part of) the contents of the memory
- dump memory to the left (assuming the data pointer was not at `0` to begin with)
- read input characters and print them

The first two just displayed empty memory, but the third one worked:

```
input: "dydydydydydydydydydydydydydydydydydydydydydydydydydydy" ...
encoded: "tititititititititititititititititititititititititititi" ...
website output:
"||||||||||qj||||||||||j|||||||||||j||||||||||||j|||||j||||||j|||||||||||||j{{{{{"
"{{\x7Fsj||ij\x7F\x7Fi{\x7F\x7F\x7F\x7F\x7Fij\x7F\x7F\x7F\x7F\x7Fij|||i{{|ijj\x7F"
"\x7F\x7F\x7F\x7F\x7F\x7F\x7F\x7Fi{{\x7Fij||ij\x7F\x7F\x7F\x7Fi{\x7F\x7F\x7Fij|||"
"||||i{{||ij|||||i{\x7F\x7F\x7F\x7Fij\x7F\x7Fij\x7F\x7Fi{{ij|||||i|ij|i{{i||||||i"
"j\x7Fi{\x7F\x7Fijj\x7F\x7Fi|||||||i{||i||||i{||||||ij\x7F\x7F\x7F\x7F\x7Fi\x7Fi{"
"\x7F\x7F\x7F\x7F\x7F\x7F\x7F\x7F\x7F\x7Fijjj\x7Fij\x7F\x7F\x7Fi{|i|iji{\x7F\x7F"
"\x7Fi||i\x7Fi\x7Fi|||iji{\x7Fi|i\x7F\x7Fi{||||ijjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiii"
"iiiiiiiii"
decoded:
"llllllllllazllllllllllzlllllllllllzllllllllllllzlllllzllllllzlllllllllllllzkkkkk"
"kkoczllyzooykoooooyzoooooyzlllykklyzzoooooooooykkoyzllyzooooykoooyzlllllllykklly"
"zlllllykooooyzooyzooykkyzlllllylyzlykkyllllllyzoykooyzzooylllllllykllyllllykllll"
"llyzoooooyoykooooooooooyzzzoyzoooyklylyzykoooyllyoyoylllyzykoylyooykllllyzzzzyyy"
"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy"
```

And upon executing that last bit:

`flag{brainfuck_is_not_encryption_19239021039231}`