I took part in the OverTheWire Advent Bonanza 2019. All in all, the CTF was very pleasant because the challenges were interesting to solve, there was quite some time available as well (I spent about two weeks on and off on it) and I also managed to solve a few challenges as well.
The following write-up is about the challenge from day 17: snowflake idle.
Description
It's not just leprechauns that hide their gold at the end of the rainbow, elves hide their candy there too.
No source code is given, just a link to a website: http://3.93.128.89:1217
The challenge is tagged as crypto/web.
The website shows a simple "game" where the user can collect snowflakes. Every x seconds, the user gets a new snowflake. Snowflakes can be traded for a higher collection speed. If the user decides to trade their snowflakes, the snowflakes are deducted from the balance but in the same x seconds the user can collect more snowflakes now. If the user collects 10^63 snowflakes, they could trade it for a flag.
The website uses JavaScript on the front-end and communicates with the server via a JSON API. The server is implemented in Flask.
Analysis
Of course, it is not feasible to collect that many snowflakes without cheating so we have to find a vulnerability.
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.
/control
The /control endpoint is used register a new user:
POST /control
{"action":"new","name":"username"}
/client
The /client endpoint is the "main" endpoint (HTTP method: POST) that the front-end uses to e. g. request the state, increase the collection speed or collect a snow flake:
POST /client
{"action":"collect","amount":1}
/history/client
Most interesting is the /history/client endpoint. Sending a GET request to that endpoint returns a JSON that basically contains a log of all actions that the client requested:
[
[
1576940433927,
{
"action": "state"
}
],
[
1576940435274,
{
"action": "collect",
"amount": 1
}
],
...
]
Interestingly, any given action 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 does not really allow us to do anything useful.
/history/control
What we did not realize for a long time was that the /history endpoint happily retrieves the history for other endpoints as well. I. e. /history/control returns data for the /control endpoint.
[
[
1578852889691,
{
"action" : "load"
}
],
[
1578852889691,
{
"data" : "nQZ2wk0avgzGKhYR4Sy5io/o55SCBiGNElPnDJJrS1rzOrmKievng4hFdsgBAg==",
"action" : "save"
}
],
(...)
]
This immediately piqued our interest because ...
- The control endpoint takes an action parameter with value save but the web interface only exposes the action new.
- The control endpoint apparently also takes a data parameter which could be interesting for manipulate the server side state.
Decoding the data leads to binary data which is good: We knew that we discovered the crypto part of the challenge.
Exploit
Note that the following is not 100% "historically" accurate but a streamlined version of what we did and how we succeeded to make the write-up easier to follow.
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}