Reverse Engineering of Malbolge Programs

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

0

Therefore, we will not get a disassembly of the code that is executed when 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, so we will not look at it.

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 large area of unused cells in the .DATA section. These cells might contain the code that prints the success message. If that assumption is correct, they appear unused simply because we did not execute them during disassembly.
Remark: A later analysis (which will not be described here) shows that the code for printing the success message is located somewhere else. The large number of ?- cells is a result of the RNop chain, which in turn is the result of poor U_-prefix usage in the original HeLL source of the crackme.

Before we start debugging, we should replace the auto-generated labels in the .CODE section with more readable ones using find and replace. The MovD commands handle program flow, so we can ignore them for now. We are interested in data manipulation, which means Rot and Opr are the most important commands. 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 character by character: every character is loaded by a Rot command and then printed. Afterwards, the program waits for user input. We should provide the same input that was used during disassembly, because running into non-disassembled regions may crash the program or lead to undefined behavior. So, we enter the following character into the HeLL IDE terminal (and press Enter afterwards).

0

Then, we can continue stepping through the program (we can skip the MovD commands). We observe that the A register, which holds our user input, is written into two memory cells in succession by the Opr command. Both cells were initialized with C1 beforehand. This is a typical Malbolge programming technique for storing the original character in the second cell (see here). We label the second cell value (i.e., we edit the source code and restart debugging), then set a breakpoint at that cell. The label allows us to watch the cell's content in HeLL IDE, so we add [value] to the right-hand panel.

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.

We label the second destination cell value2, set a second breakpoint, restart the debugger, and add [value2] to the list of observed memory cells. The disassembled code with these two labels can be downloaded 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.

To summarize what we have observed so far:
0t2222202002 ! (C0 ! (C2 ! input)) is tested against C2, where ! denotes the Opr command. It is therefore reasonable to construct a user input that will pass this 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 different 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 of these are ASCII characters (range 0x00–0x7F): ']' and '_'.

Let us restart the debugger in HeLL IDE and type one of these characters when prompted. The disassembled Malbolge program crashes. This happens because the program flow reaches code regions that are absent from the disassembled HeLL code, since the disassembler never executed them. We have probably reached a new branch that was not visited during disassembly — which indicates that we have found the correct input.

Let us find out whether this is the password or whether further transformations are performed in the non-disassembled code of the crackme. We run the original crackme.mb with a Malbolge interpreter and type ] (or _), followed by Enter. The crackme outputs:

Pass: g00dj06

That is it — we succeeded.