# Doomed to Repeat It
We have a classic game of memory, where you can only see one tile at a time. Once you unveil two identical tiles in succession, they stay face up.
The goal is to find all pairs.
![gameplay](https://i.imgur.com/2hGmv4K.gif)
The caveat : there are 56 tiles and you can only use 60 moves. Gotta be lucky.
## The source code
We have the source code, so let's dive into that.
There are a lot of red herrings in comments, but the biggest red flag should bethe custom RNG. after examination, turns out there is a problem with the implementation.
### Bad RNG
This function is used to get random bits from the os in order to generate a seed.```// OsRand gets some randomness from the OS.func OsRand() (uint64, error) {	// 64 ought to be enough for anybody	var res uint64	if err := binary.Read(rand.Reader, binary.LittleEndian, &res;; err != nil {		return 0, fmt.Errorf("couldn't read random uint64: %v", err)	}	// Mix in some of our own pre-generated randomness in case the OS runs low.	// See Mining Your Ps and Qs for details.	res *= 14496946463017271296	return res, nil}```It gets a 64bit uint from the os, and then multiply it with some "pregenerated randomness"
the pre-generated randomnessis quite problematic. It is not random at all.
![xkcd](https://i.imgur.com/uvslFTg.png)
(https://xkcd.com/221/) 
 * `14496946463017271296`'s prime factorisation is `2^47 * 103007`. 
*They are multiplying the os's randomness with 2^47!*
* Doing modulo multiplication on your randomness is bad.* Doing it with a very large power of two completely breaks it.
#### An example
Let's look at one multiplication to see why this is such a problem : 
random number multiplied by 2^47:```    8979835648265197673    111110010011110110010001111000111100100001111001001100001101001 *     140737488355328                   100000000000000000000000000000000000000000000000 ----------------------------------------------------------------------------------------   5491154583159832576    100110000110100100000000000000000000000000000000000000000000000```
As we can see, this completely eliminates the 47 least significant bits of the randomly generated number.
Instead of having `2^64` possible seed, we now have `2^17` possible seeds (and thus `2^17` possible layouts!)  thats 131072, and that's totally manageable.
#### Test the theory This is pretty easy to test : if we patch the OsRand function and replace the "pregenerated randomness" with an even bigger power of two : 
```func OsRand() (uint64, error) {	// 64 ought to be enough for anybody	var res uint64	if err := binary.Read(rand.Reader, binary.LittleEndian, &res;; err != nil {		return 0, fmt.Errorf("couldn't read random uint64: %v", err)	}	// Mix in some of our own pre-generated randomness in case the OS runs low.	// See Mining Your Ps and Qs for details.	res *= 1 << 63 // multiplying by 2^63 should squash 63 of the random number's 64 bits	return res, nil}```With this modification, the game only ever generate one of two possible layouts. 
We're on to something!
## Boards enumeration
We already have code that takes care of taking a seed and generating a board layout out of it.Let's keep it simple, and re-use that.  We patch the app's source code to have it dump every possible layouts.
A small modification to `newBoard()` and the random's library `New()` function  should do it.
This will generate all possible numbers between that have their 47 least significantbits set to zero, and use each of them as a source of entropy for the seed to generate oneboard.
```func newBoard() (*board, error) {
        var b *board        var i uint64        var upper uint64        upper = 1<<17   // 2 ^ 64        for i= 1; i< upper; i++ {   // add a loop over all board            var s uint64            s = i << 47  // generate false_seed
            rand, err := random.New(s)   //send that false_seed in the                                         // RNG to be used as the 'os random bits'
            if err != nil {                    return nil, fmt.Errorf("couldn't create random: %v", err)            }            b = &board{                    nums:    make([]int, BoardSize),                    visible: make([]bool, BoardSize),            }            for i, _ := range b.nums {                    b.nums[i] = i / 2            }            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]            }
            // and we add a print statement to dump the board do stdout            log.Printf("[%d] %v",s, b)  // print the board!
        }	return b, nil}```
We modify the New function so that it uses our specially crafted uint64 instead of the OSrand function
```func New(proto_seed uint64 ) (*Rand, error) {	// osr, err := OsRand()	// if err != nil {	// 	return nil, fmt.Errorf("couldn't get OS randomness: %v", err)	// }	// return NewFromRawSeed(osr)	return NewFromRawSeed(proto_seed)}```
With these modifications in place, running a game will print 2^17 boards to stdout. with a little bit of parsing, we can get them in a nice format :
```24 3 24 18 27 26 17 9 23 7 6 0 2 11 14 8 20 5 16 19 18 5 20 19 22 21 1 10 13 8 13 0 9 2 27 14 23 12 15 16 25 12 17 7 21 22 6 15 25 1 11 4 3 26 10 426 20 24 9 0 18 27 15 0 24 21 1 6 27 4 5 25 20 12 3 17 7 7 22 4 2 11 11 17 23 14 8 13 10 8 19 9 14 15 10 2 18 6 21 23 19 1 16 3 26 13 12 22 16 5 25```
A little python script will load them all in an dictionnary, with the first 4 tiles as key : ```
BOARD_FILE = 'boards.txt'
from collections import defaultdict
boards = defaultdict(list)def init():    with open(BOARD_FILE) as f:        for line in f:            permutation = line.strip().split(" ")            board = [int(item) for item in permutation]            board_key = tuple(board[:4])            boards[board_key].append(board)
def get_all(key):    return boards[key]```
This gives us a simple API to query the list of boards. for instance, this will get us allboards that have the following tiles starting top left corner `2,43,21,23````boards.init()boards.get_all( (2,43,21,23) )``` 
## Interracting with the game server
The game front-end interract with the game server via websockets. This was done withthe python websockets library 
some important points to note : 
    1. The websocket library used needs to understand the websocket handshake, as we       don't want to implement the http-> websocket upgrade handshake    2. The hostname needs to be specified or else the handshake won't be valid, and the server       will reject the query
### Connect to the game serverThis piece of (asyncio) code will connect:```     async with websockets.client.connect(            URI,            origin='https://doomed.web.ctfcompetition.com') as ws:        pass```
### Play a gameThese co-routines can be used to initiate the game state and send some guesses
```async def get_info(ws):
    qry = {"op":"info"}    await ws.send(json.dumps(qry))    response = await ws.recv()    return json.loads(response)
async def send_guess(x,y, ws):
    qry = {"op":"guess",           "body":{"x":x,                   "y":y}}    await ws.send(json.dumps(qry))    response = await ws.recv()    return json.loads(response)
```
At this point, it's just a matter of trying the first four tiles, infering the correct game board, and then solve a game where we know the position of all tiles!
![Imgur](https://i.imgur.com/LjXJItZ.gif)
Full python code : 
```
#!/usr/bin/env python3
import websocketsimport asyncio import json
URI = 'wss://doomed.web.ctfcompetition.com/ws'
import boardsboards.init()
async def send_guess(x,y, ws):
    qry = {"op":"guess",           "body":{"x":x,                   "y":y}}    await ws.send(json.dumps(qry))    response = await ws.recv()    return json.loads(response)
async def get_info(ws):
    qry = {"op":"info"}    await ws.send(json.dumps(qry))    response = await ws.recv()    return json.loads(response)
def xy_to_linear(x,y):    return y*7 + x
def linear_to_xy(linear):    x = linear % 7       y = linear // 7      return(x,y)
async def find_board(ws):    board_key = []     for x in range(0,4):        response = await send_guess(x,0, ws)        index = xy_to_linear(x,0)        board = response['board']        board_key.append(board[index])     return tuple(board_key)
async def play():
    async with websockets.client.connect(URI,            origin='https://doomed.web.ctfcompetition.com'            ) as ws:
        game = await get_info(ws)
        board_key = await find_board(ws)
        print (f"Board key : {board_key}")        valid_boards = boards.get_all(board_key)        print ("found {} valid boards".format(len(valid_boards)))        order = solve(valid_boards[0])        print(valid_boards[0])         print(order)
        for i in order:            x,y = linear_to_xy(i)            game = await send_guess(x,y, ws)            print_board(game["board"])            if game["message"]:                print('\n\t' + game["message"] + '\n\n')
def print_board(board):    print(" ".join([f'{x: >2}' for x in board] ))
def solve(board):     order = []    for item in range(0,28):        order.extend([i for i, x in enumerate(board) if x == item])    return order
asyncio.get_event_loop().run_until_complete(play())```
