# Writeup for Numbers, PPC Defcamp Quals 2019

## 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 subsets of size for a set with size . That means there are 92378 subsets that we can expect as vaild set of moves:

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!