Cyber Jawara International 2024 — Misc: Stone Game (100 pts)

Description

Welcome to the Stone Game. Take turns with the computer to pick stones from any set. Remove as many as you want, but the one who takes the last stone wins. Plan your moves carefully and try to outsmart the computer.

nc 68.183.177.211 10001

Solution

Given a netcat service. When we try to open the service, we find the following challenge:

jedi@aqua: /mnt/d/CTF/cj
$ nc 68.183.177.211 10001                                                                                    
Welcome to the Stone Game! Try to beat the computer.

Rules:
1. There are 7 sets of stones. Each set has a certain number of stones.
2. On your turn, pick any set and remove 1 or more stones from it.
3. You must take at least one stone, and you cannot take more than what is available.
4. The player who takes the last stone wins!


Stones:
+---+---+---+---+---+---+---+
| 3 | 4 | 5 | 2 | 6 | 3 | 5 |
+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7

Your turn! Choose a set of stones (1-7):

As you can see, this challenge falls into a type of game called a nim game. Each person will take a stone from a set, and the last person to take a stone will be the winner. The solution to solving the nim game is to do the xor calculation on each set. If the xor result is 0, then we are in a losing position. And if the xor result is not 0, then we are in a winning position. We must put the opponent in a losing position by subtracting one of the sets with the xor calculation result, so that the xor result of all sets is 0 when it is the opponent’s turn

However, when we look at the present condition, we find that 3 ⊕ 4 ⊕ 5 ⊕ 2 ⊕ 6 ⊕ 3 ⊕ 5 = 0

One solution to this problem is to not take a stone in the first round and let the computer take a stone. With this, we can be in a winning position.

Stones:
+---+---+---+---+---+---+---+
| 3 | 4 | 5 | 2 | 6 | 3 | 5 |
+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7

Your turn! Choose a set of stones (1-7): 1
1
How many stones to take from set 1? 0
0

Stones:
+---+---+---+---+---+---+---+
| 3 | 4 | 5 | 2 | 6 | 3 | 5 |
+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7
Computer takes 1 stone(s) from set 1

Stones:
+---+---+---+---+---+---+---+
| 2 | 4 | 5 | 2 | 6 | 3 | 5 |
+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7

Your turn! Choose a set of stones (1-7):

We find that we can indeed not take any stones in the first round, so we can play in a winning position. The solver that I made is as follows :

from pwn import *

host = "68.183.177.211"
port = 10001
p = remote(host, port, level='debug')

def parse_stone_sets(solve):
    lines = solve.splitlines()
    stone_line = next(line for line in lines if "|" in line)
    stones = [int(num.strip()) for num in stone_line.split("|")[1:-1]]
    return stones

def calculate_nim_sum(stones):
    nim_sum = 0
    for stone in stones:
        nim_sum ^= stone
    return nim_sum

def make_optimal_move(stones):
    nim_sum = calculate_nim_sum(stones)
    for i, stone in enumerate(stones):
        target = stone ^ nim_sum
        if target < stone:
            return i + 1, stone - target
    return 1, 1

solve = p.recvuntil(b"Your turn! Choose a set of stones")

p.sendline(b"1") 
p.sendline(b"0")
p.recvuntil(b"Computer takes")

while True:
    solve = p.recvuntil(b"Your turn! Choose a set of stones", timeout=5)
    if b"CJ{" in solve:
        print(solve.decode())
        break

    stones = parse_stone_sets(solve.decode())
    set_index, stones_to_take = make_optimal_move(stones)
    
    p.sendline(str(set_index).encode())  
    p.recvuntil(b"How many stones to take from set")
    p.sendline(str(stones_to_take).encode()) 

    solve = p.recvuntil(b"Computer takes", timeout=5)
    if b"CJ{" in solve:
        print(solve.decode())
        break

# Sorry for the broken solver, another skill issue detected :(

Flag

CJ{why_I_allowed_zero_:(}