The challenge starts with the following text:

Play the classic game Memory. Feel free to download and study the source code.

you can either press a link to play the game online or download a zip file containing the game source code (in go).

We first tried playing the game a few time to understand the challege. It is a simple memory game with a 7*8 grid of cards. Each card is a number and it appears like you have to solve the game. The catch is that you only have 60 cards to pickup and 10 seconds for each card.
If the shuffeling of the cards is done right – this game should be impossible to solve by. So we turn to the source code.

We have 3 source files – main.go, game.go and random.go – Main contains the HTTP server logic, game contains the game logic and random is a custom implementation of a psudo-random number generator. Looking at the random.go we can describe the randomness generation as follows:

1. The function OsRand – Generates an 8 byte random from the OS BUT multiplies it by 14496946463017271296 (0xc92f800000000000) – a very large number, this is used as the seed.
2. The cards start out in an ordered manner [1, 1, 2, 2, 3, 3 … 28, 28] and are then shuffled using the following algorithm: for i := BoardSize – 1; i > 0; i– {
   j := rand.UInt64n(uint64(i) + 1)
   b.nums[i], b.nums[j] = b.nums[j], b.nums[i]
   }

Starting from the last card – each card is swapped with any of its predecessors. Choosing the card relied on the randomness. A new (weak) seed is created for each game. The Uint64n function uses the Uint64 function to give us a number in the range of 0..n | 8 bytes of cell id))

We looked at the two functions Uint64n and Uint64 – they seem just as bad as OsRand.

With all the problems in the random generation we decided to try and “read” a lot of boards from the server and perform a histogram on them, assuming we would detect collisions pretty quickly.

We wrote a small python script to talk to the server via websockets and started our test.
Indeed we saw that our assumption was true – we saw the first board twice after about 2000 tries.
At this point we tried to write some fancy code that put each board into a hash table by opening the first 4 cells and using it as key adding boards as we go. We are not exactly sure why but this code didn’t solve it so after an hour or so we decided to write something simpler. We went through all the boards we collected and found the one that appeared the most. We updated our script to solve the game using it as the correct solution – figuring that if the random is as broken as we saw – we should get that table and succeed on it.
This simple approach worked 🙂

Our solution:

import asyncio
import websockets
from threading import Thread
from json import dumps, loads, load
from time import sleep
from collections import defaultdict

boards = []
hist = defaultdict(int)
board_count = 0
duplicates = 0

board_dict = defaultdict(list)


my_board = [20, 11, 23, 22, 14, 4, 9, 17, 20, 23, 19, 16, 1, 27, 6, 3, 26, 3, 4, 2, 18, 5, 22, 18, 11, 16, 8, 13, 27, 9, 24, 12, 0, 24, 25, 21, 5, 7, 19, 2, 15, 15, 21, 25, 1, 17, 10, 12, 0, 13, 8, 6, 10, 26, 14, 7]

def get_pairs_from_board(board):
    pairs = []
    for i in range(len(board)//2): 
        p = [] 
        p.append(board.index(i))
        p.append(board.index(i, p[0]+1))
        pairs.append(p)
    return pairs


async def solve_by_board(ws, board):
    pairs_list = get_pairs_from_board(board)
    for pair in pairs_list:
        for i in pair:
            y = i // 7
            x = i % 7
            await ws.send(dumps({"op":"guess","body":{"x":x,"y":y}}))
            res = loads(await ws.recv())

    if res['message']:
        print('\n\n\nWOW !!!!!!!!!!\n\n\n', res['message'])

async def hello():
    global board_count
    global duplicates
    matched_pairs = []
    try:
        async with websockets.connect(
                'wss://doomed.web.ctfcompetition.com/ws', 
                ssl=True,
                extra_headers={
                    "Origin": "https://doomed.web.ctfcompetition.com",
                    "Host": "doomed.web.ctfcompetition.com"
                }) as ws:
            board = [-1] * 8 * 7
            await ws.send(dumps({"op":"info"}))
            await ws.recv() # board info
            reqs = 0


            return await solve_by_board(ws, my_board)
    except websockets.exceptions.ConnectionClosed as e:
        print("skipped error...", e)


while True:    
    for i in range(100):
        total += 100
        if (total % 1000 == 0):
            print('total: %d\r' % total, end='')
        future = asyncio.ensure_future(hello())
    asyncio.get_event_loop().run_until_complete(future)