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 functionm, 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 mov [rsp], rdi; sub rsp, 8.

Note that this makes talking about the stack without confusion borderline impossible. For example, people with a math background tend to thing 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!

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.

In this challenge, run /challenge/program to see what address it wants argv[0] at. Then add a single environment variable, with just the right number of xs in its value, to shift argv[0] to that address:

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

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!