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.

00401070 Protection proc near 
00401070     sub     rsp, 8
00401070
00401070     ; terminate the process if the LD_PRELOAD variable
00401070     ; is set
00401070
00401074     mov     edi, offset name ; "LD_PRELOAD"
00401079     call    _getenv
00401079
0040107e     test    rax, rax
00401081     jnz     short _terminate
00401081
00401081     ; terminate if the PTRACE_TRACEME ptrace request
00401081     ; returns -1 (meaning that a debugger is already
00401081     ; attached)
00401081
00401083     xor     ecx, ecx
00401085     xor     edx, edx
00401087     xor     esi, esi
00401089     xor     edi, edi        ; request (PTRACE_TRACEME)
0040108b     xor     eax, eax
0040108d     call    _ptrace
0040108d
00401092     test    rax, rax
00401095     js      short _terminate
00401095
00401097     add     rsp, 8
0040109b     retn
0040109c
0040109c _terminate:
0040109c     xor     edi, edi        ; status (0)
0040109e     call    _exit
0040109e Protection endp

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.

004019C0 init proc near
004019C0     push    r15
004019C2     mov     r15d, edi
004019C5     push    r14
004019C7     mov     r14, rsi
004019CA     push    r13
004019CC     mov     r13, rdx
004019CF     push    r12
004019CF
004019CF     ; array contents:
004019CF     ; Initialization01 (004013D0)
004019CF     ; Protection (00401070)
004019CF     ; CppIoStreamConstructor (004012F0)
004019CF     
004019D1     lea     r12, InitializationFunctionsList1
004019D8     push    rbp
004019D8
004019D8     ; array contents: Initialization02 (004013B0)
004019D8
004019D9     lea     rbp, InitializationFunctionsList2
004019E0     push    rbx
004019E1     sub     rbp, r12
004019E4     xor     ebx, ebx
004019E6     sar     rbp, 3
004019EA     sub     rsp, 8
004019EE     call    _init_proc
004019F3     test    rbp, rbp
004019F6     jz      short loc_401A16
004019F6
004019F6     ; it's pretty obvious that someone has messed up
004019F6     ; this opcode. replace it with a function call
004019F6     ; to address 004013B0
004019F6
004019F8     nop     dword ptr [rax+rax+00000000h]
00401A00
00401A00 loc_401A00:
00401A00
00401A00     mov     rdx, r13
00401A03     mov     rsi, r14
00401A06     mov     edi, r15d
00401A06
00401A06     ; functions called:
00401A06     ; 1. Initialization01: program initialization
00401A06     ; 2. Protection: LD_PRELOAD/debugger check
00401A06     ; 3. CppIoStreamConstructor: constructor and destructor
00401A06     ;    (using atexit) for the std::ios_base c++ object
00401A06
00401A09     call    qword ptr [r12+rbx*8]
00401A0D     add     rbx, 1
00401A11     cmp     rbx, rbp
00401A14     jnz     short loc_401A00
00401A16
00401A16 loc_401A16:
00401A16
00401A16     add     rsp, 8
00401A1A     pop     rbx
00401A1B     pop     rbp
00401A1C     pop     r12
00401A1E     pop     r13
00401A20     pop     r14
00401A22     pop     r15
00401A24     retn
00401A24 init endp

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.

0040161F sub_40161f proc near
0040161F
0040161F     ; input: ebx
0040161F     ; output: eax
0040161F
0040161F     push    rcx
00401620     jmp     short loc_40162B
00401620
00401622     db 0x00
00401623     db 0x00
00401624     db 0x00
00401625     db 0xE9
00401626     db 0xA6
00401627     db 0x01
00401628     db 0x40
00401629     db 0xE9
0040162A     db 0x04
0040162B
0040162B loc_40162B:
0040162B
0040162B     xor     rax, rax
0040162E     jmp     short loc_401646

........

00401646 loc_401646:
00401646
00401646     movzx   ecx, bl
00401649     mov     al, byte ptr qword_602268[ecx]
00401649
00401650     movzx   ecx, bh
00401653     mov     ah, byte ptr qword_602268[ecx]
0040165A
0040165A     shl     eax, 10h
0040165D     shr     ebx, 10h
00401660
00401660     movzx   ecx, bl
00401663     mov     al, byte ptr qword_602268[ecx]
0040166A
0040166A     movzx   ecx, bh
0040166D     mov     ah, byte ptr qword_602268[ecx]
00401674
00401674     rol     eax, 10h
00401677
00401677     add     rsp, 8
0040167B     nop
0040167C     retn
0040167C sub_40161f endp

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:

004016E9 sub_4016e9 proc near
004016E9
004016E9     ; input: edi
004016E9     ; output: eax
004016E9
004016E9     xor     eax, eax
004016EB     jz      short loc_4016EE
004016EB
004016ED     db 0xE8
004016EE
004016EE loc_4016EE:
004016EE     movzx   r8, dil
004016F2     shr     edi, 8
004016F2
004016F5     movzx   r9, dil
004016F9     shr     edi, 8
004016F9
004016FC     movzx   r10, dil
00401700     shr     edi, 8
00401700
00401703     movzx   r11, dil
00401707     xor     eax, eax
00401707
00401709     mov     r12b, byte_602394[r11]
00401710     mov     dil, byte_602494[r8]
00401717     xor     edi, r9d
0040171A     xor     edi, r10d
0040171D     xor     edi, r12d
00401720     and     edi, 0FFh
00401726     or      eax, edi
00401728     shl     eax, 8
00401728
0040172B     mov     r12b, byte_602494[r11]
00401732     mov     dil, byte_602394[r10]
00401739     xor     edi, r8d
0040173C     xor     edi, r9d
0040173F     xor     edi, r12d
00401742     and     edi, 0FFh
00401748     or      eax, edi
0040174A     shl     eax, 8
0040174D     jb      short loc_401752
0040174F     jnb     short loc_401752
0040174F
00401751     db 0E9h
00401752
00401752 loc_401752:
00401752
00401752     mov     r12b, byte_602494[r10]
00401759     mov     dil, byte_602394[r9]
00401760     xor     edi, r8d
00401763     xor     edi, r12d
00401766     xor     edi, r11d
00401769     and     edi, 0FFh
0040176F     or      eax, edi
0040176F
00401771     shl     eax, 8
00401774     mov     r12b, byte_602494[r9]
0040177B     mov     dil, byte_602394[r8]
00401782     xor     edi, r12d
00401785     xor     edi, r10d
00401788     xor     edi, r11d
0040178B     and     edi, 0FFh
00401791     or      eax, edi
00401791
00401793     retn
0040109e sub_4016e9 endp

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.