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. Thus, we won't get a disassembly of the code that is executed when the correct passphrase is entered. Since we don't want to crack the key by brute-force we give only one input to the disassembler: 0.
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 take a look at the source.

After we got the disassembled crackme by Malbolge disassembler, we open it with HeLL IDE to debug it.

When we look at the disassembled code, we 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. Maybe the unused cells contain the code to print out the success message. If this assumption is correct, these cells only seem to be unused, because we were not able to run them during the process of disassembling due to lack of the correct passphrase.
Remark: A later analysis (which won't be described here) shows that the success message is printed out somewhere else. The huge amount of ?- cells is a result of the RNop chain, which again is the result of a very 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 readible labels by find and replace. The MovD-commands are used for program flow, so we don't care about them. 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 program, we see how the welcome message is generated. Every single character is loaded by a Rot command and then printed out. Afterwards, the program waits for user input. We enter the character 0 at the HeLL IDE's terminal (and press return). We should only give the input used during disassembling, because stepping into non-disassembled regions may crash the program or lead to undefined behavior.

After we have given the input to the program, we continue stepping through the program (we do not care about the MovD commands during this process). We see that the input character, which is stored in the A register, is written consecutively into two memory cells by the Opr command. Both cells were initialized with C1 before. This is a typical Malbolge programming technique to store the original character into the second cell (see here). We label the second cell with "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.

Figure 1: The value 0t2222202002 will be crazied into [value] next.

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 with initial value C1 by Opr.

We label the last cell the result is 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 see 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 this example, the same sequence as above is used to test whether a value equals C2.

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

The final Opr of 0t2222202002 into [D] will result in C2 iff [D] has been 0t1111121221 before. Thus we are looking for an input character that satisfies (C0 ! (C2 ! input)) = 0t1111121221. The Opr (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 must be 0tXXXXX1X11X, where each X is either a 0 or a 2.

Since Malbolge reads the input as 8 bit character, the range of input characters goes from 0 to 255 (plus C2 for EOF). Thus, only an input of 0t10110, 0t10112, 0t12110, or 0t12112 will satisfy the test performed by the crackme. Only the first two numbers correspond to ASCII characters. By decoding to ASCII characters, we can conclude that the correct input character is ] or _.

Let us restart the debugger in HeLL IDE and type one of these characters when asked. After a while the Malbolge program crashes suddenly. This may happen when reaching code regions that are not present in the disassembled HeLL code since the disassembler has not 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 already or further steps are performed in the newly discovered branch of the crackme. Therefore execute the original crackme.mb with a Malbolge interpreter and type ] (or _), followed by return. The output of the crackme is Pass: g00dj06. That's it. We succeeded.