HITB CTF 2016 - Binary 300
27 May 2016 by skuIntroduction
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