Rating: 3.0
# Doomed to Repeat It
## Description
Play the classic game Memory. Feel free to download and study the source code.
[https://doomed.web.ctfcompetition.com/](https://doomed.web.ctfcompetition.com/)
## Summary
The task is to complete a game of [Memory (also known as Concentration)](https://en.wikipedia.org/wiki/Concentration_(card_game)) with a set of 56 cards in no more than 60 tries. There are 28 distinct pairs of cards marked 0 through 27. This means that you can flip no more than two pairs of mismatched cards. A weakness in the method for randomizing cards allows collection of game boards that have a high probability of being reused.
## Method for solving
### Approach
1. Collect a large set of boards using the Golang code provided in the challenge attachment. See results in `boards.txt`. See added `NewBoard` function in `modified/game/game.go` and command line argument added to `main` in `modified/main.go`. Command: `go run memory 100000 > boards.txt`
2. Reduce the set of boards to boards that are duplicated. See results in `dupes.txt`. Command: `sort boards.txt | uniq -d > dupes.txt`
3. Create a dictionary of duplicated boards where the key is the first four cards. Flip four cards. If the key for the first four cards is in the dictionary, attempt to solve. Quit if the key is not in the dictionary or if there are any mismatches after flipping the first four cards. See `doomed.py`. I used Python 3.6.8 and the [websockets](https://pypi.org/project/websockets/) library (version 7.0). You probably want to use a virtualenv:
```
python3 -m venv venv
. venv/bin/activate
pip install websockets
python doomed.py
```
See results.txt for a successful attempt. Flag: `CTF{PastPerf0rmanceIsIndicativeOfFutureResults}`
### Observations
* Of the 100,000 boards I collected (`boards.txt`), 23,438 boards were duplicated (`dupes.txt`). This means that I should have found a duplicate about 1 out of every 4 or 5 attempts when running `doomed.py`. This seemed to be roughly the case.
* The comments in `random/random.go` heavily imply that the randomization is bad, but I went through the approaches below before making a pass through the provided code.
## Obstacles and approaches that didn't work
### Exploiting JavaScript
The link in the challenge description provides a nice UI in your browser for the game. If you click a card, it flips it over and starts a 10 second countdown until you click another card. It keeps track of turns used and ends if you run out of time or exhaust the cap of 60 attempts.
At first, I thought that it might be possible to exploit the client side to extend the time limit or reveal the board. However, both are handled on the server side.
### Origin header
The source code shows that the application uses WebSockets. The JavaScript source code inspects the protocol to use `ws://` or `wss://` for the WebSocket URI. I started writing a client in Python using the [websockets](https://pypi.org/project/websockets/) library, but I got an HTTP 302 when using `ws://` and an HTTP 403 when using `wss://`. The [Gorilla WebSocket](https://github.com/gorilla/websocket) library used in the Golang server checks that the origin header matches. The Python [websockets](https://pypi.org/project/websockets/) library allows you to set the origin to whatever you want.
### Playing perfectly
The first iteration of `doomed.py` attempted to just keep track of flipped cards and play a perfect game. However, you have to be very lucky to match 28 pairs and only make two mistakes, even if you have a perfect memory.
## Code
### Function in game.go to expose new boards
```go
func NewBoard() ([]byte) {
board, _ := newBoard()
data, _ := json.Marshal(board.nums)
return data
}
```
### Modified main function in main.go
```go
func main() {
// flag.txt should have no newline
flag, err := ioutil.ReadFile("flag.txt")
if err != nil {
log.Fatalf("Couldn't read flag: %v", err)
}
if len(os.Args) > 1 {
n, _ := strconv.Atoi(os.Args[1])
for i := 0; i < n; i++ {
data := game.NewBoard()
fmt.Printf("%s\n", data)
}
} else {
http.HandleFunc("/_ah/health", healthCheckHandler)
http.Handle("/", &rootHandler{flag: string(flag)})
log.Print("Listening on port 8080")
log.Fatal(http.ListenAndServe(":8080", nil))
}
}
```
### doomed.py
```python
import asyncio
import json
import random
import sys
import websockets
guesses = dict()
matched = []
known = [-1 for i in range(56)]
done = False
async def guess(websocket, x, y):
msg = dict(op="guess", body=dict(x=x, y=y))
await websocket.send(json.dumps(msg))
response_str = await websocket.recv()
response = json.loads(response_str)
global done
board = response["board"]
done = response["done"]
index = y * 7 + x
value = board[index]
known[index] = value
print("%d, %d: " % (x, y), value)
if value not in guesses:
guesses[value] = [index]
else:
guesses[value].append(index)
if "Flag" in response_str:
print(response["message"])
done = True
return value
async def solve(uri):
# Returns 403 if origin header not set.
origin = "https://doomed.web.ctfcompetition.com"
async with websockets.client.connect(uri, ssl=True, origin=origin) as websocket:
msg = dict(op="info")
await websocket.send(json.dumps(msg))
response = await websocket.recv()
print(f"> {response}")
dupes = dict()
with open("dupes.txt") as f:
for line in f:
dupe = json.loads(line)
key = "%d, %d, %d, %d" % (dupe[0], dupe[1], dupe[2], dupe[3])
dupes[key] = dupe
# Flip the first four cards.
first = await guess(websocket, 0, 0)
second = await guess(websocket, 1, 0)
third = await guess(websocket, 2, 0)
fourth = await guess(websocket, 3, 0)
key = "%d, %d, %d, %d" % (first, second, third, fourth)
if key in dupes:
print("FOUND DUPE!")
for index, value in enumerate(dupes[key][4:]):
if value not in guesses:
guesses[value] = [index + 4]
else:
guesses[value].append(index + 4)
else:
print("No match. Game over.")
return
while(not done):
for value in guesses.keys():
if len(guesses[value]) == 2 and value not in matched:
first_index = guesses[value][0]
first_x = first_index % 7
first_y = first_index // 7
first = await guess(websocket, first_x, first_y)
second_index = guesses[value][1]
second_x = second_index % 7
second_y = second_index // 7
second = await guess(websocket, second_x, second_y)
if first == second:
matched.append(value)
print("MATCHED: ", matched)
else:
print("MISS!!" , first, second)
print("Dupe doesn't match. Game over.")
return
not_found = [i for i, val in enumerate(known) if val == -1]
if not_found:
next_guess = random.choice(not_found)
else:
return
x = next_guess % 7
y = next_guess // 7
first = await guess(websocket, x, y)
if len(guesses[first]) == 2:
next_guess = guesses[first][0]
matched.append(first)
else:
not_found = [i for i, val in enumerate(known) if val == -1 and i != next_guess]
next_guess = known.index(-1)
next_guess = random.choice(not_found)
x = next_guess % 7
y = next_guess // 7
second = await guess(websocket, x, y)
if first not in matched:
if first == second:
matched.append(first)
print("MATCHED: ", matched)
uri = "wss://doomed.web.ctfcompetition.com/ws"
asyncio.get_event_loop().run_until_complete(solve(uri))
```
