Traveling Around Mars With C Emulation (Part 1)

In previous blog posts, we explained how JEB’s custom Intermediate Representation can serve to analyze an executable and perform advanced deobfuscation. Now it’s time to turn to the final output produced by JEB native decompilers: C code¹!

In this series of blog posts, we will describe our journey toward analyzing a heavily obfuscated crackme dubbed “MarsAnalytica”, by working with JEB’s decompiled C code.

To reproduce the analysis presented in this post, make sure to update JEB to version 3.1.3+.

MarsAnalytica Challenge Reconnaissance

MarsAnalytica crackme was created by 0xTowel for NorthSec CTF 2018. The challenge was made public after the CTF with an intriguing presentation by its author:

My reverse engineering challenge ‘MarsAnalytica’ went unsolved at #nsec18 #CTF. Think you can be the first to solve it? It features heavy #obfuscation and a unique virtualization design.

0xTowel

Given that exciting presentation, I decided to use this challenge mainly as a playground to explore and push JEB’s limits (and if we happen to solve it on the road, that would be great!).

The MarsAnalytica sample analyzed in these blogs is the one available on 0xTowel’s GitHub ². Another version seems to be available on RingZer0 website, called “MarsReloaded”.

So, let’s examine the beast! The program is a large x86-64 ELF (around 10.8 MB) which, once executed, greets the user like this:

Inserting a dummy input gives:

So I guess we have to find a correct Citizen ID! Now let’s open the executable in JEB. First, the entry point routine:

Ok, the classic libc entry point, now let’s look at strings and imports:

• 

• 

A few interesting imports: getchar() to read user input, and putchar() and puts() to write. Also, some memory manipulation routines, malloc() and memcpy(). No particular strings stand out though, not even the greeting message we previously saw. This suggests we might be missing something.

Actually, looking at the native navigation bar (right-side of the screen by default), it seems JEB analyzed very few areas of the executable:

To understand what happened let’s first look at JEB’s notifications window (File > Notifications):

Two interesting notifications here: first the file was deemed “malformed/obfuscated”, due to its sections being stripped, and second the analysis style was initially set to CONSERVATIVE.

The CONSERVATIVE analysis style means JEB was cautious during disassembly; it only followed safe control-flow relationships (i.e. branches with known targets), and searched for common routine prologue patterns to find unreferenced routines (e.g. push rbp / mov rbp, rsp)

This likely explains why most of the executable was not analyzed: the control-flow could not be safely followed and the unreferenced code does not start with common prologue patterns.

JEB usually employs AGGRESSIVE analysis on standard Linux executables, and disassembles (almost) anything within code areas (also known as “linear sweep disassembly”). In this case, JEB went CONSERVATIVE because the ELF file looks non-standard (sections are stripped).

Explore The Code (At Assembly Level)

Let’s take a look at the actual main() (first argument of __libc_start_main()):

• 

• 

• 

Ok… that’s where the fun begins!

So, first a few memcpy() to copy large memory areas onto the stack, followed by series of “obfuscated” computations on these data. The main() routine eventually returns on an address computed in rax register. In the end, JEB’s disassembler was not able to get this value, hence it stopped analyzing there.

Let’s open the binary in JEB debugger, and retrieve the final rax value at runtime: 0x402335. We ask JEB to create a routine at this address (“Create Procedure”, P), and end up on very similar code. After manually following the control-flow, we end up on very large routines — around 8k bytes –, with complex control-flow, built on similar obfuscated patterns.

And yet at this point we have only seen a fraction of this 10MB executable… We might naively estimate that there is more than 1000 routines like these, if the whole binary is built this way (10MB/8KB = 1250)!

It should be noted that most of the obfuscated routines re-use the same stack area (initialized in main() with the series of memcpy()).

Disassemble’em All!

To automatically discover more routines, I configured JEB into disassembling “everything” within code areas, i.e. applying an AGGRESSIVE analysis rather than a CONSERVATIVE one ³.

This did not end well, due to an anti-disassembly trick that interleave useless 0xE8 bytes within correct code.

When disassembling linearly, those bytes will be considered as code, because 0xE8 is x86 opcode for the CALL instruction. Hence the disassembly listing ends-up de-synchronized to what will actually be executed:

We could tweak the disassembly algorithm, but at this point we don’t know if there are others hidden “gifts” . Thus, it seems that the most robust option to correctly analyze the whole executable is to find a way to follow the control-flow.

Explore The Code (At C Level)

Let’s now take a look at the pseudo-C code produced by JEB for those first routines. For example, here is main():

The code is (pretty) nice and short! Actually… too short, a lot of the original code is not present in the decompiled code. What happened? Many instructions write values into the stack, and those values will not be re-used later on in the same routine; therefore the instructions have been deemed “useless” and removed.

But those written values will likely be used by the next routines, which share the same stack, as noted earlier. So we need to keep them if we want to have a chance to correctly analyze the code.

This can be done by configuring JEB to not apply “aggressive optimizations” during decompilation ⁴. Here is the new main() decompiled code:

A few lengthy expressions, but it remains pretty decent, given the complexity of the original assembly code: 60 lines of C, most of them simple assignments, to represent around 200 non-trivial assembly instructions.

We Need A Plan

Current Understanding

The executable is divided into (not so small) handler routines, each of them passing control to the next one by computing its address. For that purpose, each handler reads values from a large stack, make a series of non-trivial computations on them, then write back new values into the stack.

After following manually a bunch of the handlers it seems the user input is only processed after a lot of them have been executed.

As originally mentioned by 0xTowel, the crackme author, it looks like a virtual-machine style obfuscation, where bytecodes are read from memory, and are interpreted to guide the execution.

Also, let’s notice that while the executable is impressively obfuscated, there are some “good news”:

• There does not seem to be any self-modifying code, meaning that all the code is statically visible, we “just” have to compute the control-flow to find it.
• JEB decompiled C code looks (pretty) simple, most C statements are simple assignments, except for some lengthy expression always based on the same operations; the decompilation pipeline simplified away parts of the complexity of the various assembly code patterns.
• There are very few subroutines called (more on that in the next blogs), and also few system APIs, so most of the logic is contained within the chain of obfuscated handlers, connected through jmp rax or push rax/ret instructions.

Current Objective

Our first goal would be to find where the user input starts to be processed (typically a call to getchar()), and what is the exact memory state at this point (as we are likely going to need it to solve this madness).

Here Is A Plan

Given all that, we could pass through all the “deterministic” part of the execution (i.e. until the user’s input is processed) by implementing a C emulator.

The emulator would simulate the execution of each handler routine, update a memory state, and retrieve the address of the next handler, which can be described by the following pseudo-code:

emulatorState = initEmulator() // initialize memory
handlerAddress = 0x400DA9 // first handler (known address)
while(true){
  analyze(handlerAddress) // disassemble and decompile
  emulatorState = emulate(handlerAddress, emulatorState)
  handlerAddress = emulatorState.getRAX() // RAX=next handler
}

The program will then produce an execution trace, and provide us access to the exact program’s state. Hence, we should find at some point where the user’s input is processed (typically, a call to getchar()).

The main advantage of this approach is that we are going to work on C code, rather than assembly code. This will become handy later to analyze how the user’s input is processed.

Also, there are a few reasons I decided to go down that (unusual?) road, which have very little to do with MarsAnalytica challenge:

• The emulator would be architecture-independent — several native architectures are decompiled to C by JEB –, allowing us to re-use it in situations where we cannot easily execute the target (e.g. MIPS/ARM).
• It will be an interesting use-case for JEB public API to manipulate C code. Users could then extend the emulator to suit their needs.
• This approach can only work if the decompilation is correct, i.e. if the C code remains faithful to the original native code. In other words, it allows to “test” the decompilation pipeline’s correctness, which is — as a JEB’s developer — interesting!

Nevertheless, a major drawback of emulating C code on this particular executable, is that we need the C code in the first place! Decompiling 10MB of obfuscated code is going to take a while; therefore this “plan” is certainly not the best one for time-limited Capture-The-Flag competitions.

Cliffhanger Ending

How to implement a C emulator with JEB API? Is MarsAnalytica decompiled code correct? Is it really such a bad good plan to use an emulator? Will I perish under performance problems?

Answers to those questions (and more) in part 2!

---