Writeup for the Transformer challenge from VolgaCTF 2016 Quals


This is another challenge from the Volga CTF Quals 2016, involving an x64 ELF executable that encodes files. Our objective is to recover the clear text data from the encrypted file.

Here's the description for this challenge:

This binary does something with the data. The transformation must be reversible, but the details are unknown. It shouldn't be too difficult to reverse that transformation and obtain the flag, should it?

You can download the executable from the CTF Writeup repository on GitHub.

What I'm going to do in this writeup is simple:

  1. Reverse the algorithm. I will use IDA Pro, but you can also use radare2.
  2. Write a compatible encoder in C++.
  3. Invert the transformation and implement decoding functionality.

For starters, you may have noticed that this executable does not like to be run inside a debugger; you can easily pinpoint where the anti-debugger check is performed by setting a breakpoint to the exit() function.

We could have choosen to hook the ptrace() function and disable this check by using the LD_PRELOAD environment variable, but the code at address 401074 would have prevented us from being able to do it. What we really want to remove instead is the debugger protection and to be honest it's easier to just patch the program. It's not required if you don't plan on stepping through the code or if you don't mind skipping it manually with a breakpoint each time you start the program.

Now that we got rid of the protection, let's take a look at the caller.

If you played the previous level (named Broken) you will remember that the init() function had been patched to remove a function call that was required for the algorithm to work as intended; this challenge is no exception and you will have to fix the instruction located at address 004019F8. Again, the function we need to call can be found inside the second array.

There's not much else to say about the rest of the functions referenced here; they're just used for initialization and we don't really care to analyze them, provided that we take a memory snapshot once it's done. Let's see how the rest of the program works; it's pretty long, so I will use annotated pseudo-code to illustrate its internals.

// 004010B0
int main(int argc, char *argv[])
{
    // 004010d0
    if (argc != 3)
        return 0;

    const char *input_file_path = argv[1];
    const char *output_file_path = argv[2];

    // 0040111a
    std::fstream input_file(input_file_path);

    // 00401135
    std::fstream output_file(output_file_path);

    // 004011c5
    input_file.seekg(0, std::ios_base::end);

    // 004011d2
    std::streamsize file_size = input_file.tellg();

    // 004011ee
    input_file.seekg(0, std::ios_base::beg);

    // 004011fa
    std::uint8_t *buffer = new std::uint8_t[file_size];

    // 0040121D
    input_file.read(buffer, file_size);

    //
    // we don't care much about the following function, as it doesn't touch
    // our buffer in any way. Take a memory snapshot after this call
    //

    // 0040122C
    call sub_401932;

    //
    // this is what we need to analyze
    //

    // 0040123A
    call sub_401836;

    // 00401248
    output_file.write(buffer, file_size);

    return 0;
}

// 00401836
void sub_401836(uint8_t *input_buffer, uint8_t *output_buffer, uint32_t buffer_size)
{
    // rdi = input_buffer
    // rsi = output_buffer
    // rdx = buffer_size

    // an xmmword is 16 bytes long; this function encodes one block
    // at a time by calling sub_40179e

    // 00401860
    rdx = shr rdx, 0x04;

    // 00401870
    if (rdx == 0)
        return;

    do
    {
        // 00401877
        xmm0 = *rdi;

        // 0040187b
        call sub_40179e;

        // 00401880
        *rsi = xmm0;

        // 00401884
        rdi += 0x10;

        // 00401888
        rsi += 0x10;

        // 0040188c
        rdx--;
    } while (rdx != 0); // 00401864

    // 0040189f
    return;
}

// 0040179e
void sub_40179e()
{
    // this is the real encoding function; it's nothing too fancy
    // and you can easily invert each transformation by performing
    // the same operations in reverse order

    // 004017ac
    xmm7 = xmm0;

    // 004017c8
    xmm0 = xmmword_602128;

    // 004017d1
    pxor xmm7, xmm0;

    // 004017d6
    r15 = 0x10;

    do
    {
        // 004017e1
        call sub_4015d0;

        // 004017e6
        call sub_40167d;

        // 004017eb
        call sub_40169f;

        // 004017f0
        xmm0 = xmmword_602128[r15];

        // 004017f9
        pxor xmm7, xmm0;

        // 004017fe
        r15 += 0x10;
    } while (r15 < 0x0A); // 00401802

    // 0040180b
    call sub_4015d0;

    // 00401810
    call sub_40167d;

    // 00401815
    xmm0 = xmmword_602128[r15];

    // 0040181e
    pxor xmm7, xmm0;

    // 00401823
    xmm0 = xmm7

    // 00401835
    return;
}

// 004015d0
void sub_4015d0()
{
    // 004015d9
    [rsp] = xmm7;

    // 004015de
    for (offset = 0; offset < 0x0c; offset += 0x04)
    {
        ebx = [rsp + offset];
        call sub_40161f;
        [rsp + offset] = eax;
    }

    // 00401615
    xmm7 = [rsp];

    // 0040161e
    return;
}

// 0040167d
void sub_40167d()
{
    // 00401694
    xmm0 = xmmword_401683;

    // 00401698
    pshufb xmm7, xmm0;

    // 0040169e
    return;
}

// 0040169f
void __usercall sub_40169f()
{
    // 004016a8
    [rsp] = xmm7;

    // 004016ad
    for (offset = 0; offset < 0x0c; offset += 0x04)
    {
        edi = [rsp + offset];
        call sub_4016e9;
        [esp] = eax;
    }

    // 004016df
    xmm7 = [rsp];

    // 004016e8
    return;
}

// 0040161f
void __usercall sub_40161f()
{
    // input: ebx
    // output: eax

    movzx   ecx, bl
    mov     al, byte ptr qword_602268[ecx]
    movzx   ecx, bh
    mov     ah, byte ptr qword_602268[ecx]
    shl     eax, 10h
    shr     ebx, 10h
    movzx   ecx, bl
    mov     al, byte ptr qword_602268[ecx]
    movzx   ecx, bh
    mov     ah, byte ptr qword_602268[ecx]
    rol     eax, 10h
    add     rsp, 8
    nop
    retn
}

There're two more functions we need to analyze: sub_40161f and sub_4016e9; I've added some spacing to make the listings easier to follow and understand.

This function is pretty easy to invert; just execute the same opcodes in reverse order and you will obtain the input value. Let's take a look at the second procedure:

This is slightly harder, and will require some work; first of all, write down how the sub_4016e9 function encodes the input value:

output[3] = byte_602494[input[0]] ^ input[1] ^ input[2] ^ byte_602394[input[3]];
output[2] = byte_602394[input[2]] ^ input[0] ^ input[1] ^ byte_602494[input[3]];
output[1] = byte_602394[input[1]] ^ input[0] ^ input[3] ^ byte_602494[input[2]];
output[0] = byte_602394[input[0]] ^ input[2] ^ input[3] ^ byte_602494[input[1]];

Then, invert the operands so that the input value is on the left:

input[1] = output[3] ^ byte_602494[input[0]] ^ input[2] ^ byte_602394[input[3]]
input[0] = output[2] ^ byte_602394[input[2]] ^ input[1] ^ byte_602494[input[3]]
input[3] = output[1] ^ byte_602394[input[1]] ^ input[0] ^ byte_602494[input[2]]
input[2] = output[0] ^ byte_602394[input[0]] ^ input[3] ^ byte_602494[input[1]]

We can now brute force the system and obtain the input value:

// ...

for (std::uint16_t input1 = 0x00; !found && input1 <= 0xFF; input1++)
{
    input[1] = static_cast<std::uint8_t>(input1);

    for (std::uint16_t input2 = 0x00; !found && input2 <= 0xFF; input2++)
    {
        input[2] = static_cast<std::uint8_t>(input2);

        for (std::uint16_t input3 = 0x00; !found && input3 <= 0xFF; input3++)
        {
            input[3] = static_cast<std::uint8_t>(input3);

            input[0] = output[2] ^ byte_602394[input[2]] ^ input[1] ^ byte_602494[input[3]];

            if (input[1] != (output[3] ^ byte_602494[input[0]] ^ input[2] ^ byte_602394[input[3]]))
                continue;

            if (input[2] != (output[0] ^ byte_602394[input[0]] ^ input[3] ^ byte_602494[input[1]]))
                continue;

            if (input[3] != (output[1] ^ byte_602394[input[1]] ^ input[0] ^ byte_602494[input[2]]))
                continue;

            found = true;
        }
    }
}

// ...

We have pretty much analyzed everything we needed to invert the transformation algorithm, and we can now decode the encrypted file:

alessandro at tachikoma in ~/Projects/untransformer (master)
$ untransformer decode flag.transformed flag.decoded && cat flag.decoded
VolgaCTF{transf0rming_dat@_with_hardc0ded_key_is_not_saf33}

I have published the whole source code on my GitHub page in case you want to take a look at the decoder.

If you managed to get this far, thanks for reading! I hope you found this writeup interesting; I know I at least had fun writing it.