inCTF 2020 Writeup – Gamebot

I spent the past weekend competing (as part of FrenchRoomba) in bi0s's inCTF. It was an enjoyable CTF, with an especially nice set of Misc flags. Here's a writeup of one of my favourites (with only 3 solves)!

The Challenge

The challenge description hints that some robots are communicating in a format you might find on a tape in the 60s or 70s. We are told to nc 34.70.233.147 5555:

@@@@@@@@   @@@@@@   @@@@@@@@@@   @@@@@@@@  @@@@@@@    @@@@@@@@   @@@@@@@  
@@@@@@@@@  @@@@@@@@  @@@@@@@@@@@  @@@@@@@@  @@@@@@@@  @@@@@@@@@@  @@@@@@@  
!@@        @@!  @@@  @@! @@! @@!  @@!       @@!  @@@  @@!   @@@@    @@!    
!@!        !@!  @!@  !@! !@! !@!  !@!       !@   @!@  !@!  @!@!@    !@!    
!@! @!@!@  @!@!@!@!  @!! !!@ @!@  @!!!:!    @!@!@!@   @!@ @! !@!    @!!    
!!! !!@!!  !!!@!!!!  !@!   ! !@!  !!!!!:    !!!@!!!!  !@!!!  !!!    !!!    
:!!   !!:  !!:  !!!  !!:     !!:  !!:       !!:  !!!  !!:!   !!!    !!:    
:!:   !::  :!:  !:!  :!:     :!:  :!:       :!:  !:!  :!:    !:!    :!:    
::: ::::  ::   :::  :::     ::    :: ::::   :: ::::  ::::::: ::     ::    
:: :: :    :   : :   :      :    : :: ::   :: : ::    : : :  :      :     

b'eJzt0zEKwjAUBuBXcHD0CJ5DlzpYcHXQuSBubj2YR+hRPIri5iTyEq3w8ZGpSd6fl3S/67rZOuK4OWzPl2G5iIjm4TqL52hiHqd+6G+riHYEAAAAAADS2vF1fPr93fzS+2fzZ+vVzl961O5H7fdTen7p9VPL/+v6pdfXfs/+31z92vWy+/17/0vfT+382fNl+5XNXzrf1PJP/f1nz5ft17fz194PAAAAAACo7g4i1nnr'

The connection stays open after printing this first line. If we provide a line of input, we get a second line back, and the connection is closed:

b'eJzt1D0KwkAQhuEJWFh6BI8SQQO2FloHxM4uB/IIHiGFBzPYWQ7zsxN4edgqu8k3w2wu52H4HEVuh+vp8Zz2OxHpFu+N/FYnW7mP0/ha9vQzAAAAAAAAAAAw6+f/Ve25Nr/3+7z3W/ujXdn5vetpnT86T/b8aOvPzu+9vOu15o/uX/Z56/uYn7Z5oudn7fm1eavnj+6H9/ei81T7/3j3z5rfuj87v/V56/nR7q/e/7Xlj77P0fVb81i/H53fux7+P8x/pf5b62udP/q+Zp+v3n8AAAAAAAAAAGD2BcEBWsk='

The second blob is always the same, regardless of what input we give, but the first seems to be different each time we connect. I connected a bunch of times, saving the responses, so we can look for patterns:

for f in sample-* # for each saved response file
do
 awk 'NR==13{print}' "$f" # get its 13th line
done | sort | uniq -c # and count the occurrences of each option

Occurrences	Output
10	`b'eJzt0zEKwkAQBdAJWFh6BM+hTSwM2FpoHRA7uxzMI+QoHkWxsxLZWUzg8Zgquzs/m8nx0HWLbcR5d9pfb8N6FRHNy30R72piGZd+6B+biHYEAAAAAACKteNn/fr82/rs80vzl/arnT+7at9H7fnJXp+9f2r5/90/e3/tefb/lvWv3a/0vLnff/b3qZ2/9P1K76s0f3a+qeWf2/xn95/a/Nc+DwAAAAAAqO4JItZ56w=='`
9	`b'eJzt0zEKwkAQAMANpLD0Cb5Dm1gYsLXQOiB2dnmYT8hTfIpiZyXh7kyUYdgqd7vL3uawb9t6E3HaHneXa79aRkT1dKvjFVUs4tz13X0d0QwAAAAAAECyZniPsd8/nc+dP7X/1Hql+88dpedRen9yn899f279T10/9/3S++z/Tatful5qvl+ff+73mVv/Y+tP3f/YfHPr/9/2f277k1rv2/MHAAAAAACSPQAe1nnr'`
8	`b'eJzt0zEKwjAUBuBXcHD0CJ5DlzpYcHXQuSBubj2YR+hRPIri5iQliY3w8fGmJu/9TdPjoesW24jz7rS/3ob1KiKal/si3tXEMi790D82Ee0IAAAAAAAka8fPmvr82/rc/VPzp84rnT93lT6P0vcn9/rc+2vLP/f83PtL32f/b9r80vNS+/37+ef+PrXlnzp/7vxT+9WWv/b7n/p+qef16/yl+wEAAAAAAMU9ASDWees='`
6	`b'eJzt0zEKwjAUBuBXcHD0CJ5DlzpYcHXQuSBubj2YR+hRPIri5iTyEq3w8ZGpSd6fl3S/67rZOuK4OWzPl2G5iIjm4TqL52hiHqd+6G+riHYEAAAAAADS2vF1fPr93fzS+2fzZ+vVzl961O5H7fdTen7p9VPL/+v6pdfXfs/+31z92vWy+/17/0vfT+382fNl+5XNXzrf1PJP/f1nz5ft17fz194PAAAAAACo7g4i1nnr'`
7	`b'eJzt0zEKwkAQBdAJpLD0CJ5Dm1go2FpoLYidXQ7mEXIUj6LYWYnMrkZ5PLbK7s7PZLLdrNftImK/3K1O5342jYjm7tLGYzUxieOhP1znEd0AAAAAAACkdcPzevf5q/2l78/mz9arnb/0qt2P2vNTen/p82PL/+36pc/Xnmf/b65+7XrZ+369/6W/T+382ffL9iubv3S+seX/t/kf2/xk6326/wAAAAAAQNoNINZ56w=='`
5	`b'eJzt0zEKwkAQBdAJWFh6BM+hTSwUbC20DoidXQ7mEXIUj6LYWUnYWRLh8Zgquzs/m8npeDgsthGX3Xl/u/frVUQ0b49FfKqJZVy7vntuItoBAAAAAAAo1g7fNfb5r/XZ55fmL+1XO3921b6P2vOTvT57/9zyT90/e3/tefb/lvWv3a/0vH+//+zvM7f8Y/tPnX/seXPL/2/zn92/dv7s96udHwAAAAAAKPYCINZ56w=='`
4	`b'eJzt0zEKwkAQAMANWFj6BN+hTSwM2FpoHRA7uzzMJ+QpPkWxs5Jwd+aEYdgqd7ubzeZ46LrFNuK8O+2vt2G9iojm5b6IdzSxjEs/9I9NRDsCAAAAAADJ2vEzpj7/dj53/tT+U+uV7j93lJ5H6f3JfT73/dr6n7t+7vul99n/m1a/dL3UfP8+/9zfp7b9mVp/7vlPzVdb/7Xvf+r7pc7r1/2XzgcAAAAAABT3BCLWees='`
3	`b'eJzt0zEKwkAQAMANpLD0Cb5Dm1gYsLXQOiB2dnmYT8hTfIpiZyXh7kyUYdgqd7vL3uawb9t6E3HaHneXa79aRkT1dKvjFVUs4tz13X0d0QwAAAAAAECyZniPsd8/nc+dP7X/1Hql+88dpedRen9yn899f279T10/9/3S++z/Tatful5qvl+ff+73mdv+jK0/9fzH5ptb//+2/3Pbn9R6354/AAAAAACQ7AEg1nnr'`
3	`b'eJzt0zEKwlAMANAUHBw9gufQpQ4Krg46F8TNrQfzCD2KR1HcnKT8fFrh8cjU/5M0TU/Hw2GxjbjszvvbvV+vIqJ5eyziE00s49r13XMT0Q4AAAAAAECxdviOsc9/nc/OX9p/ab3a/WdH7XnU3p/s89n359b/1PWz79feZ/9vWf3a9Urz/fv8s7/P3PZnbP2p5z8239z6/7f9z65fu//s96vdPwAAAAAAUOwFItZ56w=='`

We see that there are (at least) nine possibilities, seemingly selected at random. There are some slight variations in length, and some common patterns between them.

All the blobs are wrapped in b'', which is how python3 prints out bytes objects. If we strip that out and just look at the string inside, we're left with something that seems a lot like base64 – let's test this theory:

cat sample-1 |
        awk 'NR==13{print}' "$f" | # print its 13th line
        sed -E "s/^b'(.*)'$/\1/" | # strip the surrounding b''
        base64 -d | # decode base64
        file - # inspect the decoded data

base64 decodes the data without complaint, and file manages to identify the contents:

/dev/stdin: zlib compressed data

There isn't a standard unix utility for zlib decompression (without a gzip header, at least), but the zlib-flate tool is widely packaged as part of qpdf.

Piping through zlib-flate -uncompress, file identifies what's inside the next layer:

/dev/stdin: RIFF (little-endian) data, WAVE audio, Microsoft PCM, 8 bit, mono 1200 Hz

We get an audio file – there is a constant 600Hz tone, and a burst of activity in the middle. I tried some tools for decoding data from various tape formats, as hinted in the description, but none produced any output.

Zooming in on the waveform in Audacity, some structure becomes clear:

The signal is switching between two distinct frequencies – this is a simple form of digital-over-analog data transmission known as FSK (frequency shift keying). This pattern is also visible if we inspect the wave file in a hex editor:

Every run of 16 bytes (16 audio samples) alternates between high and low values either every byte (600Hz), or every second byte (300Hz). Each of these 16-sample runs represents either a low or high bit.

Let's see what we end up with after decoding a blob like this, and resizing the window until patterns seem to line up (12 characters wide):

111111111111
[1s truncated]
111111111111
101111111111
101110100110
001110111100
101110010000
101110110110
001110110111
101110111011
001110110010
001110010000
001110011101
001110010000
001110010100
001110011000
001110010110
001110010000
101110011000
111110010100
111111111111
[1s truncated]
111111111111

Chopping off all the 1s at the start and end:

010011010111
011110010111
001000000111
011011010111
011011110111
011101100111
011001010111
001000000111
001110100111
001000000111
001010000111
001100000111
001011000111
001000000111
001100000111
001010010111

Now we're left with what could reasonably be ASCII text (note the 0 MSB), separated by "0111". Let's decode it:

My move : (0, 0)

Decoding script (essentially indistinguishable from the ramblings of a deranged markov chain fed a corpus of bash one-liners)

SHALL WE PLAY A GAME

Let's decode all of the blobs we've collected, to try and figure our what we're being asked to do:

Occurrences	Decoded text
9	`My move : (0, 0)`
8	`My move : (0, 1)`
5	`My move : (0, 2)`
7	`My move : (1, 0)`
6	`My move : (1, 1)`
10	`My move : (1, 2)`
3	`My move : (2, 0)`
4	`My move : (2, 1)`
3	`My move : (2, 2)`

And, when we send a line of text:

Unable to decompress the data

Presumably we're supposed to communicate back to the server in the same format (and the server is trying to unzlib our message unsuccessfully).

The moves we've seen the server make are all pairs of numbers in the range 0-2, presumably coordinates. Mulling this over for a while, it seems likely we're supposed to play Naughts and Crosses!

We grabbed the unbeatable Tic Tac Toe AI from this article, and modified it to perform I/O in this format:

~ $ python tictac.py
My move : (0, 0)
(1, 1)
My move : (1, 0)
(2, 0)
My move : (0, 2)
(0, 1)
My move : (2, 2)
(2, 1)

Piping this in a circle with nc via our encoder/decoder scripts, we can play a game!

My move : (0, 0)
(1, 1)
My move : (1, 2)
(0, 2)
My move : (1, 0)
(2, 0)
You won! now the score is 1(won):0(drawn):0(lost)
onto the next!
My move : (1, 0)

If we let play continue for 50 games:

You won! now the score is 39(won):11(drawn):0(lost)
That's not good enough.

At this point we were somewhat confused. We saw four possibilities:

Our AI is making incorrect moves (which we couldn't find any evidence of, looking through the logs)
We're supposed to predict the server's behavior and act accordingly, e.g. with a side-channel leakage or an RNG attack
We're supposed let the server win, flattering it into thinking it's really smart so it gives us the flag (???)
We're supposed to force a draw, so it comes to understand the futility of GLOBAL THERMONUCLEAR WAR, ushering in an era of world peace and flags

None of these seemed particularly compelling, so I dejectedly went off to help my teammates with other challenges.

Coming back later, I reran the script. The server seems to make random moves, so maybe there's a chance we'll get lucky and win enough games (however many that is)? It turns out there is!

You won! now the score is 47(won):3(drawn):0(lost)
inctf{W3W_U_B3aT_A_DUMB_ROBOT_builT_W1Th_random}

Complete scripts

Decoding a blob

#!/bin/sh
tr -d "'" |
  cut -c 2- |
  base64 -d |
  zlib-flate -uncompress |
  tail -c +13 |
  xxd -c 16 |
  cut -c 10-50 |
  head -n -1 |
  tac |
  tr -d ' ' |
  sed -E 's/40|3f/0/g;s/c0|bf/1/g'  |
  sed 's/0011001100110011/0/;s/0101010101010101/1/' |
  tr -d '\n' |
  cut -c 374- |
  grep -o '............' |
  cut -c 5- |
  grep -v '^11111111$' |
  python -c 'while True: print(chr(int(input(),2)))' 2>/dev/null |
  tac |
  tr -d '\n'; echo

Encoding a blob

#!/bin/zsh
grep -o . | tac | tr -d '\n' | # Reverse the input
  xxd -b -c 1 | cut -c 11-18 | # Convert to binary
  sed 's/^/0111/' | # Add the byte delimiters
  \ # Add all the constant data
  tail -c +2 |
  cat <(printf '1') - |
  cat - <(echo '011111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n111111111111\n1111') |
  tr -d '\n' |
  cat <(printf '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111') - |
  \ # FSK-encode
  grep -o . |
  sed 's/0/a/;s/1/b/;s/a/0011001100110011/;s/b/0101010101010101/' |
  sed 's/0/a/g;s/1/b/g;s/a/40/g;s/b/c0/g' |
  \ # Add WAV header (we're still working in reverse, so it goes at the end)
  cat - <(printf 'b00400000100080064617461e03a0000\n666d74201000000001000100b0040000\n') |
  grep -o .... |
  tr '\n' ' ' |
  grep -o ........................................ |
  sed 's/^/ /' |
  tac |
  cat - <(printf ' 40c0 40c0 40c0 40c0 40c0 40c0 40c0 40c0 \n') |
  cat <(printf '5249 4646 043b 0000 5741 5645') - |
  xxd -r -p |
  \ # Compress
  zlib-flate -compress |
  \ # Base64 encode
  base64 |
  tr -d '\n'

Naughts and Crosses AI

import sys

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

def displayBoard(b):
    eprint('     |     |')
    eprint('  ' + b[0] + '  |  ' + b[1] + '  |  ' + b[2])
    eprint('     |     |')
    eprint('-----------------')
    eprint('     |     |')
    eprint('  ' + b[3] + '  |  ' + b[4] + '  |  ' + b[5])
    eprint('     |     |')
    eprint('-----------------')
    eprint('     |     |')
    eprint('  ' + b[6] + '  |  ' + b[7] + '  |  ' + b[8])
    eprint('     |     |')
    eprint("")

Playing = True
def checkWin(b, m):
    return ((b[0] == m and b[1] == m and b[2] == m) or  # H top
            (b[3] == m and b[4] == m and b[5] == m) or  # H mid
            (b[6] == m and b[7] == m and b[8] == m) or  # H bot
            (b[0] == m and b[3] == m and b[6] == m) or  # V left
            (b[1] == m and b[4] == m and b[7] == m) or  # V centre
            (b[2] == m and b[5] == m and b[8] == m) or  # V right
            (b[0] == m and b[4] == m and b[8] == m) or  # LR diag
            (b[2] == m and b[4] == m and b[6] == m))  # RL diag
def checkDraw(b):
    return ' ' not in b

def getBoardCopy(b):
    # Make a duplicate of the board. When testing moves we don't want to 
    # change the actual board
    dupeBoard = []
    for j in b:
        dupeBoard.append(j)
    return dupeBoard

def testWinMove(b, mark, i):
    # b = the board
    # mark = 0 or X
    # i = the square to check if makes a win 
    bCopy = getBoardCopy(b)
    bCopy[i] = mark
    return checkWin(bCopy, mark)

def getComputerMove(b):
    # Check computer win moves
    for i in range(0, 9):
        if b[i] == ' ' and testWinMove(b, 'X', i):
            return i
    # Check player win moves
    for i in range(0, 9):
        if b[i] == ' ' and testWinMove(b, '0', i):
            return i
    # Check computer fork opportunities
    for i in range(0, 9):
        if b[i] == ' ' and testForkMove(b, 'X', i):
            return i
    # Check player fork opportunities, incl. two forks
    playerForks = 0
    for i in range(0, 9):
        if b[i] == ' ' and testForkMove(b, '0', i):
            playerForks += 1
            tempMove = i
    if playerForks == 1:
        return tempMove
    elif playerForks == 2:
        for j in [1, 3, 5, 7]:
            if b[j] == ' ':
                return j
    # Play center
    if b[4] == ' ':
        return 4
    # Play a corner
    for i in [0, 2, 6, 8]:
        if b[i] == ' ':
            return i
    #Play a side
    for i in [1, 3, 5, 7]:
        if b[i] == ' ':
            return i
def testForkMove(b, mark, i):
    # Determines if a move opens up a fork
    bCopy = getBoardCopy(b)
    bCopy[i] = mark
    winningMoves = 0
    for j in range(0, 9):
        if testWinMove(bCopy, mark, j) and bCopy[j] == ' ':
            winningMoves += 1
    return winningMoves >= 2

while Playing:
    InGame = True
    board = [' '] * 9
    playerMarker = '0'
    displayBoard(board)

    while InGame:
        if playerMarker == '0':
            l=input().split(" ")

            move = int(l[3][1]) + int(l[4][0])*3
            if board[move] != ' ':
                print('Invalid move!')
                continue
        else:
            move = getComputerMove(board)
            print("({}, {})".format(move%3,move//3))
        board[move] = playerMarker
        if checkWin(board, playerMarker):
            InGame = False
            displayBoard(board)
            continue
        if checkDraw(board):
            InGame = False
            displayBoard(board)
            continue
        displayBoard(board)
        if playerMarker == '0':
            playerMarker = 'X'
        else:
            playerMarker = '0'