Buffer Overflows

In order to understand how buffer overflows work, we must first understand how memory is laid out.

We’re going to work in the 32-bit x86 architecture because it’s a little simpler to learn about. However, the 64-bit x86-64 architecture is more common in computers today. This is also different that the ARM architecture used by many IoT devices. Nevertheless, the principles of buffer overflows remain the same across architectures.

Layout of memory

Programs are laid out in virtual memory and are organized by a memory map containing several key areas such as the stack and heap. Virtual memory is an abstraction managed by the OS that allows the program to occupy the entire addressable memory space as if it was the only process on the computer.

When a program executes, the OS loads everything it needs into memory and lays it out in following way:

(Highest)
0xffffffff  |------------|
            |   kernel   | holds environment variables,
            |            | command-line arguments, etc.
            |------------|
            |   stack    | holds local variables 
            |------------|          
            |            |          |
            |            |         \ /
            |            |          v
            |            |          direction of stack growth
            |            |
            |            |
            |            |          direction of heap growth
            |            |          ^
            |            |         / \
            |            |          |
            |------------|          
            |    heap    | holds dynamically allocated data
            |------------|
            |    data    | holds global and static variables
            |------------|
            |    text    | holds executable code (read only)
0x00000000  |------------|
(Lowest)

Stack Frame

A stack is a last-in first-out data structure. In this case you can think of the stack as being a little bit like a notebook that can be used to keep notes. A stack frame is a region of the stack which is dedicated to the execution of a particular function.

When a new function is called, things are added to the stack. When a function completes, all those things are removed from the stack. The program needs to keep track of a several important things:

  1. Where the current function’s stack frame begins
  2. Where the current function’s stack frame ends
  3. What instruction the current function is to execute next

To keep track of this, the system uses the following hardware registers:

  • ebp: the base pointer (also called the frame pointer), which points to the bottom of the stack frame. It is fixed within the current stack frame.
  • esp: the stack pointer, which points to the current top of the stack frame. It changes (downward) as the stack grows.
  • eip: the instruction pointer, which points points to the next instruction (in the text region) to be executed.

The relationship between the registers and memory looks like this:

CPU registers:              ebp  esp  eip
                              |    |    |
                              |    |    |
Memory address                |    |    |
(High)      |            |    |    |    |
            |            |    |    |    |
            |------------|<---/    |    |
            |  current   |         |    |
            |   stack    |         |    |
            |   frame    |         |    |
            |------------|<--------/    |
            |            |              |
            |            |              |
            |     .      |              |
            |     .      |              |
            |     .      |              |
            |            |              |
            |            |              |
            |------------|              |
            |            |              |
            |   text     |              |
            |   region   |              |
            |            |              |
            |            |<-------------/
(low)       |            |

Calling a Function

When a function is called, the system creates a new stack frame. The new function becomes the current function and the previous function is called the calling function.

The system must now do two things:

  1. Save the values of ebp, esp and eip, of the calling function:
    • Any arguments for the new function are pushed on the stack.
    • The calling function’s eip and ebp are then pushed to the stack (in fact all the CPU’s registers are pushed to the stack, but we’ve omitted them for brevity).
  2. Set the values of ebp, esp and eip of the current function:
    • The calling functions eip + 4 bytes becomes the current functions ebp
    • Space for current function’s local variables are allocated onto the stack, and current function’s esp grows downwards accordingly.

The memory now looks like this:

CPU registers:              ebp  esp  eip
                              |    |    |
                              |    |    |
Memory address                |    |    |
(High)                        |    |    |
            |            |    |    |    |
    Calling |   ...      |    |    |    |
 function's |   arg 3    |    |    |    |
      stack |   arg 2    |    |    |    |
      frame |   arg 1    |    |    |    |
            | eip (prev) |    |    |    |
            | ebp (prev) |<---/    |    |
    Current | local var1 |         |    |
      stack | local var2 |         |    |
      frame | local var3 |         |    |
            |------------|<--------/    |
            |            |              |
            |     .      |              |
            |     .      |              |
            |     .      |              |
            |            |              |
            |------------|              |
            |            |              |
            |            |<-------------/
            |   text     |              
            |   region   |              
            |            |              
            |            |
(low)       |            |

Writing strings to Memory

Suppose during the execution of the current function a string is copied into memory. Strings have the interesting property that they are copied from low to high addresses. If you combine this with a buffer overflow vulnerability (the ability to write beyond the bounds of allocated memory), you could potentially overwrite the calling function’s return address.

For example, if we had a C program that looked like this:

#include <string.h>

void foo()
{
  char b[12];
  gets(buf);  // no bounds checking
}

int main (int argc, char **argv)
{
   foo();
   return 0;
}

Then when foo() is initially called, memory looks like this:

CPU registers:              ebp  esp  eip
                              |    |    |
                              |    |    |
Memory address                |    |    |
(High)                        |    |    |
            |            |    |    |    |
            |     .      |    |    |    |
     main's |     .      |    |    |    |
      stack |     .      |    |    |    |
      frame |     .      |    |    |    |
            | eip (prev) |    |    |    |
            | ebp (prev) |<---/    |    |
      foo's | buf[8-12]  |         |    |
      stack | buf[4-7]   |         |    |
      frame | buf[0-3]   |         |    |
            |------------|<--------/    |
            |            |              |
            |     .      |              |
            |     .      |              |
            |     .      |              |
            |            |              |
            |------------|              |
            |            |              |
            |            |<-------------/
            |   text     |              
            |   region   |              
            |            |              
            |            |
(low)       |            |

Suppose we were to input the string AAAABBBBCCCCDDDDEEEE. Since there is no bounds checking with the gets() function, the eip and ebp of main will be overwritten!

CPU registers:              ebp  esp  eip
                              |    |    |
                              |    |    |
Memory address                |    |    |
(High)                        |    |    |
            |            |    |    |    |
            |     .      |    |    |    |
     main's |     .      |    |    |    |
      stack |     .      |    |    |    |
      frame |     .      |    |    |    |
            |    EEEE    |    |    |    |
            |    DDDD    |<---/    |    |
      foo's |    CCCC    |         |    |
      stack |    BBBB    |         |    |
      frame |    AAAA    |         |    |
            |------------|<--------/    |
            |            |              |
            |     .      |              |
            |     .      |              |
            |     .      |              |
            |            |              |
            |------------|              |
            |            |              |
            |            |<-------------/
            |   text     |              
            |   region   |              
            |            |              
            |            |
(low)       |            |

When the function foo returns, the current stack frame is unallocated, and the contents of the previous eip are loaded into the eip register, in this case is the string “EEEE” (i.e., \x69\x69\x69\x69), meaning the next instruction the program will execute is whatever lives at address 0x69696969.

Ok so here’s an idea. What if we created a buffer overflow that overwrites the return address of the instruction pointer such that it returned into the stack? It would start to execute whatever was in the stack! If you loaded the stack with malicious code, you cause this code to run!

Buffer Overflow Attacks

Buffer overflows on the stack are a common exploitation method. Learn the basics in this buffer overflow attack video

A typical objective of such an attack is to inject malicious code to provide the attacker with a shell. This code is called shell code.

Why stack overflows work:

  • Stack fills variables down (high to low)
  • Strings fill up (low to high)
  • Return address at highest memory
  • Buffer overrun fills up to overwrite return address

Protections: Non-executable Memory

Basic buffer overflow exploits arise from the unintended execution of (read-only) data. One protection is to explicitly designate data as non executable (NX), however even with this protection there are ways to boostrap “gadgets” out of pieces of executable code to overcome this, including return-oriented programming and return-to-libc attacks.

Protections: Address Space Layout Randomization

Recall that our buffer overlflow attack was exploited by getting the program to jump to an address of the attacker’s choosing. Recall in the passcode challenge the attacker exploits that fact that they can write to any memory address, and they use this ability to overwrite the address of fflush in the Procedure Linkage Table. So when the program tries to call fflush, it actually ends up calling the cat flag system instruction instead. Uh oh!

But for this to work, the attacker needs to know the memory address to write to. Recall we found this by running:

(gdb) disas fflush
Dump of assembler code for function fflush@plt:
=> 0x08048430 <+0>:	jmp    *0x804a004
   0x08048436 <+6>:	push   $0x8
   0x0804843b <+11>:	jmp    0x8048410
End of assembler dump.

The attacker needs to place the address of the cat flag instruction into address 0x804a004. Similarly we can find the address of this system call:

(gdb) disas login
...
0x080485ea <+134>:	call   0x8048460 <system@plt>
...

So as you see the attack is highly dependent on the specific memory address. So if we could somehow make these addresses random, we could make such attacks much harder. Address Space Layout Randomization (ASLR) provides such protection against buffer overflows.

You can check if your system supports ASLR by typing:

cat /proc/sys/kernel/randomize_va_space

A value of 0 means ASLR is not present, whereas 1 and 2 are respectively support for “conservative” and “full” randomization. In order to exploit ASLR you must compile your program to as a “position independent executable” (PIE) using the following compiler flags:

gcc -pie -fPIE <yourprogram.c>

We can test this out on the username.c program from assignment 1:

gcc -pie -fPIE username.c -g
chmod +x a.out
gdb a.out

By default GDB turns off ASLR for debugging, however you can re-enable it as follows:

(gdb) set disable-randomization off

Now let’s set a breakpoint in the main() function. Run the program and disassemble the pin function and look for the <system@plt> call. We get something that looks like this:

0x8005d76e <+94>: 	call	0x8005d510 <system@plt>

But now let’s stop the debug and run it again. We get something different, e.g.:

0x8004976e <+94>: 	call	0x80049510 <system@plt>

And if we run it again:

0x800eb76e <+94>: 	call	0x800eb510 <system@plt>

This is a problem for the attacker. If the address of the system call in memory is randomly chosen at runtime, how can the attacker know where it will be to jump to it?

Assignment 3 Notes

In this assignment we put together all our knowledge into a semi-realistic Capture-the-flag scenario. You will be given a virtual machine (see OWL), and must capture the flag.

The Flag

There is only one flag in this assignment: obtain the root user’s password. There are two steps to this challenge:

  1. Execute a stack buffer overflow to run shellcode that will print the /etc/shadow file.
  2. Crack the root user’s password hash to obtain the flag (i.e., the root user’s password).

Background

Assignment 3 is based on the Protostar/Stack 5 Capture the Flag challenge. This challenge brings to bear a great many concepts, and therefore you must prepare with some additional background preparation involving gdb, the stack, assembly code, program execution, and program memory.

The goal will be to create a stack buffer overflow of the following program in order to run your malicious payload:

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv)
{
  char buffer[64];

  gets(buffer);
}

The website liveoverlfow.com offers several excellent videos walking you through these ideas:

  1. Start by watching video 0x0C, which is a walk through solution to the Stack 0 challenge. This will introduce you to the stack and its layout in the context of a CTF about using a buffer overflow to modify a variable.

  2. Next watch video 0x0D to gain additional insight into buffer overflow attacks in the context of the Stack 3 challenge, which demonstrates how a buffer overflow can be used to redirect program execution.

  3. Finally watch video 0x0E, which is a walk through of the Stack 5 challenge. Assignment 3 is based off this CTF, which demonstrates the attacker’s ability to use a stack buffer overflow to inject and execute shellcode. You may find you need to watch this video numerous times!

Phases of the stack buffer overflow exploit

There is an executable file smashme in the user’s home directory. Your job is to run this program and provide it with input to achieve two goals: (1) put a malicious program onto the stack (shellcode), and (2) use a stack buffer overflow to hijack the program’s execution flow, and get it to run this shellcode to gain access to the system’s shadow file.

This exploit involves several steps, which you should seek to understand and master before moving on to the next one. Anyone can get the finished exploit and run it. Your job is to understand something about why it works.

Here are the high-level phases of the buffer overflow exploit:

  1. Determine in gdb how many characters of input are needed before you can take control of the return address
  2. Determine in gdb the appropriate address on the stack to send the program execution to
  3. In gdb, demonstrate trivial code execution in the stack by getting the sigint interrupt to run
  4. Implement a Nop slide to overcome the address difference between running it in gdb, and running in the command line
  5. Add in your shellcode, run from the command line to print the /etc/shadow file.

Password Cracking

Once you have the shadow file, you can use your favorite password cracking utility to recover the root user’s password!

Hint: The root user chose a password in this list of the top 1000 most common passwords.

You may use whatever shellcode you wish to obtain the shadow file, and the website shell-storm.org provides numerous specimens. However, we recommend the following shellcode which executes /bin/cat /etc/shadow.

For convenience you can copy it in hex form here:

\x31\xc0\x50\x68\x2f\x63\x61\x74\x68\x2f\x62\x69\x6e\x89\xe3\x50\x68\x61\x64\x6f\x77\x68\x2f\x2f\x73\x68\x68\x2f\x65\x74\x63\x89\xe1\x50\x51\x53\x89\xe1\xb0\x0b\xcd\x80

Tips and differences from Stack 5

As is pointed out in the 0x0E video starting at 6:38, if you copy and recompile the program, crucial addresses in the stack may be different due to different environment variables.

For example, if you analyze the program in gdb using virtual box’s terminal window, you will find you get different stack addresses than if you log into the VM over ssh, because the two different sessions will have different environment variables, which will make the stack bottom start at different addresses.

My recommendation, therefore, is you only interact with the VM over ssh, that way you can have multiple sessions open simultaneously, with environment variables of similar length.

Also, when the author implements the Nop slide starting at 8:18, he uses a 30 byte offset, and 100 byte Nop slide. If you keep getting an illegal instruction error, you may want to try increasing these values.

How to complete the assignment

  1. Download the Assignment 3 VM in OWL under Resources->ECE9609-Assignment-3.ova
  2. Complete the assignment steps to recover the root user’s password
  3. Give your solutions in OWL under Tests/Quzzes -> Assignment 3