#11 – covfefe.exe

Wait, “covfefe”? What does that even mean?  Jokes and memes aside that’s indeed the name of the binary for the 11th challenge. The task description reads:

Only two challenges to go. We have some bad hombres here but you’re going to get the keys out.

The binary requests a password on running.

Providing an incorrect password displays a humorous message.

Analyzing IDA

Let’s have a quick look in IDA.

IDA identifies only a handful of functions. The purpose of the function name exec_instruction  and exec_vm  will be explained a bit later. The call flow graph is simple as well.

The entry function start  calls exec_vm  which in turns calls exec_instruction. Apart from this, we can observe calls to time, rand, srand , printf  and scanf.

start seeds the random number generator with the current time. arr is an array of DWORDs. A random number modulo 8 is then stored at arr[273]. Lastly, it calls exec_vm  passing the array as a parameter. The second argument is the size of the array.

Let’s have a look at the decompiled code of exec_vm .

The code fetches three consecutive elements from the array and passes it to the exec_instruction  function. The return value decides the next three elements be passed at the next call. All of this is wrapped in a while loop. The experienced eye will immediately recognize this as the dispatch stub used in virtualization based code protection.  Let’s have a look at exec_instruction.

The function subtracts array[i] from array[j] storing the difference back in array[j] . If the third parameter passed is non zero, it returns the comparison of difference <= 0. The virtual machine instruction set comprises of only a single instruction and referred to as One Instruction Set Computer (OSIC). The algorithm implemented is Subleq.

Writing the Subleq in Python

The logic is simple enough to be implemented in Python. The bytecode for the VM is located at 403008 and can be extracted using IDA Python.

The code for the emulator is as follows

from __future__ import print_function 
from vm import code import random 

userinput = None 
input_idx = -1 # printf("%c", char) 
def printfc(char): 
print(chr(char), end='') # 
scanf("%c", &returned) 

def scanfc(): 

global userinput, input_idx 

if userinput is None: 

userinput = raw_input() 
input_idx = 0 

if userinput == '': 
    return 0xA 
    
else: 
    return ord(userinput[input_idx]) 
    
else: 
    input_idx += 1 
    
if input_idx == len(userinput): 
    input_idx -= 1 return 0xA 

else: 
    return ord(userinput[input_idx]) 

def exec_instruction(a, b, c): 
    code[b] -= code[a] 
    
if c != 0: return code[b] <= 0 else: return False 

def exec_vm(entry, size): 
    global ins_count, scanf_count, printf_count 
    pc = entry 
    while pc + 3 <= size: 
        if exec_instruction(code[pc], code[pc+1], code[pc+2]): 
            if code[pc+2] == -1: 
                return 1 
                pc = code[pc+2] 
            else: pc += 3 
            if code[4] == 1: 
                printfc(code[2]) 
                code[4] = 0 
                code[2] = 0 

            if code[3] == 1: 
                code[1] = scanfc() 
                code[3] = 0 
    
def main(): 

    code[273] = random.randint(0, 32767) % code[272] exec_vm(1123, 4352) 

if __name__ == '__main__': 
    main()

Let’s’ test out our shiny new emulator.

That’s perfect. At this point, we have a working emulator that mimics the exact operation of the VM. We no longer need the original binary for testing. However, we still have no idea about how the password is checked.

Visualizing execution pattern

Let us try to get a high-level overview of the password checking algorithm by plotting the value of the instruction pointer during the execution of the VM. To obtain deterministic execution pattern, the random number was replaced with a fixed number 0. Plotting the value of the Instruction Pointer we get the following image when trying with the password “12”.

Similarly, trying with the password “1212” yields the following plot.

By comparing the two plots, we can observe the number of executed instructions increases with the length of the password. The sawtooth patterns indicate loop. We can also notice that characters of the password are checked two at a time. The value of the instruction pointer never goes below 1000, indicating that offsets 0-1000 stores data.

The first and last sawtooth patterns indicate the printing of the welcome and failure message respectively. Correspondingly, this means the function which prints a string is located near offset 4000 in the bytecode. The function which handles input is located near 4200. The four peaks in the input pattern correspond to the four-letter password we provided. Characters at odd position in the password are processed near 3000 whereas those at even-numbered position are processed near 3500.

Visualizing memory read patterns

A subleq instruction is a tuple of three values (a,b,c) which performs arr[b] -= arr[a] . We can say the value at a is accessed for reading whereas the value at b is accessed for writing. We can plot the address the program reads from as the execution proceeds. The graph below is for the password “1212”.

The plot is quite similar to the execution pattern which implies the data and the code that uses it are located close to each other. Memory address 0 has the highest read count suggesting that its used as a temporary variable for storing the results of intermediate calculations. We can reason that the checking algorithm works by performing some calculations on the password characters and comparing the result to a hardcoded value. By intuition, this check seems to be done at the two points marked, close to 3700.

Tracing execution

We can trace the executed subleq instructions by modifying the exec_vm  function.

def exec_vm(entry, size): global trace pc = entry while pc + 3 <= size: print('loc_{} [{}]={} [{}]={}'.format(pc, code[pc], code[code[pc]], code[pc+1], code[code[pc+1]]), file=trace) if exec_instruction(code[pc], code[pc+1], code[pc+2]): if code[pc+2] == -1: return 1 pc = code[pc+2] else: pc += 3 if code[4] == 1: printfc(code[2]) code[4] = 0 code[2] = 0 if code[3] == 1: code[1] = scanfc() code[3] = 0

The number of lines in the trace for password “1212” is close to 15k. Let us inspect the trace using the execution flow graph as a reference.

The first preprocess stage occurs when the instruction count is in the range 1800 – 2700. In the trace file, we can see that the ASCII value of the first character of the password is multiplied by 15. The multiplication is done by repeated addition.

ASCII value of ‘1’ = 49
49 * 15 = 735

735 is then left shifted 7 times to obtain 94080. This calculation when the instruction count is in the range 2700-2800.

Getting the flag

From the memory read plot, we have identified 3700 as the possible location where the result of the previous calculation might be stored. If we inspect the bytecode near offset 3700, we indeed get a list of values.

In order to get back the initial ASCII values of the letters, we have to reverse the calculation. This can simply be done by right shifting 7 times followed by dividing by 15, i.e.  (x >> 7) / 15

Thus, we have the characters at the odd-numbered positions.

This is a subleq challenge, hence the first word seems to be subleq.

Lets, try to guess the remaining words using this list of English words. We will be using regex search. Searching for .b.u.d.m we get exactly 1 hit – absurdum.

The password formed till now is

Searching for absurdum on google reveals the word reductio ad absurdum.

The password is most likely to be subleq_and_reductio_ad_absurdum

If we try this as the password we get the much-coveted success message.

The flag for this challenge is subleq_and_reductio_ad_absurdum@flare-on.com