Language selection: Deutsch / English

Reverse engineering of Malbolge programs

As an example we try to crack zb3's crackme (mirror) here.

We use the Malbolge disassembler to transform the crackme into HeLL code. Note that we won't get the code executed when the correct passphrase is entered, because the disassembler outputs only the code it has executed with our interaction. We don't want to crack the key by brute-force, so the only input we try with the disassembler is 0.
Annotation: The source code of the crackme (without the key) is available. However, using the original source code feels like cheating, so we won't take a look at the source.

Now we can use HeLL IDE to debug the program. We open the disassembled file with HeLL IDE.

We see that the program contains a long RNop chain in the .CODE section and a huge area of unused cells in the .DATA section. Probably the unused cells contain the code to print out the success message in the original crackme. They seem to be unused, because we did not run the disassembler with the correct passphrase.
Annotation: 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 and block-splitting of the Malbolge disassembler. The extremely long RNop chain is the result of a poor U_-prefix usage in the original HeLL source of the crackme.

Before we will start debugging, we should transform the labels in 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. Afterwards we start debugging and step through the the program. We see how the welcome message is generated. Every single character is loaded by 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). Then we continue stepping through the program, ignoring the MovD commands. We see that the input character is crazied into two fields by Opr, which have been initialized with C1. This is done to get the original character stored in the second field (see here). We set a breakpoint at the second field and label it with "value", so we can watch it in HeLL IDE. To apply the renaming we have to stop and then start the debugging mode again. Now we can 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 see the following:
C2 is loaded and crazied into value.
C0 is loaded and crazied into value.
0t2222202002 is loaded and crazied into value (see Figure 1).
The result is crazied into two further fields with initial value C1. We will name the second of them value2. Let's set a breakpoint here, stop and start debugging, and add [value2] to observed memory cells.

We see that, after the first access to value2, the following sequence is repeated many times:
crazy C1 into value,
crazy C2 into value,
rotate value2,
crazy the result into value,
crazy C1 into value.
We remember the file example_cat_halt_on_eof.hell from LMAO. There, the above sequence is used to test whether a value is C2 or not.

We can summarize the behaviour of the crackme so far:
0t2222202002 ! (C0 ! (C2 ! input)) is tested against C2, where ! denotes the crazy operation.
Let us construct an input value that satisfies the condition.

Figure 2: Crazy operations performed on the input.

Therefore, we consider the input tritwise.
(C0 ! (C2 ! input)) transforms every digit of the input that is 0 or 2 into 1. Every 1 will be transformed into a 2.
The crazy operation of 0t2222202002 into [D] will result in C2, iff [D] has been 0t1111121221 before.
So we are looking for an input character that satisfies (C0 ! (C2 ! input)) = 0t1111121221. Therefore, the input must be 0tXXXXX1X11X, where each X is either 0 or 2 (cf. Figure 2).
Since we can only make input in range 0-255 (plus EOF = C2), the input should be 0t10110, 0t10112, 0t12110, or 0t12112.
Because only the first two numbers correspond to ASCII characters, we conclude that the correct input character is ] or _.

So, let us restart the debugger in HeLL IDE and type one of these characters when asked. We step through the program again. After a while, [value] becomes C2 and then it becomes C2 again and again. Then suddenly the Malbolge program crashes.
This may be caused by reaching code regions that has not been disassembled by Malbolge disassembler. Probabliy we have entered a new branch we have not visited during disassembling. This indicates that we were successful.

Let's find out, whether this is the complete password or there are more characters read and checked. We execute the original crackme.mb with a Malbolge interpreter and type ] (or _), followed by return. The output is Pass: g00dj06. That's it. We succeeded.