magicbox was a simple VM reversing challenge from TetCTF 2022.

Description

My machine is running very simple, can you understand it?

Files:

• magicbox.zip (extract password TetCTF-7c71accd8175c365688a233a14fc4a1a)

I’d like to take a moment to say Google Drive downloads suck! There’s no easy way to download this from the terminal. If you’re a CTF organizer, please take note!

Reversing

We’re given a Windows PE32 (yuck). The challenge description strongly suggests some kind of VM.

The startup code for Windows binaries is a lot more convoluted than the glibc call to __libc_start_main we’re used to. I’m not that experienced in Windows reversing, but entry calls FUN_004010ad and later exits with its return value as the exit code, so that’s probably main. With a bit of renaming and retyping, the decompilation is rather clean. Here it is, with some hand-rewriting.

This VM only has one instruction: NOR. An instruction is made up of three numbers a, b, and c, and the NOR instruction sets mem[c] <- mem[a] NOR mem[b]. Jumps are possible because PC is at mem[0], which can be written to.

Disassembly

My immediate thought was to just reimplement the VM and output some basic disassembly. First, I dumped the entire prog into a file. Since I already had most of the C code, I just added a bit of extra code to load the program into memory and run it. I chose not to just put prog in my code because I expected to do further analysis on it in the future (spoiler alert: I didn’t!).

With a working VM, it’s easy to add fprintfs to print every instruction. Here’s the format I chose:

From here on out, [a] denotes mem[a], and a is just the number a. Here’s the first bit of the code—the part that prints Password:

Interpreting Disassembly

This is obviously quite different from regular assembly, so understanding it is difficult. However, we’ll be able to identify some common patterns that will make our life easier.

Input

We can figure out how long the flag is by just checking how many times scanf is called. It turns out the answer is 26. Let’s input our favorite 26-character string, ABCDEFGHIJKLMNOPQRSTUVWXYZ, and investigate how it stores the input.

This repeats many times. Immediately, we notice some patterns:

1. mem[7] is used as a temporary variable very often
2. not is accomplished with x x y, which is mem[y] = ~(~x | ~x) = x
3. mov is accomplished with x x 7; 7 7 y, which, when combined with #2, is mem[y] = mem[x]
4. jmp is accomplished by moving to mem[0]

The first character of the input is stored at mem[6691], and the last is stored at mem[6716].

First Check

Right after the last character is read and stored, the program starts checking the input.

Notice how it accesses mem[6691], which is the first character of our input. By carefully tracing the instructions, we can start to understand what is happening.

We can make use of DeMorgan’s Laws to simplify this:

Aha, this is simply ([6691] ^ 87) | [494]! This section of code essentially boils down to:

We will see this method of computing XOR again.

Second Check

Let’s move on to the second character. Remember, it’s stored at 6692.

We’ve seen a lot of these patterns already, so I won’t write everything out in full this time.

This second check is just:

Correct State

With a VM this simple, there’s not a whole lot you can do to check an entire flag. We can reasonably assume that every check will OR mem[494] with some combination of XORs, and then check if it’s 0 at the end. We can verify this by skipping down to the end of the disassembly.

This repeats several times. Recall that mem[1] contains the result of the NOR, rotated left by one bit. This section essentially ORs mem[494] with all the rotations of itself. Thus, if any bit of this is 1, then the number will be 65535 by the end. This is then presumably used to jump to one of two places, but we don’t really have to worry about that. In our VM, let’s just set mem[494] at an appropriate location.

Now, we run it with our favorite input.

Cool! So now that we’ve identified the success condition, we know that all our XORs have to equal 0. We’ve already gathered the following:

From this, we can deduce the first two characters of the flag: WE.

Pintools Cheese

We could continue to reverse all the checks. It is much of the same, but would probably take a long time. Instead, we’ll employ another strategy that, from what I can tell, most other teams also used. We know mem[494] has to be 0 at the end, and it seems to check characters in order, so let’s just print the number of times 0 is written to mem[494]. We’ll also get rid of the other outputs while we’re here.

Let’s try it out.

Success! Now, we can just brute force every character sequentially.

Uh-oh. There’s no flag. But wait, shouldn’t that : be a for “virtual machine?”

Aha! Looks like more than one character works sometimes. This calls for a… tree search!

There’s the flag!