Reverse Engineering of Malbolge Programs

In this tutorial, we crack zb3's crackme (mirror). For that purpose, we need the help of Malbolge disassembler to transform the crackme into HeLL code, which is easier to understand and can be debugged using the HeLL IDE. In order to create HeLL code, the debugger needs to run the Malbolge program. It can only generate HeLL code for those parts of the program that are actually executed. Since we don't want to crack the key by brute-force, we only give one input to the disassembler:

Thus, we won't get a disassembly of the code that is executed if the correct passphrase is entered.
Remark: The original source code of the crackme (without the key) is available on github. However, using the original source code feels like cheating. Hence, we won't look at the source.

After we got the disassembled crackme, we open it with HeLL IDE for debugging.

When looking at the disassembled code, we can see that the program contains a long chain of RNop commands in the .CODE section and a huge area of unused cells in the .DATA section. The missing cells may contain the code to print out the success message. If our assumption is correct, these cells seem to be unused, just because we didn't execute them during the disassembling process.
Remark: A later analysis (which won't be described here) shows that the code for printing out the success message is located somewhere else. The huge amount of ?- cells is a result of the RNop chain, which again is the result of a poor U_-prefix usage in the original HeLL source of the crackme.

Before we start debugging, we should transform the labels of the .CODE section into more legible ones using find and replace. The MovD commands are used for program flow, so we don't care about them now. We are interested in data manipulation, which means Rot and Opr are the most important commands for us. The result can be downloaded here: disassembled crackme with improved code labels.

Now we are ready to start debugging with HeLL IDE. When stepping through the crackme, we see how the welcome message is generated charatcer by character: every single character is loaded by a Rot command and then printed out. Afterwards, the program waits for user input. We should provide the same input as used during disassembling, because running into non disassembled regions may crash the program or lead to undefined behavior. Thus, we enter the following character into the HeLL IDE's terminal (and press return afterwards).

Then, we can continue stepping through the program (we don't care about the MovD commands during this process). We observe that the A register, which holds our user input, is stored into two memory cells one after the other by the Opr command. Both cells were initialized with C1 before. This is a typical Malbolge programming technique for storing the original character into the second cell (see here). We label the second cell value (i.e. we change the source code and restart debugging afterwards) and set a breakpoint at that cell. The label allows us to watch the content of the cell in HeLL IDE. Therefore we add [value] to the right side of HeLL IDE.

When we continue stepping through the program, we observe the following actions:

C2 is loaded by Rot command and then written into the cell labeled value by Opr command.
C0 is loaded and written into value.
0t2222202002 is loaded (by Rot C1 and Opr 0t2222202002) and written into value (see Figure 1).
The result is written into two further cells that hold the initial value C1 by Opr.

Figure 1: The value 0t2222202002 is written into value then.

We label the second cell the result is finally written to by value2, set a second breakpoint, stop and start debugging, and add [value2] to the list of observed memory cells. You can download the disassembled code with these two labels here: disassembled crackme with improved labels

We observe that, after the first access to value2, the following actions are performed repetitively:

Opr of C1 into value,
Opr of C2 into value,
Rot of [value2],
Opr of the result into value,
Opr of C1 into value.

Remember the file example_cat_halt_on_eof.hell that comes with LMAO. In that example, the same sequence is used to test whether a value equals C2.

Let's summarize the behaviour of the crackme we observed so far:
0t2222202002 ! (C0 ! (C2 ! input)) is tested against C2, where ! denotes the Opr command. Thus, it seems reasonable to construct a user input that will pass the test.

Applying Opr with 0t2222202002 into a given value will result in C2 if and only if the value had been 0t1111121221 before. Thus, we are looking for an input character that satisfies C0 ! (C2 ! input) = 0t1111121221. The following table shows how differnet trits of the input are transformed by these two Opr commands.

input	C2 ! input	C0 ! (C2 ! input)
0	0	1
1	2	2
2	1	1

The operation C0 ! (C2 ! input) transforms every 0 and every 2 of the input into a 1. On the other hand, every 1 will be transformed into a 2. Consequently, the input we are looking for is 0tXXXXX1X11X, where each X is either a 0 or a 2.

Since Malbolge reads input as an 8-bit character, the range of possible input characters goes from 0 to 255 (plus C2 for EOF). Thus, the following input characters satisfy the test performed by the crackme: 0t10110, 0t10112, 0t12110, and 0t12112. Only the first two characters are ASCII characters (range from 0x00 to 0x7f): ']' and '_'.

Let's restart the debugger in HeLL IDE and type one of these characters when asked. Doing so, the disassembled Malbolge program crashes. This happens because the progran flow is reaching code regions that are not present in the disassembled HeLL code since the disassembler hasn't seen them. Probabliy we have reached a new branch that we have not visited during disassembling. This indicates that we were successful.

Let's find out whether this is the password or further transformations are performed in the non disassembled code of the crackme. Therefore, we execute the original crackme.mb with a Malbolge interpreter and type ] (or _), followed by return. The output of the crackme is as follows.

Pass: g00dj06

That's it. We succeeded.