Writeup for Numbers, PPC Defcamp Quals 2019

4 minute read

Task Description

numbers (Misc - 171 pcts.) Bonus points for first 3 solvers.

This game is pretty simple. You and my friend have to play a game. To win, you must get to 0 before my friend does by subtracting a certain value from the allowed moves. Btw, you don’t have too much time.

Target: 206.81.24.129:2337

Author: Andrei

Solution

By connection the server, we can figure out that we should solve a strategic game for 10 rounds. The server sends us an array, seems to have 10 members, all integers and all less than 20:

Hi! What's your name?
asis
Hi asis
This game is pretty simple. You and my friend have to play a game. To win, you must get to 0 before my friend does by substracting a certain value from the allowed moves. Btw, you don't have too much time
Ready? Y/N
Y
Round 0/10
Allowed moves:
[19, 5, 4, 15, 18, 1, 6, 2, 16, 9]
Total Score:  1000
Your move: 

Searching around the web for strategic games related to summation guide me through the nim-sum games. It took me a while to map the game to the given problem, altough after the game someone send a link which basically reprsents ths mapping. The idea then gets definitive, the code should at first find all the winning positions, and then selects a move that guarantees, the player wins. Obviously if we start the game first and trim the game always in the winning position, we can win at the end.

#!/usr/bin/env python
from pwn import *
import itertools
import sys
import subprocess

def positions(A):
    max_set = max(A)
    min_set = min(A)
    A.sort()
    winning_pos = []
    for i in range(min_set):
        winning_pos.append(i)
    for i in range(1000):
        flag = 0
        for move in A:
            if flag == 0 and (i - move) in winning_pos and i >= move:
                flag = 1
        if (flag == 0 ) and i not in winning_pos:
            winning_pos.append(i)
    return winning_pos

def next_move(A, winning_pos, score):
    for move in A:
        if (score - move) in winning_pos:
            return move
    print "no move"
    # nim.py is the name of this python script, it calls itself and exit
    subprocess.call("/usr/bin/python /home/rooney/nim.py",  shell = True)
    sys.exit(0)
    return A[0]

# def test():
#     A = [7, 9, 17, 8, 13, 12, 14, 19, 3, 10]
#     p_positions(A)

HOST = '206.81.24.129'   # The server's hostname or IP address
PORT = 2337
conn = remote(HOST, PORT)
data = conn.recvuntil("Hi! What's your name?")
#data = conn.recv()
print data
conn.sendline('asis')
data = conn.recvuntil("Ready? Y/N")
conn.sendline('Y')
eof_flag = 0
while True:
    if eof_flag:
        print "finished game"
        print conn.recvall()
        sys.exit(0)
        #data = conn.recvrepeat(timeout = default)
        #print data
    data = conn.recvuntil("Total Score:")
    if data.find("Allowed") == -1:
        data = conn.recvuntil("Total Score:")
    if data.find("Round 9/10") !=-1:
        eof_flag = 1
    data = data.strip().split('\n')
    print data
    A = eval(data[-2])
    print "Rooney talks"
    print A
    winning_pos = positions(A)
    score = 1000
    m = min(A)
    while True:
        data = conn.recvuntil("Your move: ")
        score = int(data.split("\n")[-2].split(": ")[-1])
        print data
        step = next_move(A, winning_pos, score)
        print step
        conn.sendline(str(step))
        if (score - step) < m:
            break
        #print next_move(A,winning_pos, score)

And after 11 minutes, I got the flag:

Well done this round! 🙂
('FLAG', 'DCTF{D46CA831D4DA67C22034865B917F6ACCA45158D2C0B6622E79C532DFDB161080}')

Discussion

The cahllange was quite simple and at least 20 teams solved it (excluding us, we didn’t send the flag), but it has some aspectes I would like to mention as post-ctf-discussion.

As I have added in the code, the pair 1000 and a 10-member-array is not enough to win the game, there are positions which will result in loosing despite the fact that we start the game and always select a move that leads us to winning positions. And I saw lots of these positons at the first and in the middle of games, menaing that organizers didn’t want to prune them. In the code when the no move situations happens, I terminate the run and call the python program for a fresh run (probably could code it better using threads!).

Here are some statistics I have which shows the number of sample arrays which is not possible to select a winning move with them at first.

In general, there are {n \choose k} subsets of size k for a set with size n. That means there are 92378 subsets that we can expect as vaild set of moves:

{19 \choose 10} = \dfrac{19!}{10! 9!} = 92378

Given this number, I build all the valid sets and calculated the portion of sets which are doomed to be killed in my program.

#!/usr/bin/env python
from pwn import *
import itertools
import sys
import subprocess

def positions(A):
    max_set = max(A)
    min_set = min(A)
    A.sort()
    winning_pos = []
    for i in range(min_set):
        winning_pos.append(i)
    for i in range(1000):
        flag = 0
        for move in A:
            if flag == 0 and (i - move) in winning_pos and i >= move:
                flag = 1
        if (flag == 0 ) and i not in winning_pos:
            winning_pos.append(i)
    return winning_pos

def next_move(A, winning_pos, score):
    for move in A:
        if (score - move) in winning_pos:
            return move
    #print "no move"
    return -1

def findsubsets(A, k): 
    return list(itertools.combinations(A, k))



def main():
    all_failures = 0
    superset= [i for i in range(1,20)]
    subsets = findsubsets(superset,10)
    i = 0
    for A in subsets:
        A = list(A)
        i+=1
        #print(i, len(subsets))
        winning_pos = positions(A)
        data = next_move (A, winning_pos, 1000)
        if data == -1: 
            all_failures +=1
    print ("******************************")
    print (len(subsets) , all_failures)

if __name__ == "__main__":
    main()

The result is 92378, 20236. Which means that player start the round at a loosing position in almost 1/5 times. We know that the game is 10 rounds, therefore my solution wins with 10% chance ((4/5)^10) for each run.

I was wondering if this one is intended or we should have a machine that prunes the undesired subsets. Anyway I enjoyed this challenge very much!