Introduction

This was the last binary challenge released on the second day of the CTF, worth 300 points.

$ file lost.elf 
lost.elf: ELF 64-bit LSB  executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=f9e196b2aad4d644223e22e424c8c192bdb41175, stripped

gdb-peda$ checksec
CANARY    : disabled
FORTIFY   : disabled
NX        : ENABLED
PIE       : disabled
RELRO     : disabled

This looks promising: no exotic architecture, no static linking, no stack canaries, no PIE. Should be a simple exploitation challenge, ready to pop a shell.

Reverse Engineering

int __cdecl main(int argc, const char **argv, const char **envp)
{
  addr_len = 16;
  flagStream_ = fopen("flag.txt", "rb");
  if ( !flagStream_ )
    exit(1);
  flagStream = flagStream_;
  fread(&flag, 1uLL, 0x80uLL, flagStream_);
  fclose(flagStream);
  create_bpf_network_filter();
  // This initializes g_filter with the result from the bpf syscall.
  // Note: for my tests, I edited the binary to use the "lo" interface instead.
  listenSock = create_raw_socket_bind_port_4352_udp("ens3");
  listenSock_ = listenSock;
  // SO_ATTACH_BPF.
  if ( listenSock < 0 || (exitcode = setsockopt(listenSock, 1, 50, &g_filter, 4u)) != 0 )
  {
    exitcode = 1;
  }
  else
  {
    // Receive somthing on port 4352 (only if it passes the packet filter code).
    while ( recvfrom(listenSock_, &recvdPacket, 0x400uLL, 0, &addr, &addr_len) )
    {
      udpSocket = socket(2, 2, 17);
      recipient.sa_family = 2;
      // port = 0x1337 = 4919
      *(_WORD *)&recipient.sa_data[0] = 0x3713;
      // v20 contains the IP that sent the packet, so the binary
      // will send a reply with the flag to the same IP on port 4919.
      *(_DWORD *)&recipient.sa_data[2] = v20;
      // < inline strlen nonsense code .. >
      sendto(
        udpSocket,
        &flag,
        len,
        0,
        &recipient,
        0x10u);
    }
  }
  return exitcode;
}

The code for creating packet filter, binding the socket, etc. is fairly straight forward, so I will not dump the code here as well. So apparently, we do have to deal with some exotic architecture after all: BPF.

I browsed the interwebs to find BPF (or in this case, eBPF) disassemblers, but none worked properly, so I started hand analyzing the code. It became pretty evident that I would not have enough time during the last few hours of the CTF to analyze the code (0x274 instructions of some weird architecture I do not know..), so I decided to move on to different challenges instead. After my flight home, equipped with stable non-hotel Internet, I started digging more into the architecture because I really wanted to solve this challenge. I am not sure if this is the inteded solution, but after a couple of hours I was able to solve it as well.

Kudos to StratumAuhuur for solving it so quickly during the CTF, deservedly getting first place!

Just In Time

Just in time - get it? ...

During my Googling-Frenzy on BPF and eBPF, I found several tools to debug and assemble these filters, but the disassemblers just would not work. Additionally, my kernel version does not support this, and during the CTF I did not have other VMs with newer kernels ready (lessons learned: prepare better). At last, I found something that eventually allowed me to solve the challenge: /proc/sys/net/core/bpf_jit_enable [0].

Values :
    0 - disable the JIT (default value)
    1 - enable the JIT
    2 - enable the JIT and ask the compiler to emit traces on kernel log.

If we set this to 1, the kernel will emit x86_64 code for the network filter. Now we are getting somewhere! With option 2, not only will this generate sane code, it will also log it!

dmesg
[ 3671.038259] flen=628 proglen=2479 pass=3 image=ffffffffa01035b2 from=lost.elf pid=90
[ 3671.038300] JIT code: 00000000: 55 48 89 e5 48 81 ec 28 02 00 00 48 89 9d d8 fd
[ 3671.038315] JIT code: 00000010: ff ff 4c 89 ad e0 fd ff ff 4c 89 b5 e8 fd ff ff
[ 3671.038326] JIT code: 00000020: 4c 89 bd f0 fd ff ff 31 c0 4d 31 ed 48 89 85 f8
...

Glorious!

Packet Filter Code

We know the address where the code is emitted to, so relocating it should not be difficult. Turns out, other than a few calls at the beginning to read out packet data, the whole code is a linear series of XORs and shifts and all that jazz, until it finally performs a comparison, deciding whether the packet should be allowed to pass through or not.

seg016:000000000000000A                 shl     r14, 8
seg016:000000000000000E                 and     r14, 0FF0000h
seg016:0000000000000015                 mov     rdi, rax
seg016:0000000000000018                 shl     rdi, 18h
seg016:000000000000001C                 or      r14, rdi
seg016:000000000000001F                 mov     rdi, rax
seg016:0000000000000022                 shr     rdi, 18h
seg016:0000000000000026                 and     rdi, 0FFh
seg016:000000000000002D                 or      r14, rdi
seg016:0000000000000030                 shr     rax, 8
seg016:0000000000000034                 and     rax, 0FF00h
seg016:000000000000003B                 or      r14, rax
seg016:000000000000003E                 mov     r13, 0FFFFFFE0h
seg016:0000000000000048                 mov     rdi, r14
seg016:000000000000004B                 and     rdi, r13
seg016:000000000000004E                 shr     rdi, 5
seg016:0000000000000052                 mov     r15, r14
seg016:0000000000000055                 shl     r15, 4
seg016:0000000000000059                 xor     r15, rdi
seg016:000000000000005C                 mov     rax, rsi
seg016:000000000000005F                 mov     rdi, rax
seg016:0000000000000062                 shl     rdi, 8
seg016:0000000000000066                 and     rdi, 0FF0000h
seg016:000000000000006D                 mov     rsi, rax
seg016:0000000000000070                 shl     rsi, 18h
seg016:0000000000000074                 or      rdi, rsi
seg016:0000000000000077                 mov     rsi, rax
seg016:000000000000007A                 shr     rsi, 18h
seg016:000000000000007E                 and     rsi, 0FFh
seg016:0000000000000085                 or      rdi, rsi
seg016:0000000000000088                 shr     rax, 8
seg016:000000000000008C                 and     rax, 0FF00h
...
seg016:00000000000008B2                 mov     edx, 46245443h ; CT$F
seg016:00000000000008B7                 cmp     rsi, rd
...
seg016:00000000000008E5                 mov     edi, 42744968h ; hItB
seg016:00000000000008EA                 cmp     r14, rdi
...
seg016:0000000000000914                 leave
seg016:0000000000000915                 retn

I parsed the dmesg output and extracted all the bytes for the emitted packet filter function. After analyzing the function prologue, I was able to replace all the function calls at the beginning with simple constants (these calls are used to extract the first 8 bytes of the user data in the UDP packet). To make the whole analysis easier, I simply converted this function into a function taking two integer arguments. The result is a function taking two arguments, returing 1 on success and 0 on failure.

int packet_filter(unsigned int a1, unsigned int a2) {
 v2 = (a1 >> 8) & 0xFF00 | ((unsigned int)a1 >> 24) | (a1 << 24) | ((_DWORD)a1 << 8) & 0xFF0000;
  v3 = ((a2 >> 8) & 0xFF00 | ((unsigned int)a2 >> 24) | (a2 << 24) | ((_DWORD)a2 << 8) & 0xFF0000)
     - ((v2 + (((unsigned __int64)((unsigned int)v2 & 0xFFFFFFE0) >> 5) ^ 16 * v2)) ^ 0x69859111);
  v4 = v2 - ((v3 + (((unsigned __int64)((unsigned int)v3 & 0xFFFFFFE0) >> 5) ^ 16 * v3)) ^ 0x6DCA2938);
  v5 = v3 - ((v4 + (((unsigned __int64)((unsigned int)v4 & 0xFFFFFFE0) >> 5) ^ 16 * v4)) ^ 0x6DCA2938);
  v6 = v4 - ((v5 + (((unsigned __int64)((unsigned int)v5 & 0xFFFFFFE0) >> 5) ^ 16 * v5)) ^ 0x2D169D9F);
  v7 = v5 - ((v6 + (((unsigned __int64)((unsigned int)v6 & 0xFFFFFFE0) >> 5) ^ 16 * v6)) ^ 0xFFFFFFFFF6F49763LL);
  v8 = v6 - ((v7 + (((unsigned __int64)((unsigned int)v7 & 0xFFFFFFE0) >> 5) ^ 16 * v7)) ^ 0xFFFFFFFFF7762178LL);
  v9 = v7 - ((v8 + (((unsigned __int64)((unsigned int)v8 & 0xFFFFFFE0) >> 5) ^ 16 * v8)) ^ 0xFFFFFFFFF7762178LL);
  v10 = v8 - ((v9 + (((unsigned __int64)((unsigned int)v9 & 0xFFFFFFE0) >> 5) ^ 16 * v9)) ^ 0xFFFFFFFFBA85A3F1LL);
  v11 = v9 - ((v10 + (((unsigned __int64)((unsigned int)v10 & 0xFFFFFFE0) >> 5) ^ 16 * v10)) ^ 0xFFFFFFFFF0A7AA2DLL);
  v12 = v10 - ((v11 + (((unsigned __int64)((unsigned int)v11 & 0xFFFFFFE0) >> 5) ^ 16 * v11)) ^ 0xFFFFFFFFF4EC4254LL);
  v13 = v11 - ((v12 + (((unsigned __int64)((unsigned int)v12 & 0xFFFFFFE0) >> 5) ^ 16 * v12)) ^ 0x52703074);
  v14 = v12 - ((v13 + (((unsigned __int64)((unsigned int)v13 & 0xFFFFFFE0) >> 5) ^ 16 * v13)) ^ 0xFFFFFFFFB438B6BBLL);
  v15 = v13 - ((v14 + (((unsigned __int64)((unsigned int)v14 & 0xFFFFFFE0) >> 5) ^ 16 * v14)) ^ 0x56B4C89B);
  v16 = v14 - ((v15 + (((unsigned __int64)((unsigned int)v15 & 0xFFFFFFE0) >> 5) ^ 16 * v15)) ^ 0x7E983A94);
  v17 = v15 - ((v16 + (((unsigned __int64)((unsigned int)v16 & 0xFFFFFFE0) >> 5) ^ 16 * v16)) ^ 0xFFFFFFFFDFDF36C6LL);
  v18 = v16 - ((v17 + (((unsigned __int64)((unsigned int)v17 & 0xFFFFFFE0) >> 5) ^ 16 * v17)) ^ 0x41A7BD0D);
  v19 = v17 - ((v18 + (((unsigned __int64)((unsigned int)v18 & 0xFFFFFFE0) >> 5) ^ 16 * v18)) ^ 0xFFFFFFFFE060C0DBLL);
  v20 = v18 - ((v19 + (((unsigned __int64)((unsigned int)v19 & 0xFFFFFFE0) >> 5) ^ 16 * v19)) ^ 0x7C0E5B70);
  v21 = v19 - ((v20 + (((unsigned __int64)((unsigned int)v20 & 0xFFFFFFE0) >> 5) ^ 16 * v20)) ^ 0x42294722);
  v22 = v20 - ((v21 + (((unsigned __int64)((unsigned int)v21 & 0xFFFFFFE0) >> 5) ^ 16 * v21)) ^ 0x3B5ACFD7);
  v23 = v21 - ((v22 + (((unsigned __int64)((unsigned int)v22 & 0xFFFFFFE0) >> 5) ^ 16 * v22)) ^ 0x3B5ACFD7);
  v24 = v22 - ((v23 + (((unsigned __int64)((unsigned int)v23 & 0xFFFFFFE0) >> 5) ^ 16 * v23)) ^ 0x5BA53B0);
  v25 = v23 - ((v24 + (((unsigned __int64)((unsigned int)v24 & 0xFFFFFFE0) >> 5) ^ 16 * v24)) ^ 0x3F9F67FE);
  v26 = v24 - ((v25 + (((unsigned __int64)((unsigned int)v25 & 0xFFFFFFE0) >> 5) ^ 16 * v25)) ^ 0xFFFFFFFFC8C9D629LL);
  v27 = v25 - ((v26 + (((unsigned __int64)((unsigned int)v26 & 0xFFFFFFE0) >> 5) ^ 16 * v26)) ^ 0xFFFFFFFFC8C9D629LL);
  v28 = v26 - ((v27 + (((unsigned __int64)((unsigned int)v27 & 0xFFFFFFE0) >> 5) ^ 16 * v27)) ^ 0x330748C);
  v29 = v27 - ((v28 + (((unsigned __int64)((unsigned int)v28 & 0xFFFFFFE0) >> 5) ^ 16 * v28)) ^ 0xFFFFFFFFC94B603ELL);
  v30 = v28 - ((v29 + (((unsigned __int64)((unsigned int)v29 & 0xFFFFFFE0) >> 5) ^ 16 * v29)) ^ 0xFFFFFFFFC27CE8F3LL);
  v31 = v29 - ((v30 + (((unsigned __int64)((unsigned int)v30 & 0xFFFFFFE0) >> 5) ^ 16 * v30)) ^ 0x2B13E685);
  v32 = v30 - ((v31 + (((unsigned __int64)((unsigned int)v31 & 0xFFFFFFE0) >> 5) ^ 16 * v31)) ^ 0xFFFFFFFF8CDC6CCCLL);
  v33 = v31 - ((v32 + (((unsigned __int64)((unsigned int)v32 & 0xFFFFFFE0) >> 5) ^ 16 * v32)) ^ 0x24456F3A);
  v34 = v32 - ((v33 + (((unsigned __int64)((unsigned int)v33 & 0xFFFFFFE0) >> 5) ^ 16 * v33)) ^ 0x4FEBEF45);
  v35 = v33 - ((v34 + (((unsigned __int64)((unsigned int)v34 & 0xFFFFFFE0) >> 5) ^ 16 * v34)) ^ 0x288A0761);
  v36 = v34 - ((v35 + (((unsigned __int64)((unsigned int)v35 & 0xFFFFFFE0) >> 5) ^ 16 * v35)) ^ 0xFFFFFFFF8A528DA8LL);
  v37 = v35 - ((v36 + (((unsigned __int64)((unsigned int)v36 & 0xFFFFFFE0) >> 5) ^ 16 * v36)) ^ 0xFFFFFFFFB1B4758CLL);
  v38 = v36 - ((v37 + (((unsigned __int64)((unsigned int)v37 & 0xFFFFFFE0) >> 5) ^ 16 * v37)) ^ 0x499F020F);
  v39 = v37 - ((v38 + (((unsigned __int64)((unsigned int)v38 & 0xFFFFFFE0) >> 5) ^ 16 * v38)) ^ 0xFFFFFFFFB235FFA1LL);
  v40 = v38 - ((v39 + (((unsigned __int64)((unsigned int)v39 & 0xFFFFFFE0) >> 5) ^ 16 * v39)) ^ 0x13FE85E8);
  v41 = v39 - ((v40 + (((unsigned __int64)((unsigned int)v40 & 0xFFFFFFE0) >> 5) ^ 16 * v40)) ^ 0x13FE85E8);
  v42 = v40 - ((v41 + (((unsigned __int64)((unsigned int)v41 & 0xFFFFFFE0) >> 5) ^ 16 * v41)) ^ 0xFFFFFFFFD70E0861LL);
  v43 = v41 - ((v42 + (((unsigned __int64)((unsigned int)v42 & 0xFFFFFFE0) >> 5) ^ 16 * v42)) ^ 0xD300E9D);
  v44 = v42 - ((v43 + (((unsigned __int64)((unsigned int)v43 & 0xFFFFFFE0) >> 5) ^ 16 * v43)) ^ 0x1174A6C4);
  v45 = v43 - ((v44 + (((unsigned __int64)((unsigned int)v44 & 0xFFFFFFE0) >> 5) ^ 16 * v44)) ^ 0x1174A6C4);
  v46 = v44 - ((v45 + (((unsigned __int64)((unsigned int)v45 & 0xFFFFFFE0) >> 5) ^ 16 * v45)) ^ 0xFFFFFFFFD0C11B2BLL);
  v47 = v45 - ((v46 + (((unsigned __int64)((unsigned int)v46 & 0xFFFFFFE0) >> 5) ^ 16 * v46)) ^ 0xFFFFFFFF9A9F14EFLL);
  v48 = v46 - ((v47 + (((unsigned __int64)((unsigned int)v47 & 0xFFFFFFE0) >> 5) ^ 16 * v47)) ^ 0xFFFFFFFF9B209F04LL);
  v49 = v47 - ((v48 + (((unsigned __int64)((unsigned int)v48 & 0xFFFFFFE0) >> 5) ^ 16 * v48)) ^ 0xFFFFFFFFFC679B36LL);
  v50 = v48 - ((v49 + (((unsigned __int64)((unsigned int)v49 & 0xFFFFFFE0) >> 5) ^ 16 * v49)) ^ 0x5E30217D);
  v51 = v49 - ((v50 + (((unsigned __int64)((unsigned int)v50 & 0xFFFFFFE0) >> 5) ^ 16 * v50)) ^ 0xFFFFFFFFFCE9254BLL);
  v52 = v50 - ((v51 + (((unsigned __int64)((unsigned int)v51 & 0xFFFFFFE0) >> 5) ^ 16 * v51)) ^ 0xFFFFFFFF9896BFE0LL);
  v53 = v51 - ((v52 + (((unsigned __int64)((unsigned int)v52 & 0xFFFFFFE0) >> 5) ^ 16 * v52)) ^ 0xFFFFFFFFF61AAE00LL);
  v54 = v52 - ((v53 + (((unsigned __int64)((unsigned int)v53 & 0xFFFFFFE0) >> 5) ^ 16 * v53)) ^ 0x57E33447);
  v55 = v53 - ((v54 + (((unsigned __int64)((unsigned int)v54 & 0xFFFFFFE0) >> 5) ^ 16 * v54)) ^ 0xFFFFFFFFFA5F4627LL);
  v56 = v54 - ((v55 + (((unsigned __int64)((unsigned int)v55 & 0xFFFFFFE0) >> 5) ^ 16 * v55)) ^ 0x2242B820);
  v57 = v55 - ((v56 + (((unsigned __int64)((unsigned int)v56 & 0xFFFFFFE0) >> 5) ^ 16 * v56)) ^ 0xFFFFFFFF8389B452LL);
  v58 = v56 - ((v57 + (((unsigned __int64)((unsigned int)v57 & 0xFFFFFFE0) >> 5) ^ 16 * v57)) ^ 0xFFFFFFFFE5523A99LL);
  v59 = v57 - ((v58 + (((unsigned __int64)((unsigned int)v58 & 0xFFFFFFE0) >> 5) ^ 16 * v58)) ^ 0xFFFFFFFFE5523A99LL);
  v60 = v58 - ((v59 + (((unsigned __int64)((unsigned int)v59 & 0xFFFFFFE0) >> 5) ^ 16 * v59)) ^ 0x1FB8D8FC);
  v61 = v59 - ((v60 + (((unsigned __int64)((unsigned int)v60 & 0xFFFFFFE0) >> 5) ^ 16 * v60)) ^ 0xFFFFFFFFE5D3C4AELL);
  v62 = v60 - ((v61 + (((unsigned __int64)((unsigned int)v61 & 0xFFFFFFE0) >> 5) ^ 16 * v61)) ^ 0xFFFFFFFFDF054D63LL);
  v63 = v61 - ((v62 + (((unsigned __int64)((unsigned int)v62 & 0xFFFFFFE0) >> 5) ^ 16 * v62)) ^ 0xFFFFFFFFDF054D63LL);
  v64 = v62 - ((v63 + (((unsigned __int64)((unsigned int)v63 & 0xFFFFFFE0) >> 5) ^ 16 * v63)) ^ 0xFFFFFFFFA964D13CLL);
  v65 = v63 - ((v64 + (((unsigned __int64)((unsigned int)v64 & 0xFFFFFFE0) >> 5) ^ 16 * v64)) ^ 0xFFFFFFFFE349E58ALL);
  v66 = 0xFFFFLL;
  if ( (v65 & 0xFFFFFFFF) != 0x46245443 )
    v66 = 0LL;
  if ( ((v64 - ((v65 + (((unsigned __int64)((unsigned int)v65 & 0xFFFFFFFF) >> 5) ^ 16 * v65)) ^ 0x6C7453B5)) & 0xFFFFFFFF) != 0x42744968 )
    v66 = 0LL;
  return v66;
}

This looks suspiciously like (X)TEA, but with non-standard constants. I could not figure out the reverse operations, so instead I opted for an automated solver. I had no high hopes for z3, but tried it regardless. As expected, it simply turned my laptop into a heating device for a couple of minutes, until I killed it.

KLEE

I assumed that KLEE would also not fare too well, but surprisingly it coughed up a valid solution within approx. 3 seconds. I used the default docker image for klee and adjusted the C code:

  unsigned int a1, a2; 
  klee_make_symbolic(&a1, sizeof(a1), "a1"); 
  klee_make_symbolic(&a2, sizeof(a2), "a2"); 

  // Code..

  v65 = v65 & 0xffffffff; 
  v66 = v66 & 0xffffffff; 

  if (v65 != 0x46245443) 
      return 1; 

  if (v66 != 0x42744968) 
      return 1; 

  // success. 
  klee_assert(0); 
  return 0;
$ clang -emit-llvm -c -g x.c
$ klee x.bc
KLEE: output directory is "/home/klee/x/klee-out-0"
Using STP solver backend
KLEE: WARNING: undefined reference to function: klee_assert
KLEE: WARNING ONCE: calling external: klee_assert(0)
KLEE: ERROR: /home/klee/x/x.c:157: failed external call: klee_assert
KLEE: NOTE: now ignoring this error at this location

KLEE: done: total instructions = 1312
KLEE: done: completed paths = 3
KLEE: done: generated tests = 3

$ ktest-tool --write-ints klee-last/test000003.ktest
ktest file : 'klee-last/test000003.ktest'
args       : ['x.bc']
num objects: 2
object    0: name: b'a1'
object    0: size: 4
object    0: data: -870510808
object    1: name: b'a2'
object    1: size: 4
object    1: data: 810027724

These 2 integers fulfill the requirements:

>>> hex(-870510808&0xffffffff)
'0xcc1d0f28'
>>> hex(810027724&0xffffffff)
'0x30480acc'

Lets test this:

# Wait for the flag here..
$ nc -u -l -p 4919

# Send packet:
$ echo -ne "\x28\x0f\x1d\xcc\xcc\x0a\x48\x30" | nc -u localhost 4352

# And on the nc we were listening:
slowpoke{only_one_day_too_late_for_the_2000_euro...idiot}

Well, that is a bit harsh.. then again, I do not know what the real flag would be since the services have been turned off right after the CTF. ;) This would have given us enough points for second place.. but there is always next year.

Huge thanks to the HITB CTF organizers and all the teams for an amazing event. The whole CTF infrastructure, challenges, and organization were impressive, there were no issues whatsoever, everything just worked (tm).

Congratulations to StratumAuhuur, Hack.ERS, and KITCTF, well done!

References

[0] https://www.kernel.org/doc/Documentation/sysctl/net.txt


Sharif CTF 2016 - Misc 300 - impossible game

10 February 2016 by sku

Writeup for the misc challenge impossible-game

read more

Sharif CTF 2016 - Web 250 - oldpersian

06 February 2016 by sku

Writeup for the web challenge oldpersian

read more

HackIm CTF - Exploitation 200 - sandman

03 February 2016 by sku

Writeup for the pwnable challenge sandman

read more

HackIm CTF - Exploitation 300 - cman

03 February 2016 by sku

Writeup for the pwnable challenge cman

read more

HackIm CTF - Exploitation 100 - pinkfloyd

31 January 2016 by sku

Writeup for the pwnable challenge pinkfloyd

read more

Insomnihack Teaser 2016 - rbaced1

20 January 2016 by sku

Writeup for the pwnable challenge rbaced1

read more

Insomnihack Teaser 2016 - toasted

20 January 2016 by sku

Writeup for the pwnable challenge toasted

read more

SECCON Online CTF 2015 - Exec dmesg

06 December 2015 by sku

Writeup for the forensics challenge Exec dmesg

read more

SECCON Online CTF 2015 - Reverse-Engineering Android APK 2

06 December 2015 by sku

Writeup for the reverse engineering and web exploitation challenge APK 2.

read more