The Complexity Elephant

Thoughts about software engineering, and game development.

Topics

1. Write Up: Gre-Hack CTF 2019 - Reverse - The Point

This is a reverse challenge from the Gre-Hack CTF 2019. The challenge was designed by Xarkes.

1.1. TL;DR

The main is a lie. The actual pass/fail branching occurs in a function called from atexit. ANSI codes are used to clear the fail message and replace it with the success one.

The user input is encrypted from the main function, and checked against a reference. The xor/substitute tables are modified from extra entry points, and will be wrong if you’re running with a non-interactive stdout.

1.2. First contact

We’re given a binary executable file. Let’s try to run it:

Nice, a challenge with colors! Let’s jump on the occasion to refresh our ANSI control code skills:

Err. There are no ANSI codes in there. Seems like the program is, like many UNIX utilities, disabling colors depending on whether stdout is interactive or not. Too bad.

OK, so it’s expecting the flag on stdin. Let’s try to run it again under a debugger:

Ok, now it gets frustrating. No debug? Bypass this limitation should be relatively easy; but, first, let’s fire up radare2 and get a summary:

Nothing specially fancy here, except it’s detected as C\++, and that it’s PIE.

1.3. Overview

Let’s fix a base address of 0x100000 to keep our sanity, and have a look at the call graph:

$ r2 -B 0x100000 ../1573855486.7463248_ThePoint
: aaa
: afn TheMain @ main
: agCd > graph.dot

After some libstdc++ pruning from graph.dot, we get a very readable graph:

One thing is immediately obvious: there’s more than one entry point. Also, cxa_atexit is being called from entry.init4, but this seems to be for legitimate destruction code. Let’s complete the search and look at the xrefs of cxa_atexit. Bingo: it’s also being called indirectly by entry.init3, and the function to be run at exit is 0x102b50.

So now we have lots of functions to check:

0x1022c0 aka entry.init0 : seems to be legit initialization stuff, let’s ignore this one.
0x102b10 aka entry.init1 : can reach a syscall, lets' keep an eye one this one.
0x102b30 aka entry.init2 : can reach a syscall, lets' keep an eye one this one.
0x102b40 aka entry.init3 : seems to be legit initialization stuff, let’s ignore this one.
0x1033f0 aka TheMain: the official entry point.
0x102b50 : the sneaky function to be run at exit.

1.4. The main function

Let’s decompile TheMain:

$ pdd @ TheMain

So this is a pretty conventional main function.

We also recognize the anti-debug warning message. Indeed, it should be easy to circumvent. However, to detect the presence of a debugger you need to issue at least one syscall, and there doesn’t seem to be any here. So we confirm that some processing must occur before TheMain.

Seemingly the pass/fail branching hinges on the result of the function 0x103330. Let’s add this into our list of addresses to check.

1.5. The sneaky function

Before going too far, let’s have a look a the sneaky function at 0x102b50. We see that first, it sends \e[A (from 0x104004), \e[2K to stdout. So it seems we’ll finally have a chance to refresh our ANSI skills! This very ANSI sequence means move the cursor up one line and clear entire line. Interesting … especially when considering that this function is to be called after the main function!

/* r2dec pseudo code output */
/* ../1573855486.7463248_ThePoint @ 0x102b50 */
#include <stdint.h>

void fcn_00102ac0 (void) {
    rdi = *(reloc.std::cout);
    rsi = 0x00104004;
    std::string & std::operator << std::string (std::string &,char const*) ();
    rdi = *(reloc.std::cout);
    rsi = "\e[2K";
    std::string & std::operator << std::string (std::string &,char const*) ();
}

int64_t fcn_00102b50 (void) {
    int64_t var_8h;
    int64_t var_10h;
    int64_t var_18h;
    int64_t var_19h;
    int64_t var_1ah;
    int64_t var_1bh;
    int64_t var_1ch;
    int64_t var_1dh;
    int64_t var_1eh;
    int64_t var_1fh;
    int64_t var_20h;
    int64_t var_21h;
    int64_t var_22h;
    int64_t var_23h;
    int64_t var_24h;
    int64_t var_25h;
    int64_t var_26h;
    int64_t var_27h;
    int64_t var_28h;
    int64_t var_30h;
    int64_t var_38h;
    int64_t var_48h;
    rax = *(fs:0x28);
    var_48h = *(fs:0x28);
    eax = fcn_00102ac0 ();
    eax = 0;
    rcx = 0x00106b20;
    rcx += 0x30;
    *(rsp) = rcx;
    r9 = *(rsp);
    rcx = 0x0010400d;
    rdx = rcx;
    do {
        rdx++;
        rax++;
        rcx = rdx;
    } while (*((rcx + 1)) != 0);
    esi = 0;
    r10b = *(r9);
    cl = 1;
    if (r10b == 0) {
        goto label_0;
    }
    edx = 0;
    rsi = r9;
    rcx = r9;
    while (*((rsi + 1)) != 0) {
        rcx++;
        rdx++;
        rsi = rcx;
    }
    esi = 0;
    cl = (eax != 0) ? 1 : 0;
    bl = (edx != 0) ? 1 : 0;
    cl &= bl;
    cl = 1;
    if ((cl & 1) == 0) {
        goto label_0;
    }
    edi = 0;
    esi = 0;
    ecx = 0xffffffff;
    rdx &= rcx;
    r8d = eax;
    cl = 7;
    do {
        if (r10b != cl) {
            goto label_1;
        }
        rdi++;
        esi++;
        cl = (rdi < r8) ? 1 : 0;
        bl = (rdi < rdx) ? 1 : 0;
        cl &= bl;
        if ((cl & 1) == 0) {
            goto label_2;
        }
        r10b = *((r9 + rdi));
        rcx = 0x0010400d;
        cl = *((rcx + rdi));
    } while (1);
label_1:
    ecx = 0;
    esi = edi;
    goto label_0;
label_2:
    cl = 1;
label_0:
    al = (esi == eax) ? 1 : 0;
    al &= cl;
    if ((al & 1) == 0) {
    } else {
        rdi = *(reloc.std::cout);
        rsi = "\e[32m";
        edx = 5;
        std::string &std::_ostream_insert<char,std::char_traits<char>>(std::string &,char const*,long) ();
        r14 = &var_38h;
        var_28h = r14;
        edi = 0x3b;
        rax = operatornew(unsigned long) ();
        rbx = rax;
        r15 = &var_28h;
        var_28h = rbx;
        var_38h = 0x3a;
        memcpy (rbx, 0x00104120, 0x3a);
        var_30h = 0x3a;
        *((rbx + 0x3a)) = 0;
        *(rbx) = 0x43;
        *((rbx + 1)) = 0x6f;
        *((rbx + 2)) = 0x72;
        *((rbx + 3)) = 0x72;
        *((rbx + 4)) = 0x65;
        *((rbx + 5)) = 0x63;
        *((rbx + 6)) = 0x74;
        *((rbx + 7)) = 0x21;
        *((rbx + 8)) = 0x20;
        *((rbx + 9)) = 0x59;
        *((rbx + 0xa)) = 0x6f;
        *((rbx + 0xb)) = 0x75;
        *((rbx + 0xc)) = 0x20;
        *((rbx + 0xd)) = 0x63;
        *((rbx + 0xe)) = 0x61;
        *((rbx + 0xf)) = 0x6e;
        *((rbx + 0x10)) = 0x20;
        *((rbx + 0x11)) = 0x75;
        *((rbx + 0x12)) = 0x73;
        *((rbx + 0x13)) = 0x65;
        *((rbx + 0x14)) = 0x20;
        *((rbx + 0x15)) = 0x74;
        *((rbx + 0x16)) = 0x68;
        *((rbx + 0x17)) = 0x69;
        *((rbx + 0x18)) = 0x73;
        *((rbx + 0x19)) = 0x20;
        *((rbx + 0x1a)) = 0x69;
        *((rbx + 0x1b)) = 0x6e;
        *((rbx + 0x1c)) = 0x70;
        *((rbx + 0x1d)) = 0x75;
        *((rbx + 0x1e)) = 0x74;
        *((rbx + 0x1f)) = 0x20;
        *((rbx + 0x20)) = 0x74;
        *((rbx + 0x21)) = 0x6f;
        *((rbx + 0x22)) = 0x20;
        *((rbx + 0x23)) = 0x76;
        *((rbx + 0x24)) = 0x61;
        *((rbx + 0x25)) = 0x6c;
        *((rbx + 0x26)) = 0x69;
        *((rbx + 0x27)) = 0x64;
        *((rbx + 0x28)) = 0x61;
        *((rbx + 0x29)) = 0x74;
        *((rbx + 0x2a)) = 0x65;
        *((rbx + 0x2b)) = 0x20;
        *((rbx + 0x2c)) = 0x74;
        *((rbx + 0x2d)) = 0x68;
        *((rbx + 0x2e)) = 0x65;
        *((rbx + 0x2f)) = 0x20;
        al = *((rbx + 0x30));
        al ^= 0x99;
        *((rbx + 0x30)) = al;
        al = *((rbx + 0x31));
        al ^= 0x99;
        *((rbx + 0x31)) = al;
        al = *((rbx + 0x32));
        al ^= 0x99;
        *((rbx + 0x32)) = al;
        al = *((rbx + 0x33));
        al ^= 0x99;
        *((rbx + 0x33)) = al;
        al = *((rbx + 0x34));
        al ^= 0x99;
        *((rbx + 0x34)) = al;
        al = *((rbx + 0x35));
        al ^= 0x99;
        *((rbx + 0x35)) = al;
        al = *((rbx + 0x36));
        al ^= 0x99;
        *((rbx + 0x36)) = al;
        al = *((rbx + 0x37));
        al ^= 0x99;
        *((rbx + 0x37)) = al;
        al = *((rbx + 0x38));
        al ^= 0x99;
        *((rbx + 0x38)) = al;
        al = *((rbx + 0x39));
        al ^= 0x99;
        *((rbx + 0x39)) = al;
        rbx = var_28h;
        if (rbx == 0) {
            rax = *(reloc.std::cout);
            rcx = *(rax);
            rcx = *((rcx - 0x18));
            rdi = rax;
            rdi += rcx;
            esi = *((rax + rcx + 0x20));
            esi |= 1;
            std::basic_ios<char,std::char_traits<char>>::clear(std::_Ios_Iostate) ();
        } else {
            rax = strlen (rbx);
            rdi = *(reloc.std::cout);
            rsi = rbx;
            rdx = rax;
            std::string &std::_ostream_insert<char,std::char_traits<char>>(std::string &,char const*,long) ();
        }
        rdi = *(reloc.std::cout);
        rsi = "\e[37m";
        edx = 5;
        std::string &std::_ostream_insert<char,std::char_traits<char>>(std::string &,char const*,long) ();
        rax = *(reloc.std::cout);
        rcx = *(rax);
        rcx = *((rcx - 0x18));
        rbx = *((rax + rcx + 0xf0));
        if (rbx == 0) {
            std::_throw_bad_cast() ();
        }
        if (*((rbx + 0x38)) != 0) {
            al = *((rbx + 0x43));
        } else {
            rdi = rbx;
            std::ctype<char>::_M_widen_init()const ();
            rax = *(rbx);
            rax = *((rax + 0x30));
            rdi = rbx;
            esi = 0xa;
            al = void (*rax)() ();
        }
        esi = (int32_t) al;
        rdi = *(reloc.std::cout);
        rax = std::ostream::put(char) ();
        rdi = rax;
        std::ostream::flush() ();
        rdi = *(r15);
        if (rdi != r14) {
            delete ();
        }
        goto label_3;
    }
    rbx = *(reloc.std::cout);
    rsi = "\e[31m";
    rdi = rbx;
    edx = 5;
    std::string &std::_ostream_insert<char,std::char_traits<char>>(std::string &,char const*,long) ();
    r14 = &var_18h;
    var_8h = r14;
    var_10h = 0xf;
    var_27h = 0;
    r15 = &var_8h;
    var_18h = 0x57;
    var_19h = 0x72;
    var_1ah = 0x6f;
    var_1bh = 0x6e;
    var_1ch = 0x67;
    var_1dh = 0x20;
    var_1eh = 0x70;
    var_1fh = 0x61;
    var_20h = 0x73;
    var_21h = 0x73;
    var_22h = 0x77;
    var_23h = 0x6f;
    var_24h = 0x72;
    var_25h = 0x64;
    var_26h = 0x21;
    rax = strlen (r14);
    rdi = rbx;
    rsi = r14;
    rdx = rax;
    std::string &std::_ostream_insert<char,std::char_traits<char>>(std::string &,char const*,long) ();
    rdi = *(reloc.std::cout);
    rsi = "\e[37m";
    edx = 5;
    std::string &std::_ostream_insert<char,std::char_traits<char>>(std::string &,char const*,long) ();
    rax = *(reloc.std::cout);
    rcx = *(rax);
    rcx = *((rcx - 0x18));
    rbx = *((rax + rcx + 0xf0));
    if (rbx == 0) {
        std::_throw_bad_cast() ();
    }
    if (*((rbx + 0x38)) != 0) {
        al = *((rbx + 0x43));
    } else {
        rdi = rbx;
        std::ctype<char>::_M_widen_init()const ();
        rax = *(rbx);
        rax = *((rax + 0x30));
        rdi = rbx;
        esi = 0xa;
        al = void (*rax)() ();
    }
    esi = (int32_t) al;
    rdi = *(reloc.std::cout);
    rax = std::ostream::put(char) ();
    rdi = rax;
    std::ostream::flush() ();
    rdi = *(r15);
    if (rdi != r14) {
        delete ();
    }
label_3:
    rax = *(fs:0x28);
    rcx = var_48h;
    if (rax == rcx) {
        return rax;
    }
    return stack_chk_fail ();
}

It gets better: the whole function seems to have control flow very similar to the main function.

It compares two buffers in memory, and depending on the result of the comparison, prints a success message or a failure message. And the way the message is filled (char by char, so the string doesn’t appear as such in the binary) confirms that this function is trying to hide its behavior. Seems like we were right to name it sneaky.

The two compared buffers are 0x10400d and 0x106b50, which changes depending on the user input: so 0x106b50 must contain the encrypted flag. Let’s look at the xrefs for 0x106b50: there’s exactly one, in the function 0x103090, which is the check function indirectly called from TheMain. The other buffer, 0x10400d, is fixed and its data directly comes from the binary executable file.

1.6. The check function

Now we have two reasons to go look into 0x103090:

it writes some input-flag-dependent encrypted buffer
its return value determines the pass/fail branching TheMain

Let’s decompile it:

Basically, it does that:

void fcn_0x103090(char* theFlag)
{
  // encryption
  for(int i = 0; i < flagLen; ++i)
  {
    for(int k = 0; k < flagLen; ++k)
      theFlag[k] = PermutationTable[rotateLeft(theFlag[k])];

    theFlag[i] += theFlag[i + 1];

    for(int k = 0; k < flagLen; ++k)
      theFlag[k] ^= XorTable[i + k];
  }

  for(int k = 0; k < 0x100; ++k)
    g_encryptedFlag[k] = theFlag[k];
}

The encryption can be reversed this way:

void Decrypt(char* theFlag)
{
  for(int i = flagLen - 1; i >= 0; --i)
  {
    for(int k = 0; k < flagLen; ++k)
      theFlag[k] ^= XorTable[i + k];

    theFlag[i] -= theFlag[i + 1];

    for(int k = 0; k < flagLen; ++k)
      theFlag[k] = ror(ReversePermute(theFlag[k]));
  }
}

So at the point we need to dump:

PermutationTable ( 0x106180 )
XorTable ( 0x106780 )
The reference encrypted flag ( 0x10400d )

But we can’t do this dumping from a debugger : if we do this, we will get wrong tables.

So let’s use a simulator instead.

1.7. Enter ANGR

At this point, we know enough to properly to setup a simulation from angr.

we hook ioctl because the program uses ioctl 0x5401 on stdout to determine if it’s interactive.
we also hook each occurence of the endbr instruction, as angr doesn’t support them.

#!/usr/bin/env python3

import angr;

BINARY='../1573855486.7463248_ThePoint'
BASE=0x100000

def Main():
    p = angr.Project(BINARY, load_options={"auto_load_libs": True, 'main_opts': {'custom_base_addr': BASE}})

    p.hook_symbol("ioctl", MyIoctl())

    # Angr/VEX chokes 'endbr' instructions: skip them
    def endbr(state):
        pass

    p.hook(BASE + 0x2000, endbr, length=4)
    p.hook(BASE + 0x2260, endbr, length=4)
    p.hook(BASE + 0x2350, endbr, length=4)
    p.hook(BASE + 0x38c0, endbr, length=4)
    p.hook(BASE + 0x3940, endbr, length=4)

    initState = p.factory.full_init_state(args=["prog"], add_options={'BYPASS_UNSUPPORTED_SYSCALL'})

    simulator = p.factory.simgr(initState)
    simulator.explore()

    finalState = simulator.deadended[0]
    dumpTable(finalState, "EncryptedFlag", 0x400d, 36)
    dumpTable(finalState, "PermuteTable",  0x6180, 256)
    dumpTable(finalState, "XorTable",      0x6780, 256)

class MyIoctl(angr.SimProcedure):
    def run(self, sym_fd, sym_num, sym_addr):
        fd = self.state.solver.eval_one(sym_fd)
        number = self.state.solver.eval_one(sym_num)
        address = self.state.solver.eval_one(sym_addr)
        print("ioctl", fd, number, hex(address))

        # intercept TCGETS, fill result struct with '1'
        if number == 0x5401:
            print("-> tcgets")
            for b in range(address, address+60):
                self.state.memory.store(b, 0xff, 1)

def dumpTable(state, name, addr, size):
    print("uint8_t " + name + "[] = ")
    print("{")
    line=""
    for addr in range(BASE + addr, BASE + addr + size):
        val=state.solver.eval_one(state.memory.load(addr, 1))
        line += ("0x%x" % val) + ", "
    print("  " + line)
    print("};")


Main()

We run the simulation, and get the tables:

$ python solve.py
('ioctl', 1L, 21505L, '0x7fffffffffefeb8L')
-> tcgets
uint8_t EncryptedFlag[] =
{
  0x7, 0xbb, 0xcb, 0xe, 0x86, 0x6, 0x5d, 0x92, 0x57, 0xa6, 0x2c, 0xa2, 0x39, 0x6e, 0x7f, 0x24,
  0xbf, 0x98, 0x4c, 0x1, 0xd3, 0xc7, 0x12, 0x9d, 0x43, 0xf, 0x39, 0xa1, 0x53, 0x33, 0x8d, 0x8c,
  0x2f, 0x30, 0x52, 0x0,
};
uint8_t PermuteTable[] =
{
  0x19, 0xc3, 0xf2, 0xa2, 0x4c, 0xcc, 0x53, 0x64, 0x32, 0x5b, 0xc8, 0xb0, 0xc6, 0x90, 0x4e, 0xeb,
  0x9f, 0x8d, 0xa7, 0xe3, 0x5, 0xc2, 0x1b, 0xd1, 0x24, 0xf3, 0x86, 0xaf, 0x6c, 0x56, 0xcb, 0xc5,
  0x3, 0xf4, 0xb7, 0xf1, 0x9c, 0x71, 0xdd, 0x46, 0x8b, 0xd4, 0x4d, 0x2b, 0x58, 0x6e, 0x37, 0x14,
  0x60, 0x88, 0xb5, 0x44, 0x84, 0x59, 0xde, 0x96, 0x12, 0x3b, 0x6d, 0xe6, 0xfb, 0xd0, 0xa1, 0x11,
  0x0, 0xba, 0x8e, 0xc0, 0xbb, 0x80, 0x55, 0xcf, 0xad, 0x9b, 0x6b, 0x33, 0xa, 0x23, 0x9, 0xd5,
  0xf9, 0xb1, 0x2c, 0xe0, 0x17, 0xd6, 0x75, 0x87, 0xaa, 0xfd, 0xa9, 0x76, 0xcd, 0x7d, 0x3f, 0x41,
  0x93, 0xbd, 0x67, 0x10, 0x4a, 0x38, 0xe, 0x54, 0x1d, 0x94, 0x4f, 0x2d, 0x7c, 0x36, 0xd7, 0x89,
  0x29, 0x6, 0x5f, 0xf8, 0x97, 0xbc, 0xca, 0xb6, 0x63, 0x52, 0x1f, 0xa4, 0xee, 0xe5, 0x7a, 0x26,
  0x81, 0xa0, 0xd, 0x6a, 0xf6, 0xdc, 0xdf, 0x18, 0x25, 0x8c, 0x9d, 0xa5, 0xd9, 0xbe, 0xac, 0x77,
  0x2a, 0xfe, 0x1e, 0xb2, 0x2f, 0x85, 0xb4, 0x9a, 0x1c, 0x47, 0xa6, 0xe4, 0x68, 0x95, 0xef, 0x42,
  0x83, 0x48, 0x2, 0x22, 0x98, 0x3a, 0x9e, 0x15, 0x92, 0xe7, 0xdb, 0x82, 0x1, 0x78, 0x3d, 0xed,
  0x3e, 0xf0, 0x51, 0x8a, 0xd3, 0xa3, 0x69, 0xe9, 0x73, 0x31, 0x4, 0x20, 0x5c, 0x61, 0x4b, 0x34,
  0xb9, 0xab, 0x7e, 0xc1, 0x62, 0xc, 0x6f, 0x7, 0x30, 0x91, 0x1a, 0xd2, 0x16, 0xe8, 0xec, 0x74,
  0xb8, 0x27, 0xf5, 0x72, 0x5a, 0x70, 0x39, 0xb3, 0xc7, 0x43, 0x8, 0x5d, 0xff, 0x50, 0xe2, 0x7b,
  0xfc, 0x79, 0x45, 0xf7, 0x2e, 0x13, 0x65, 0xa8, 0xbf, 0x35, 0x49, 0xae, 0x99, 0x7f, 0x8f, 0xfa,
  0xb, 0x3c, 0xf, 0x28, 0xd8, 0xea, 0xda, 0xc9, 0x57, 0xce, 0x21, 0xc4, 0xe1, 0x66, 0x40, 0x5e,
};
uint8_t XorTable[] =
{
  0x2a, 0x1, 0x2c, 0x3, 0x2e, 0x5, 0x30, 0x7, 0x32, 0x9, 0x34, 0xb, 0x36, 0xd, 0x38, 0xf,
  0x3a, 0x11, 0x3c, 0x13, 0x3e, 0x15, 0x40, 0x17, 0x42, 0x19, 0x44, 0x1b, 0x46, 0x1d, 0x48, 0x1f,
  0x4a, 0x21, 0x4c, 0x23, 0x4e, 0x25, 0x50, 0x27, 0x52, 0x29, 0x54, 0x2b, 0x56, 0x2d, 0x58, 0x2f,
  0x5a, 0x31, 0x5c, 0x33, 0x5e, 0x35, 0x60, 0x37, 0x62, 0x39, 0x64, 0x3b, 0x66, 0x3d, 0x68, 0x3f,
  0x6a, 0x41, 0x6c, 0x43, 0x6e, 0x45, 0x70, 0x47, 0x72, 0x49, 0x74, 0x4b, 0x76, 0x4d, 0x78, 0x4f,
  0x7a, 0x51, 0x7c, 0x53, 0x7e, 0x55, 0x80, 0x57, 0x82, 0x59, 0x84, 0x5b, 0x86, 0x5d, 0x88, 0x5f,
  0x8a, 0x61, 0x8c, 0x63, 0x8e, 0x65, 0x90, 0x67, 0x92, 0x69, 0x94, 0x6b, 0x96, 0x6d, 0x98, 0x6f,
  0x9a, 0x71, 0x9c, 0x73, 0x9e, 0x75, 0xa0, 0x77, 0xa2, 0x79, 0xa4, 0x7b, 0xa6, 0x7d, 0xa8, 0x7f,
  0xaa, 0x81, 0xac, 0x83, 0xae, 0x85, 0xb0, 0x87, 0xb2, 0x89, 0xb4, 0x8b, 0xb6, 0x8d, 0xb8, 0x8f,
  0xba, 0x91, 0xbc, 0x93, 0xbe, 0x95, 0xc0, 0x97, 0xc2, 0x99, 0xc4, 0x9b, 0xc6, 0x9d, 0xc8, 0x9f,
  0xca, 0xa1, 0xcc, 0xa3, 0xce, 0xa5, 0xd0, 0xa7, 0xd2, 0xa9, 0xd4, 0xab, 0xd6, 0xad, 0xd8, 0xaf,
  0xda, 0xb1, 0xdc, 0xb3, 0xde, 0xb5, 0xe0, 0xb7, 0xe2, 0xb9, 0xe4, 0xbb, 0xe6, 0xbd, 0xe8, 0xbf,
  0xea, 0xc1, 0xec, 0xc3, 0xee, 0xc5, 0xf0, 0xc7, 0xf2, 0xc9, 0xf4, 0xcb, 0xf6, 0xcd, 0xf8, 0xcf,
  0xfa, 0xd1, 0xfc, 0xd3, 0xfe, 0xd5, 0x00, 0xd7, 0x02, 0xd9, 0x04, 0xdb, 0x06, 0xdd, 0x08, 0xdf,
  0x0a, 0xe1, 0x0c, 0xe3, 0x0e, 0xe5, 0x10, 0xe7, 0x12, 0xe9, 0x14, 0xeb, 0x16, 0xed, 0x18, 0xef,
  0x1a, 0xf1, 0x1c, 0xf3, 0x1e, 0xf5, 0x20, 0xf7, 0x22, 0xf9, 0x24, 0xfb, 0x26, 0xfd, 0x28, 0xff,
};

1.8. Putting it all together

We can then use the following C program to get the flag:

#include <stdio.h>
#include <stdint.h>
#include <assert.h>

enum { flagLen = 35 };

uint8_t EncryptedFlag[] =
{
  0x7, 0xbb, 0xcb, 0xe, 0x86, 0x6, 0x5d, 0x92, 0x57, 0xa6, 0x2c, 0xa2, 0x39, 0x6e, 0x7f, 0x24,
  0xbf, 0x98, 0x4c, 0x1, 0xd3, 0xc7, 0x12, 0x9d, 0x43, 0xf, 0x39, 0xa1, 0x53, 0x33, 0x8d, 0x8c,
  0x2f, 0x30, 0x52, 0x0,
};

uint8_t PermuteTable[] =
{
  0x19, 0xc3, 0xf2, 0xa2, 0x4c, 0xcc, 0x53, 0x64, 0x32, 0x5b, 0xc8, 0xb0, 0xc6, 0x90, 0x4e, 0xeb,
  0x9f, 0x8d, 0xa7, 0xe3, 0x5, 0xc2, 0x1b, 0xd1, 0x24, 0xf3, 0x86, 0xaf, 0x6c, 0x56, 0xcb, 0xc5,
  0x3, 0xf4, 0xb7, 0xf1, 0x9c, 0x71, 0xdd, 0x46, 0x8b, 0xd4, 0x4d, 0x2b, 0x58, 0x6e, 0x37, 0x14,
  0x60, 0x88, 0xb5, 0x44, 0x84, 0x59, 0xde, 0x96, 0x12, 0x3b, 0x6d, 0xe6, 0xfb, 0xd0, 0xa1, 0x11,
  0x0, 0xba, 0x8e, 0xc0, 0xbb, 0x80, 0x55, 0xcf, 0xad, 0x9b, 0x6b, 0x33, 0xa, 0x23, 0x9, 0xd5,
  0xf9, 0xb1, 0x2c, 0xe0, 0x17, 0xd6, 0x75, 0x87, 0xaa, 0xfd, 0xa9, 0x76, 0xcd, 0x7d, 0x3f, 0x41,
  0x93, 0xbd, 0x67, 0x10, 0x4a, 0x38, 0xe, 0x54, 0x1d, 0x94, 0x4f, 0x2d, 0x7c, 0x36, 0xd7, 0x89,
  0x29, 0x6, 0x5f, 0xf8, 0x97, 0xbc, 0xca, 0xb6, 0x63, 0x52, 0x1f, 0xa4, 0xee, 0xe5, 0x7a, 0x26,
  0x81, 0xa0, 0xd, 0x6a, 0xf6, 0xdc, 0xdf, 0x18, 0x25, 0x8c, 0x9d, 0xa5, 0xd9, 0xbe, 0xac, 0x77,
  0x2a, 0xfe, 0x1e, 0xb2, 0x2f, 0x85, 0xb4, 0x9a, 0x1c, 0x47, 0xa6, 0xe4, 0x68, 0x95, 0xef, 0x42,
  0x83, 0x48, 0x2, 0x22, 0x98, 0x3a, 0x9e, 0x15, 0x92, 0xe7, 0xdb, 0x82, 0x1, 0x78, 0x3d, 0xed,
  0x3e, 0xf0, 0x51, 0x8a, 0xd3, 0xa3, 0x69, 0xe9, 0x73, 0x31, 0x4, 0x20, 0x5c, 0x61, 0x4b, 0x34,
  0xb9, 0xab, 0x7e, 0xc1, 0x62, 0xc, 0x6f, 0x7, 0x30, 0x91, 0x1a, 0xd2, 0x16, 0xe8, 0xec, 0x74,
  0xb8, 0x27, 0xf5, 0x72, 0x5a, 0x70, 0x39, 0xb3, 0xc7, 0x43, 0x8, 0x5d, 0xff, 0x50, 0xe2, 0x7b,
  0xfc, 0x79, 0x45, 0xf7, 0x2e, 0x13, 0x65, 0xa8, 0xbf, 0x35, 0x49, 0xae, 0x99, 0x7f, 0x8f, 0xfa,
  0xb, 0x3c, 0xf, 0x28, 0xd8, 0xea, 0xda, 0xc9, 0x57, 0xce, 0x21, 0xc4, 0xe1, 0x66, 0x40, 0x5e,
};

uint8_t XorTable[] =
{
  0x2a, 0x1, 0x2c, 0x3, 0x2e, 0x5, 0x30, 0x7, 0x32, 0x9, 0x34, 0xb, 0x36, 0xd, 0x38, 0xf,
  0x3a, 0x11, 0x3c, 0x13, 0x3e, 0x15, 0x40, 0x17, 0x42, 0x19, 0x44, 0x1b, 0x46, 0x1d, 0x48, 0x1f,
  0x4a, 0x21, 0x4c, 0x23, 0x4e, 0x25, 0x50, 0x27, 0x52, 0x29, 0x54, 0x2b, 0x56, 0x2d, 0x58, 0x2f,
  0x5a, 0x31, 0x5c, 0x33, 0x5e, 0x35, 0x60, 0x37, 0x62, 0x39, 0x64, 0x3b, 0x66, 0x3d, 0x68, 0x3f,
  0x6a, 0x41, 0x6c, 0x43, 0x6e, 0x45, 0x70, 0x47, 0x72, 0x49, 0x74, 0x4b, 0x76, 0x4d, 0x78, 0x4f,
  0x7a, 0x51, 0x7c, 0x53, 0x7e, 0x55, 0x80, 0x57, 0x82, 0x59, 0x84, 0x5b, 0x86, 0x5d, 0x88, 0x5f,
  0x8a, 0x61, 0x8c, 0x63, 0x8e, 0x65, 0x90, 0x67, 0x92, 0x69, 0x94, 0x6b, 0x96, 0x6d, 0x98, 0x6f,
  0x9a, 0x71, 0x9c, 0x73, 0x9e, 0x75, 0xa0, 0x77, 0xa2, 0x79, 0xa4, 0x7b, 0xa6, 0x7d, 0xa8, 0x7f,
  0xaa, 0x81, 0xac, 0x83, 0xae, 0x85, 0xb0, 0x87, 0xb2, 0x89, 0xb4, 0x8b, 0xb6, 0x8d, 0xb8, 0x8f,
  0xba, 0x91, 0xbc, 0x93, 0xbe, 0x95, 0xc0, 0x97, 0xc2, 0x99, 0xc4, 0x9b, 0xc6, 0x9d, 0xc8, 0x9f,
  0xca, 0xa1, 0xcc, 0xa3, 0xce, 0xa5, 0xd0, 0xa7, 0xd2, 0xa9, 0xd4, 0xab, 0xd6, 0xad, 0xd8, 0xaf,
  0xda, 0xb1, 0xdc, 0xb3, 0xde, 0xb5, 0xe0, 0xb7, 0xe2, 0xb9, 0xe4, 0xbb, 0xe6, 0xbd, 0xe8, 0xbf,
  0xea, 0xc1, 0xec, 0xc3, 0xee, 0xc5, 0xf0, 0xc7, 0xf2, 0xc9, 0xf4, 0xcb, 0xf6, 0xcd, 0xf8, 0xcf,
  0xfa, 0xd1, 0xfc, 0xd3, 0xfe, 0xd5, 0x00, 0xd7, 0x02, 0xd9, 0x04, 0xdb, 0x06, 0xdd, 0x08, 0xdf,
  0x0a, 0xe1, 0x0c, 0xe3, 0x0e, 0xe5, 0x10, 0xe7, 0x12, 0xe9, 0x14, 0xeb, 0x16, 0xed, 0x18, 0xef,
  0x1a, 0xf1, 0x1c, 0xf3, 0x1e, 0xf5, 0x20, 0xf7, 0x22, 0xf9, 0x24, 0xfb, 0x26, 0xfd, 0x28, 0xff,
};

uint8_t ReversePermute(uint8_t val)
{
  for(int i = 0; i < 256; ++i)
    if(val == PermuteTable[i])
      return i;

  assert(0);
}

uint8_t ror(uint8_t b) { return (b >> 3) | (b << 5); }

void Decrypt(char* theFlag)
{
  for(int i = flagLen - 1; i >= 0; --i)
  {
    for(int k = 0; k < flagLen; ++k)
      theFlag[k] ^= XorTable[i + k];

    theFlag[i] -= theFlag[i + 1];

    for(int k = 0; k < flagLen; ++k)
      theFlag[k] = ror(ReversePermute(theFlag[k]));
  }
}

int main(int argc, char* argv[])
{
  Decrypt(EncryptedFlag);
  printf("Flag: '%.*s'\n", flagLen, EncryptedFlag);

  return 0;
}

And then we get the flag!

Thanks Xarkes for this sneaky one :D

The Complexity Elephant

Topics

Software Development

Collision detection

Procedural content generation

Software Security

Meta