From time to time I solve levels of Smash the Stack for fun.
Here's how it works. On each level there's a program with a security vulnerability and the source code for said program. You SSH into their server with the level's given username and password. Your job is to exploit the vulnerability in a way that gives you the content of the next level's password file. The vulnerability exposed on level 5 is a buffer overflow.
A buffer overflow can be exploited to insert content of the attacker's choice into the target program's memory. This can manifest itself in a number of ways. I'll be using it to inject a new program into the target process and get the process to run it. The end result is that the target process will execute the code of my choice.
To demonstrate how this works, I'll be using a simplified computer to model what's happening in the memory of the target program.
The rectangle below is a block of memory. Each cell has an address with the number on the left being the address of the leftmost cell in that row. In the memory below, P is loaded into cell 0 and _ is loaded into cell 3. This computer always starts by executing the instruction located in cell 0 and then proceeding to the next instruction. When the computer hits an empty space or an invalid instruction, it resets itself.
The first instruction is P. This instruction prints the contents of the following cell to the computer's output. Go ahead and step through this program to see how it works.
0
P
Y
P
_
4
P
H
P
E
8
P
L
P
O
12
P
_
P
T
16
P
H
P
A
20
P
R
24
28
32
36
40
output
Px
Print x
So that's cool, but a computer that doesn't interact with the outside world is of pretty limited utility. To rectify that, I'll introduce the R instruction. This allows the computer to read data into memory that wasn't there when it started. In order to do that, it needs a place to store the information. That place is called a buffer. A buffer is just a chunk of memory. For this program, the buffer starts at address 36. Notice that I don't specify an end address. My computer doesn't know how long buffers are. When a piece of data is read, it is stored at the next address in the buffer.
0
R
R
R
R
4
8
12
16
20
24
28
32
36
40
inputYEOP
output
R
Read a letter or number into the buffer
Px
Print x
The next program adds confirmation messages to the previous one. Now, rather than silently reading a bunch of data, it will print OK after each successful read.
0
R
P
O
P
4
K
R
P
O
8
P
K
R
P
12
O
P
K
R
16
P
O
P
K
20
24
28
32
36
40
inputYEOP
output
R
Read a letter or number into the buffer
Px
Print x
That implementation is crying out for a subroutine. I clearly want a single piece of code that I can call out to when I want to read a piece of data and print a confirmation. What I want is the G instruction. G causes the computer to go to the given address and start executing the code there.
0
R
G
16
R
4
G
16
R
G
8
16
R
G
16
12
16
P
O
P
K
20
24
28
32
36
40
inputYEOP
output
Gx
Goto x
R
Read a letter or number into the buffer
Px
Print x
As you have no doubt noticed, G is not sufficient to make a subroutine. I don't have a way to get back to the main routine! S and F will solve that. S saves the address of the next non-goto instruction and F will fetch that address and jump back to it. The computer arbitrarily stores the saved address at address 40.
0
R
S
G
20
4
R
S
G
20
8
R
S
G
20
12
R
S
G
20
16
20
P
O
P
K
24
F
28
32
36
40
inputYEOP
output
S
Save the address after the next instruction
F
Fetch the address of the next instruction
Gx
Goto x
R
Read a letter or number into the buffer
Px
Print x
The last thing the computer needs is a way to conditionally execute code. Z will fill that role. If the last input is a 0, Z jumps to the given address. Otherwise it's skipped.
0
S
G
12
G
4
0
8
12
R
Z
20
F
16
20
P
O
P
K
24
28
32
36
40
inputYEOP0
output
Zx
Go to x if the last input was a zero
S
Save the address after the next instruction
F
Fetch the address of the next instruction
Gx
Goto x
R
Read a letter or number into the buffer
Px
Print x
Now the computer is powerful enough to demonstrate the overflow in buffer overflow. Recall that a buffer is just a chunk of memory. A buffer overflow is when too much data is written into a buffer. In this example, I've allocated 8 cells of memory for my buffer. So what happens when I read in the 9
th
piece of data?
0
S
G
12
G
4
0
8
12
R
Z
20
F
16
20
P
O
P
K
24
28
32
36
40
inputY_HELO_THAR
output
Zx
Go to x if the last input was a zero
S
Save the address after the next instruction
F
Fetch the address of the next instruction
Gx
Goto x
R
Read a letter or number into the buffer
Px
Print x
What happens is that the memory after the buffer gets corrupted. When the computer writes past the end of the buffer, it writes on top of the data saved by the last S instruction. In the previous program, I overwrite it with an H. When the subsequent F tries to load the saved value, it gets the H instead and crashes because H is an invalid address.
To exploit this flaw, I purposefully overwrite the saved S address with the address where the buffer starts. Because the computer doesn't distinguish between data and instructions, the next F blindly loads the value I've chosen and jumps to our input for its next instruction rather than where the original programmer intended.
0
S
G
12
G
4
0
8
12
R
Z
20
F
16
20
P
O
P
K
24
28
32
36
40
inputPLPOG32__32__
output
Zx
Go to x if the last input was a zero
S
Save the address after the next instruction
F
Fetch the address of the next instruction
Gx
Goto x
R
Read a letter or number into the buffer
Px
Print x
This is the buffer overflow attack. The attacker sends the program more information than it's prepared for. In doing so, the program's memory gets corrupted with data of the attacker's choosing. In this case I use it to execute the instructions of my choice. It could equally be used to change any of the program's memory.
