0ctf 2016 writeup for VM challenge(reverse 7 pts)

Categories CTF

This is a write-up for the 0ctf 2016 quals “VM” reverse challenge worth 7 points.

The main process of solving this challenge contains 3 phase:

  1. Find the location of input check algorithm
  2. Reverse input transform algorithm
  3. profit

I wasted much life in the second phase. This function is flattend by a big switch structure and contains a lot of goto instruction. It’s hard to reverse such a function statically, So we use dynamic analysis and black box analysis. we make a few assumptions on the transform pattern. We can reverse the algorithm without understanding  assembly or decompiled code.

The keygen algorithm is implemented in some VM which leverages dynamic loading of shared libray and function relocation, but this part is of less interest. Our target is the input check algorithm. The following is the analysis result in pseudo-C.

Unfortunately, transform_input() is highly obfuscated.

Intuitively, I set hardware W/R breakpoint on user input(0x1234fd90) and script to dump this area once upon a hit. The output is like this:

Observing the data tracing, only 2 bytes at most are transformed each time.

We made two assumption: 1. the transform algorithm is deterministic 2. the transform algorithm is a one-to-one mapping.

There are more then 130 round of transformation. We assume each round of the transform is a one-to-one mapping, and only the following six operation is applicable:

  1. newpos[i] = oldpos[i] + pos[j]
  2. newpos[i] = oldpos[i] –  pos[j]
  3. newpos[i] = oldpos[i] ^ pos[j]
  4. newpos[i] = oldpos[i] +   c
  5. newpos[i] = oldpos[i] ^   c
  6. switch the location of pos[i] and pos[j]

Given how the input is transformed in each round, we can find many possible operations. The remaining problem is how we choose the right operation from many candidates. We can change input and calculate the intersection set  of two operation set, iterate this process until only one candidate remained.

After getting the transform operation of each round, things turned easy, just do the inverse-transform on the flag_transformed array and we can get the flag:

Due to some error what I got initially is 0utf{Mipsel_Virtual_MachineM><} , as we know the flag format, and most of it looks meaningful, I just bruteforce on the last three bytes and I was lucky, the real flag is :


I did’t find an elegant solution to this challenge, the process is full of assumptions and dirty hack. And I was lucky.


do inverse-transform:


No Comments

Leave a Reply