SIGINT CTF 2013: Task fenster (400 pts)

In this task we have a binary - fenster.exe (link to original exe: click), which checks if the given text is our sought flag. The executable is obfuscated and contains some anti-debug. The first step is to remove all garbage and produce a clean exe.

So, let's start!

The first debug check is inside TLS callback at 0x4019CB. All it does is:

encrypt(check_for_debugger, 0x1B, 0xEC, 0x00409CD8);
bool debugger = check_for_debugger();
encrypt(check_for_debugger, 0x1B, 0xEC, 0x00409CD8);
if (debugger) {
   exit(0);
}

encrypt(void* data, int size, int key, int* some_data) is a lengthy function (address: 0x40194B) responsible for data encryption / decryption, but its exact implemenation is not relevant to us. As you can see, we can just remove this TLS callback entry from the executable without any consequence later on.

If we enter the check_for_debugger routine, we can see three further anti-debugging techniques:

push ss
pop ss

This is quite tricky. Any modification of the ss register (excluding the lssinstruction) register causes interrupts to be delayed until the end of execution of next instruction. So, if we step through this code using a debugger (step into/over) the code will "escape" the single-stepping mode immediately after one steps into/over "pop ss". We can safely nop these instructions out.

pushfd
pop eax

This was probably inserted only to fool automatic analyzers and decompilators such as Hex-Rays. We can also nop it out.

call <jmp.&KERNEL32.IsDebuggerPresent>

Standard anti-debugging check, we can replace it with "xor eax,eax" or anything else. Those anti-debugs would often show up inside other functions, so watch out while stepping through the executable. ;)

The main function is located at 0x401EF9. It loads user input from stdin and then does the following with different dataA and dataB pointers in seven iterations (anti-debugging code is skipped, check is a function at 0x00401ab5):

encrypt(check, 0x24, KEY, SOME_PTR);
input_ok &= check(dataA, dataB, user_input);
encrypt(check, 0x24, KEY, SOME_PTR);

To make further analysis easier, we should dump the decrypted check function (and all sub-functions, which are encrypted too) and get rid of all calls to encrypt(). Once this is done, we are ready to dive into the check code and switch from OllyDbg to IDA.

After a brief analysis, it is clear that the function passes our input through finite-state machines (compiled regular expressions). The first subfunction at 0x401C44 performs some kind of initialization, the second one at 0x401C9D executes the machine and the last one at 0x401AD9 checks if the machine completed in a final state. The two pointers passed to check are:

• int*** dataA - machine specification, dataA[state][letter] is a NULL-terminated list of states that we can reach from the given state after a specific letter. Note that states are numbered from 1 to 255 and dataA[0] refers to the first state. Only capital letters cause transitions. Index=0 corresponds to 'A' and index 25 to 'Z'.
• int* dataB - a null-terminated list of final state indexes

Once we know the meaning of those structures, we can write some visualization and crack the regular expressions. I wrote a small C++ program which reads data from the "fenster" process, generates a graph description for dot and then compiles it to svg. The results are shown below (rectangles = final states, * = all capital letters, ^XY = all capitals without X and Y):

machine0.svg:

machine1.svg: 

machine2.svg: 

machine3.svg: 

machine4.svg: 

machine5.svg: 

machine6.svg: 

Solving them by hand would be painful (look at machine4.svg!), so the next step was to write an optimized brute-force solver. Analyzing the machines shows that:

• machine0 - input must end with "EN" and the second letter is "E"
• machine1 - input is a concatenation of pairs: {"NW", "EN", "ES", "CH", "SW", "RG", "GS", "SE", "RE", "GE", "NE"}
• machine3 - input length is 16

With the above knowledge, we only have to check around 4*11^6 different inputs. The simplest way for me to check if the input was correct was to just reuse the original check function from fenster.exe loaded as a DLL. The solver's code was as follows:

#include <cstring>
#include <cstdio>
#include <Windows.h>
#include <cassert>

using namespace std;

int machines[7] =   { 0x4077A0, 0x407E40, 0x4082E0, 0x408BA0, 0x4098C0, 0x409B48, 0x409C68 };
int end_states[7] = { 0x4077DC, 0x407E70, 0x408300, 0x408BE4, 0x409920, 0x409B58, 0x409C70 };
const int pairscnt = 11;
char* pairs[pairscnt] = {"NW", "EN", "ES", "CH", "SW", "RG", "GS", "SE", "RE", "GE", "NE"};
char key[17] = " E            EN";
int it[7] = {7};
int regex_match, memset_addr;

__declspec(naked) bool __cdecl check()
{
    __asm
    {
        push edi
        push ebp
        mov ebp, esp
        and esp, 0xFFFFFFF0

        mov edi, 0

        looop:
            sub esp,4
            push offset key
            push end_states[edi*4]
            push machines[edi*4]
            call regex_match
            add esp, 0x10
            test eax,eax
            jz hop

            inc edi
            cmp edi, 7
        jnz looop

hop:
        mov esp, ebp
        pop ebp
        pop edi
        retn
    }
}

int main()
{
    int fenster = (int)LoadLibraryA("~fenster2.dll");

    // It doesn't work on bases different from 0x400000,
    // because the binary has no relocations (e.g. final states list pointers)
    // just run it until it works
    assert(fenster == 0x400000);
    regex_match = 0x401d97;
    memset_addr = 0x40C17C;

    // Resolving imports
    *(int*)memset_addr = (int)memset;

    // Assert that last pair is set
    assert(strlen(key) == 16);

    while(it[6] < pairscnt)
    {
        for(int i=0; i<7; i++)
           key[i*2] = pairs[it[i]][0],
           key[i*2+1] = pairs[it[i]][1];
 
        if(check())
            puts(key);
 
        it[0]++;
        for(int i=0; i<6 && it[i]==pairscnt; i++)
            it[i+1]++,
            it[i] = 0;
    }
    return 0;
}

where ~fenster2.dll is a deobfuscated executable, you can download it here: https://docs.google.com/file/d/0B-L9DIAuaV7STkNjNGdBY1RnQ2M/edit?usp=sharing. After running the application for a short while, it spit out the "REGENECHENSESWEN" textual string, which indeed turned out to be the correct flag. +400pts :)