The Stack, Revisited

In addition to storing scratch data and return addresses, the stack stores the local variables of functions: data they use for functionality that's not necessarily needed by other functions of a program. In security situations where a hacker gets ``code execution'' inside a process, these variables are an open book: there is nothing preventing code in a process from reading data from all over the stack!

This challenge explores this concept. Once again, you write a solve function that the challenge calls, but the challenge passes you no arguments. Instead, the challenge's caller function has stored the flag in its own local variables before calling you. You have to reach over into the caller's "frame" (what we call the part of the stack including a function's local variables and the saved return address to which it will return) and grab those bytes.

Wait, what?
Let's walk through why this is possible. In this challenge, the main function calls the caller function, which then calls your solve function. Right before the challenge's caller function executed call solve, the stack looked like this:

                                          [smaller addresses]
   +───────────────────────────────────+  ◀── rsp, immediately before `call solve`
   │ caller's local region             │
   │ ... your flag is in here ...      │
   +───────────────────────────────────+
   │ caller's saved rbp                │
   +───────────────────────────────────+
   │ return address (back to main)     │
   +───────────────────────────────────+
   │ ... main's frame ...              │
   +───────────────────────────────────+
                                          [larger addresses]

The call solve instruction does two things:

1. Pushes the return address onto the stack (8 bytes). Pushing decrements rsp, so the return address ends up at a smaller address than what was already on the stack.
2. Jumps to your code.

That first step is critical: the stack grows backwards from what you might expect. pop actually adds 8 to rsp, and push subtracts 8. This is counter-intuitive and is a concept that often confuses learners. If you think of the stack as a page that is 8 bytes wide, you would start writing in this page at the very bottom, and move one line upwards on the page every time you push. In other words, say, pop rdi is equivalent to mov rdi, [rsp]; add rsp, 8 and push rdi is equivalent to sub rsp, 8; mov [rsp], rdi.

Note that this makes talking about the stack without confusion borderline impossible. For example, people with a math background tend to think of a coordinate of 0 as being on the bottom or the left of a page, whereas people with a video game or web development background tend to think of 0 as being on the top or the left. This leads to massive confusion about the definition of "higher address", "lower address", and so on. Everyone has different ways of dealing with this. In this document, because horizontal space is at a premium, we put diagrams from 0 (top) to 0xffffffff (bottom), but in everyday life when not restricted by horizontal space, we simply conceptualize memory from the "left" (0) to the "right" (0xffffffff).

Anyways, at the moment your solve starts running, the stack looks like this:

                                          [smaller addresses, where rsp goes if you grow your own frame]
   +───────────────────────────────────+
   │ return address (back to caller)   │  ◀── rsp points here
   +───────────────────────────────────+
   │ caller's stack frame              │
   │ ... your flag is in here ...      │
   +───────────────────────────────────+
   │ return address (back to main)     │
   +───────────────────────────────────+
   │ ... main's frame ...              │
   +───────────────────────────────────+
                                          [larger addresses]

The caller's locals sit at larger addresses than your rsp --- below your rsp in the diagram. The data you want is somewhere in that region. To find it, you index into memory with a positive offset from rsp.

If you go the other way --- negative offsets, at addresses smaller than rsp (above rsp in the diagram) --- you'll find unallocated stack space. There's nothing useful for you up there (yet!).

When your solve starts running, the layout looks like this:

   [rsp + 0x00]   your return address (back into caller's code)
   [rsp + 0x08]   first byte of caller's local region
   ...
   [rsp + 0x40]   the flag (copied here by the caller)
   ...
   [rsp + 0x110]  caller's return address (back to main)

Your job: reach into the caller's frame, grab the flag at [rsp + 0x40], and write it to stdout (you already know how to issue a write syscall!). Get it right, and your solve will print the flag for you!

In the last level, you reached rightward into your caller's frame. Now you'll look leftward, at bytes left behind by a function that already returned.

When your code calls a function, that callee can move rsp left and use stack memory of its own. When it returns, it moves rsp back right, but the bytes it wrote are not automatically erased. They become stale stack data: ordinary memory left behind by code that already finished. Software could erase those bytes before returning, but erasing data means running more instructions and writing more memory. When the leftover data is sensitive, skipping that erasure can become a vulnerability. This level starts with the smallest version of that issue: one stale 8-byte value.

This challenge passes your solve a function pointer named load_secret. Call it first. It stores one 8-byte secret in its own stack frame and returns, leaving those bytes at a negative offset from your current rsp. The checker will tell you the exact offset.

Because the goal is to return the 8-byte value itself, load it with mov:

mov rax, qword ptr [rsp-0x40]

That example offset is hypothetical; use the offset printed by the checker. Write a function called solve that calls load_secret, loads the stale 8-byte value into rax, and returns.

Build it into a shared library and hand it to the grader:

hacker@dojo:~$ as -o solve.o solve.s
hacker@dojo:~$ ld -shared -o solve.so solve.o
hacker@dojo:~$ /challenge/check solve.so

For debugging a submitted function inside a shared library, refer back to Writing From a Shared Library.

In the last level, you loaded one stale 8-byte value from an old callee frame. Now you'll use the same stale-stack idea on a byte buffer.

This challenge passes your solve a pointer to a function named read_flag. Call that function first. It puts the flag in its own stack frame and returns. After it returns, that old frame is to the left of your current rsp, and the flag bytes are still there until something overwrites them!

Write a function called solve that calls the function pointer in rdi, then writes the stale flag bytes from the old callee frame to stdout. From solve's perspective, those stale bytes sit at a negative offset from rsp; find the exact offset in gdb or read it from the checker output. The important distinction is value versus address. If you wanted to load one 8-byte value from that old frame, you would use mov:

mov rax, qword ptr [rsp-0x40]

But write needs the address of the first byte in rsi, not the qword stored there as a value. For that, compute the address with lea:

lea rsi, [rsp-0x40]

That example offset is hypothetical; use the offset printed by the checker. Build it into a shared library and hand it to the grader:

hacker@dojo:~$ as -o solve.o solve.s
hacker@dojo:~$ ld -shared -o solve.so solve.o
hacker@dojo:~$ /challenge/check solve.so

For debugging a submitted function inside a shared library, refer back to Writing From a Shared Library.

In the last levels, you reached rightward into the caller's frame and leftward into stale data from an old callee. Now you'll carve out a frame of your own.

So far, your functions have kept their temporary values in registers. But a function can need more scratch space than registers can hold. On 64-bit x86, a function makes stack scratch space by modifying the stack pointer (rsp) to point to a lower address: sub rsp, 256 reserves 256 bytes to the right of the new stack pointer. Those bytes are then addressable as [rsp] through [rsp+255]. The stuff already on the stack is of course still there, but because rsp moved left, it now needs different offsets from rsp.

This does not give you freshly-zeroed bytes. The bytes you just moved rsp across are ordinary stack memory, and they may contain bytes left behind by earlier code. If you use those bytes as a table or a set of counters, stale values look exactly like values your function wrote. In fact, failure to initialize stack data, and the subsequent use of resulting garbage by the program, is a common source of vulnerabilities in software! That is why a stack frame that will hold scratch data normally starts with initialization: reserve the space, write known values into it, use it, then put rsp back before returning.

Initialization happens between allocation and deallocation of the stack frame:

sub rsp, 256       # allocate a 256-byte frame
    ...            # initialize and use [rsp] through [rsp+255]
add rsp, 256       # deallocate the frame
ret

That last step matters as much as the first. ret pops its return address from [rsp], so if rsp is not back where it started, ret will read the wrong bytes as an address and your program will crash.

Write a function called solve that reserves a 256-byte stack frame, clears every byte in it to zero, restores rsp, and returns. The grader fills the would-be frame with nonzero bytes before calling your function, then checks that all 256 bytes were cleared after your function returns. You may find mov byte ptr [rsp+rcx], 0 useful for clearing one byte at offset rcx.

Build it into a shared library and hand it to the grader:

hacker@dojo:~$ as -o solve.o solve.s
hacker@dojo:~$ ld -shared -o solve.so solve.o
hacker@dojo:~$ /challenge/check solve.so

For debugging a submitted function inside a shared library, refer back to Writing From a Shared Library.

In the last level, you reserved a stack frame, cleared it, restored rsp, and returned safely. Now you'll put that frame to work.

Count how many distinct byte values appear in a buffer. The natural way is to keep a table with one slot per possible byte value: 256 slots, indexed by the byte value itself. Start with the same 256-byte stack frame you built before and clear it to zero. Then, when you see byte value b, write 1 into slot b. After you have scanned the buffer, count how many table slots are marked.

Write a function called solve that takes a pointer to a buffer in rdi and a length in rsi, and returns, in rax, the number of distinct byte values among those rsi bytes. You might find the instruction mov byte ptr [rsp+rcx], 1 useful for marking a given value (stored in rcx) as "present" in your scratch table (based at rsp).

Build it into a shared library and hand it to the grader:

hacker@dojo:~$ as -o solve.o solve.s
hacker@dojo:~$ ld -shared -o solve.so solve.o
hacker@dojo:~$ /challenge/check solve.so

HINT: You'll need three loops in this level, one after the other: one to clear the scratch table, one to mark each value you see, and one to count the marked slots afterwards.

For debugging a submitted function inside a shared library, refer back to Writing From a Shared Library.

The stack stores more than just argc and argv! Right after the argument list, the kernel places the environment variables you learned about in the Linux Luminarium. Just like argv, these are stored on the stack as an array of pointers to strings, where each string includes both the name and value of the variable, as so: PATH=/usr/bin:..., HOME=/home/hacker, or PWN=COLLEGE.

If a program is called with no arguments (e.g., argc is 1 and the only string in argv is the name of the program itself) and a single environment variable named FLAG, its starting stack layout might look like this:

     Address    │ Contents
   +────────────────────────+
   │ rsp + 0    │ 1         │ ◀─── argc
   +────────────────────────+
   │ rsp + 8    │ rsp + 128 │──┐  argv[0]: pointer to the program name
   +────────────────────────+  │
   │ rsp + 16   │ 0         │  │  NULL (end of argv)
   +────────────────────────+  │
   │ rsp + 24   │ rsp + 200 │──┼──┐  envp[0]: pointer to the first env var
   +────────────────────────+  │  │
   │ rsp + 32   │ 0         │  │  │  NULL (end of envp)
   +────────────────────────+  │  │
                               │  │
     Address    │ Contents     │  │
   +────────────────────────+  │  │
   │ rsp + 128  │ "/tmp/..."│◀─┘  │  the program name
   +────────────────────────+     │
   │ ...        │ ...       │     │
   +────────────────────────+     │
   │ rsp + 200  │ "FLAG=..."│◀────┘  the first env var: the `FLAG` variable
   +────────────────────────+

Two new things to notice:

1. Both argv and envp are NULL-pointer-terminated: the kernel writes a NULL pointer at the end of each list of pointers. That's how programs (and you!) know where each list ends --- walk the pointers until you hit a NULL. In the diagram, you can see the NULL at rsp+16 marking the end of argv, and another at rsp+32 marking the end of envp.

2. The envp strings look like NAME=VALUE (e.g., PATH=/usr/bin:/bin). So envp[0] points to a string that starts with the first env var's name.

In this challenge, we will set the FLAG environment variable to the actual flag and run your program with no arguments and no other env vars. That means [rsp+24] will hold a pointer to the FLAG=... string, and you can get the flag by write()ing it out!

In the previous level, you read envp[0] --- a pointer that the kernel placed on the stack, pointing into the strings region above the pointer tables. The same layout applies here:

     Address    │ Contents
   +────────────────────────+
   │ rsp + 0    │ 1         │ ◀─── argc
   +────────────────────────+
   │ rsp + 8    │ rsp + 128 │───────┐  argv[0]: pointer to the program name
   +────────────────────────+       │
   │ rsp + 16   │ 0         │       │  NULL (end of argv)
   +────────────────────────+       │
   │ rsp + 24   │ rsp + 200 │─────┐ │  envp[0]: pointer to the first env var
   +────────────────────────+     │ │
   │ rsp + 32   │ 0         │     │ │  NULL (end of envp)
   +────────────────────────+     │ │
                                  │ │
  ┌───────────────────────────────│─┘
  │                               │
  │   Address   │ Contents        │
  │ +──────────────────────────+  │
  │ │ rsp + 128 │ "/tmp/..."   │◀─┘ the program name
  │ +──────────────────────────+
  │ │ ...       │ ...          │
  │ +──────────────────────────+
  └▸│ rsp + 200 │ "FOO=..."    │ ◀─ the first env var
    +──────────────────────────+

But where do the actual addresses (rsp, or the actual address that rsp+200 resolves to, etc.) come from?

When your program is launched, the kernel fills the stack backwards from some chosen starting address. From there, it lays down the env strings ("growing" toward smaller addresses), then the arg strings, other metadata, then the envp[] and argv[] pointer tables, and finally argc on the leftmost side of the structure. That's where rsp ends up pointing.

This has an interesting consequence: the more bytes you stuff into the environment (or the program arguments), the further "left" the stack the kernel pushes everything else. An extra env byte means rsp ends up at a smaller address, the arg-strings region sits one byte further "left", and argv[0] (a pointer into that region) holds a one-byte-smaller value.

Here, env -i means "run the following command with an empty environment"; any NAME=VALUE pairs you put after -i are the only environment strings the child program receives. In this challenge, take a clean baseline with env -i /challenge/program to see what address it wants argv[0] at. Then run it again with exactly one environment variable, with just the right number of xs in its value, to shift argv[0] to that address. Use env -i for both runs so your shell's own variables do not also land on the stack and throw off your count:

hacker@dojo:~$ env -i /challenge/program
hacker@dojo:~$ env -i FOO=xxxxxxxx /challenge/program

Remember that the whole environment string is placed on the stack, so FOO=, the value, and the trailing null byte count toward the shift. You're not modifying the program at all, just changing how it's launched, which influences where its data ends up!

A common stack-related snafu is the shift in stack addresses that happens when launching a program under gdb. By default, gdb passes its own environment (your shell's env, plus a few of gdb's own additions) to the debugged program, and these extra environment variables shift the stack to the left, so argv[0] ends up at a different address than it does when you run the program straight from your shell. This isn't so important right now, but it becomes a big bother later on when you're trying to figure out why your bit-precise exploit code works in gdb but not on a target running normally. In those cases, learning to "synchronize" the two environments is important.

This challenge will teach you the basics: making the addresses outside of gdb line up better with the addresses inside gdb.

1. Run /challenge/program under gdb (gdb /challenge/program, then run). The program records its own argv[0] as your target.
2. Quit gdb. Run /challenge/program from your shell --- it'll tell you how far off your shell-context argv[0] is from the target.
3. Use an environment variable to "pad" your shell environment until argv[0] lands at the gdb-captured target.
4. Flag!

The challenge in the previous level inherited your interactive shell's environment both in and outside of gdb. In reality, the differences in environment are often more significant between your local setup and the target you're analyzing. The binary you're debugging from your shell and the same binary running as a service, a cron job, or a remote script would see completely different environments (different HOME, different PATH, a different set of variables entirely).

This level explores this concept a bit more. In this level, the gdb wrapper sets its own environment rather than inheriting it from your shell, and the challenge, when run directly forces you to do the same, requiring an environment with only a single variable. For example:

hacker@dojo:~$ /challenge/program
You're running me with 8 environment variables, but I need exactly 1! Clear the environment and set one variable, then rerun me!
hacker@dojo:~$ /challenge/program

How do you clear the environment? You can do so with the env command, which we've used before to print out all exported environment variables in the Linux Luminarium. The env command can also be used as a wrapper to carefully control the environment of a program. For example, you can clear the child program's environment completely using env -i:

hacker@dojo:~$ env -i /challenge/program
You're running me with 0 environment variables, but I need exactly 1! Clear the environment and set one variable, then rerun me!
hacker@dojo:~$ /challenge/program

You can also set variables after clearing the environment:

hacker@dojo:~$ env -i PWN=COLLEGE HACK=PLANET /challenge/program
You're running me with 2 environment variables, but I need exactly 1! Clear the environment and set one variable, then rerun me!
hacker@dojo:~$ /challenge/program

This allows you to have very finegrained control over your environment. In this challenge, you'll use this finegrained control to line up addresses in a slightly more realistic setting, but keep the capability in mind for other situations!