writeups/litplus/otw19.md

   1 OverTheWire Advent Bonanza 2019
   2 ===============================
   3 CTF write-up by Philipp Nowak (litplus, 11776858)
   4
   5 Overview
   6 --------
   7 Challenges participated in:
   8
   9  * day-02: Summer ADVENTure `solved` - 20.75 hours
  10  * day-23: Gr8 Escape `unsolved` - 0.75 hours
  11  * day-24: Got shell? `solved` `web, linux` - 2.25 hours
  12  * day-25: Lost in Maze `solved` `misc` - 16.00 hours
  13
  14 Total time spent: 39.75 hours (+ 4 hours for writeups) -- More effort TBD
  15
  16 ### Personal Reflection
  17 Since the guidelines require that the whole writeup be in a single file, this has been merged by a very sophisticated shell script. The source files for the individual challenges are located in the [`writeups/litplus/otw19`](..) directory and match the RegEx `Adv-\d{2}.md`.
  18
  19 In general, this CTF was very fun and interesting to play! I originally planned to do more work before Christmas, but other courses sadly did not like this idea *at all*. However, Summer ADVENTure was very interesting, so I continued figuring our more and more things. In the end, it ended up eating most of my Christmas break nights, but I think that I learned a lot of new things. I was surprised that I was able to play such a major part in solving three of the challenges. Another great thing was that I got to play around writing non-trivial Python applications, which is something I had wanted to do for some time anyways.
  20
  21 Cooperation with other team members worked especially well with Suummer ADVENTure, but Gr8 Escape saw nearly zero interest, although this is understandable since the challenge seemed to require a lot of tedious reverse-engineering. I individually didn't feel like I had the correct skill set after taking a closer look.
  22
  23 ### Note on Materials
  24 Sadly, all the challenge servers, including the scoreboard with the challenge descriptions, were taken down before I got to write this. I did not anticipate this extent of take-down, and hence I don't have complete metadata on all challenges. This affects especially the original challenge description, number of solves, and detailed demonstration. Thankfully, I was able to save some screenshots from Summer ADVENTure and the Mattermost channels also had some resources.
  25
  26 ---
  27
  28 day-02 Summer ADVENTure
  29 -----------------------
  30 OverTheWire Advent 2019, day 2
  31
  32 Discussion on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-02-summer-adventure)
  33
  34 Full exploit source code on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-02)
  35
  36 Time spent for this challenge: 20.75hours
  37
  38  * December 10: 3.0 hours (21:00-00:00)
  39  * December 12: 3.0 hours (00:15-03:15)
  40  * December 22: 2.0 hours (22:00-00:00)
  41  * December 23: 6.5 hours (00:00-04:00, 17:00-19:30)
  42  * December 24: 6.25 hours (00:30-05:30, 06:15-06:30, 13:40-14:10)
  43
  44 ### Overview
  45 #### Challenge setup
  46 We are provided with a website that acts as client to a simple adventure game. Instructions on the site state that we do not have hardware access to client or server, the only exploitation path is by intercepting and manipulating network traffic. The server is running at TCP port 12021, and the client runs in some kind of emulator in the browser.
  47
  48 On the site, we can either connect to the genuine server, or connect to our own server. This works by connecting a TCP client to port 12022. The server then responds with a server id that we can enter in the browser to complete the connection.
  49
  50 It seems that this challenge wants to simulate protocol-only access, avoiding usual exploitation paths. The website also states some advice from the challenge author. It is advised not to touch the browser client, as it just streams HTML from a server that handles the actual connection. Further, no insane implementation choices were made, so exploitation should exclusively focus on the protocol.
  51
  52 To prevent excessive brute-force, the game disconnects after 1 MB of traffic (per side), and a 20-second colldown is enforced between logins. Also, accounts are deleted an hour after their last login.
  53
  54 #### Gameplay
  55 The first thing we see after connecting to either server is a login screen. We can create an account by providing a username and password. The username has to be between 4 and 16 characters, the password between 4 and 256.
  56
  57 ![Login screen](otw19/02-login.png)
  58
  59 After logging in, a map is presented. Movement is possible via WASD keys.
  60
  61 ![Map](otw19/02-map.png)
  62
  63 Upon moving to the same square as a monster, a fight starts, where health points are deducted in rounds. Upon winning, the player gains EXP and coins. A health potion can afterwards be used to restore the player's health to the maximum. The maximum depends on the player's level, which is increased by gaining EXP.
  64
  65 ![Fight](otw19/02-fight.png)
  66
  67 The weird entity above the player at the start is their stash. It allows to store excess items, which is helpful because inventory size is limited.
  68
  69 ![Stash view](otw19/02-stash.png)
  70
  71 The other entity inside of the fence is a salesperson. Upon approaching them, a shop GUI opens that allows to buy items for gold. For a huge amount of coins, a "Scroll of Secrets" is offered. This seems like the path to obtain the flag.
  72
  73 ![Shop view](otw19/02-shop.png)
  74
  75 ### Exploitation
  76 **Note:** For brevity, full listings are omitted due to their complexity. Full exploit scripts are available in GitLab, linked above.
  77
  78 #### Basic protocol structure
  79 `@mli` on Mattermost started looking at the protocol. They created a proxy and discovered that responses depend solely on the input (i.e. no reandomised cryptography). Newlines are sent in plain text, suggesting some kind of atomic unit, e.g. packets between them. They further discovered that there is some var-length string encoding involved -- changing the length of the password significantly also affects other bytes.
  80
  81 The next day, `@georg` implemented a basic MITM proxy to recover more information about the protocol. Upon analysis, he discovered that the initial 16 bytes that the server sends are used as XOR key, affecting the responses. However, this is not directly used as a key. As a consequence, he suggested using varying passwords to recover the actual key stream.
  82
  83 Six days later, I started working on the challenge. Every game message is preceded by another two-byte message, which we initially suspected to be some kind of packet id or key rotation mechanism.
  84
  85 I extended `@georg`'s server to store traces in a different format and wrote [a Python program](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/f4c3df3c62066b87ad2ee47ee48fd4a4908f07ba/day-02/crypt_test.py) to parse those.
  86
  87 What this program does is load connection traces stored by the MITM server and play with them. For this, [`common.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/common.py) provides two models that are parsed from the binary/base64 data: `ConnectionTrace` and `TracePacket`. The former keeps trace of the current offset in the stream (crucial for the key schedule) and all packets of the trace. The latter represents a packet and provides operations to get different representations of the ciphertext.
  88
  89 After playing around with captured traces for some time, a pattern emerged: XOR'ing two traces yields the contents of the initial 16-byte message. I was confused for some time because I did not recognise the packet header to be part of the ciphertext. After including this, the pattern was clearly visible. Normally, with deterministic encryption, one would expect the XOR's of two packet traces to yield zero. Here, it becomes obvious that the 16-byte packet is a dynamic key used in the encryption and the rest is static.
  90
  91 Hence, we can obtain a consistent result by XOR'ing the binary stream with the dynamic key. I added this to the analysis program to recover the encoded message, as I thought at the time.
  92
  93 `@georg` however suggested that another key stream was XOR'ed to the encoded message, explaining why the encoding has no obvious correlation with the actual plaintext, even when using all A's as password. He was able to recover around 256 bytes of this *auxilliary key* by using known input, however some bytes were still off because of the unknown encoding. However, he was able to discover that the same key schedule is (independently) used for clientbound messages, recovering the promising plaintext `b'NB[\xd63\x1bInvalid password.'`.
  94
  95 After also adding this auxilliary key to the analysis script, it finally displayed plaintext (at least until the key ends). I also included this in the client directly to save the intermediate step, which made analysis easier. `@georg` suggested simply increasing the money in the join packet, which I tried. Some of the values from the UI are clearly reflected in the plaintext, including the amount of coins.
  96
  97 Changing the byte value however resulted in weird behaviour. When changing from `0x51` (81$) to `0xFF` resulted in $70 being displayed in the client. This hints at integer being encoded in the protocol. Further, changing other game properties that are reflected earlier in the binary stream shifts the location of the money byte. All this hints at some variable-length encoding of numbers.
  98
  99 We tried to reverse-engineer this encoding for some time. We also realised that we can't change the packet length -- this would desynchronise the client's key schedule from the server. A full MITM decryption was not feasible because we did not have enough key material to decrypt and therefore forge the whole join packet.
 100
 101 Utlimately, changing the money in the protocol did not work, because money is tracked server-side (as suggested by the challenge description). The server sends its state with every operation that affects coins, i.e. after fights and purchases.
 102
 103 Latery, `@georg` discovered that the number format corresponds to [a common VarInt format](https://en.wikipedia.org/wiki/Variable-length_quantity). `@Hetti` poked some sticks at the protocol to figure out where certain values are reflected. He also had the idea of executing the same action repetedly on the client to recover a longer auxilliary key stream. (This works because client and server use the same key but an independent schedule.)
 104
 105 Applying this to the client, I was able to recover around 4KB of key stream. I tried to replace some packets, namely the fight request. This however did not allow money gains, as only monsters actually present in the game are accepted by the server. Monster levels are related to player levels. There is always a monster with the same level present.
 106
 107 #### Packet models
 108 Looking for a VarInt decoder online, I stumbled upon one for [Google's protobuf libarary](https://developers.google.com/protocol-buffers/docs/encoding). It worked, but the important catch was protobuf, which is a framework to encode objects into binary streams -- exactly the kind of thing one would use to encode packets that are reused by both peers.
 109
 110 Using [the discovered online protobuf parser](https://protogen.marcgravell.com/decode), I was able to correlate the binary stream to model-level packets. For example, the join packet has a structure of:
 111
 112 ```
 113 * (1) varint: 1
 114 * (2) object
 115   * (1) varint: level 4
 116   * (2) varint: exp 319
 117   * (3) varint: exp-max 400
 118   * (4) varint: weapon-strength 4
 119   * (5) varint: health 280
 120   * (6) varint: health-max 280
 121   * (7) varint: coins 220
 122 * (3) object
 123   * (2) object:
 124     * (2) varint: 10
 125     * (4) object:
 126       * (1) varint: 2
 127       * (2) varint: 1
 128       * (3) ???
 129     * (4) object, repeated:
 130       * (1) varint: 2
 131       * (3) ???
 132   * (2) object, repeated: ...
 133 * (3) object, repeated: ...
 134 * (3) object, repeated: ...
 135 ```
 136
 137 Now, the idea was to reverse-engineer the entire protocol and have our client connect to the server independently of a browser. With this and a long-enough auxilliary key, we could bot the game, obtain the required money, and buy the flag.
 138
 139 I recovered [most of the packet models](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/Packet_Format.md) Next up, we needed a longer XOR key so taht we can reliably bot the server without having to reconnect too often. `@Hetti` helped me realise that it's easy to bot a login failure. This doesn't require and setup and in the browser is only a button. To do this, I simply hid the error dialog using `display: none;` and was able to click the login button repeatedly. This recovered 39 KB of auxilliary key. For this, I used [a specialised MITM server](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/recover_aux_server.py).
 140
 141 I estimated that with this key, we would be able to do around 500 fights (with a 64 byte response) before exhaustion. Expecting constant reward of 10 coins, that results in 5000 coins per session -- including the timeouts, this was expected to take around 11 hours. What I  did not think of here is that the size of the key file refers to base64 text, i.e. the actual key size is smaller.
 142
 143 Later that day, I was able to convert the packet information we obtained thus far [into protobuf model format](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/packets.proto). This can be compiled into Python models using the protobuf compiler. On Arch Linux, it can be installed using `pacman -S protobuf`. Then, running `protoc --python_out=. packets.proto` generates [the models](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/packets_pb2.py) in the current directory.
 144
 145 With this, the client now produced output of this readable form:
 146
 147 ```
 148 join {
 149   success: true
 150   state {
 151     level: 1
 152     expMax: 100
 153     weaponStrength: 1
 154     health: 220
 155     healthMax: 220
 156   }
 157   inventories {
 158     items {
 159       type: MAGICAL_POTION
 160       unknownHealRelated: 100000
 161       prices {
 162         unknownConstant: 2
 163         isBuy: true
 164         value: -10
 165       }
 166 ...
 167 ```
 168
 169 The way packets are represented is by a huge meta-packet that has a field for every packet. Only the packet that is used is filled, all other fields are left unset.
 170
 171 Just adding the `Scroll of Secrets` to the client-side inventory did not do the trick though, since the "Use" operation is processed server-side. Using the scroll while in the shop inventory didn't work either, the server just disconnects.
 172
 173 Finally, the last puzzle piece for full botting was the packet header. This turned out to be the length of the body, but little-endian 🙄.
 174
 175 #### The fight bot
 176 In [the initial state of the fight bot](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/a629482bb9547dbfb6364c09ca74f0505c8649eb/day-02/fake_fight_server.py) we were now able to forge a full fight and have the server respond. The next challenge was that we need to wait for the server response before sending the next request apparently. This significantly increases the time necessary, because the server takes ~400ms RTT to process the request. Also, due to the asynchronous nature of the client, this needed some architecture changes in the exploit.
 177
 178 The first thing I did here was to represent the player state, that is sent on join and after every fight, in a readable manner. This allows to see what the bot is doing. I also wrote some code to forge packets from models using protobuf and the key schedule information stored in `ConnectionTrace`.
 179
 180 The main logic of the bot is located in [`handle_response`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/bc23a28eb375f676975b5f34196ddd67fdff79de/day-02/fake_fight_server.py#L95). This takes a packet from the server. If it has a message set, it is displayed (important because this is how the flag is sent).
 181
 182 After a join packet, the client analyses the player inventory to find the location of the health potion. This is necessary to recover to full health after a fight. Then, it starts a fight. This takes into account the player level. Through trial and error, it has surfaced that the highest monster that can be fought is the player level plus two. Also, rewards scale up with the monster level, which reduces the time required to get the scroll.
 183
 184 After receiving a fight response, we first check if it succeeded. If not, we use the health potion. Otherwise, we continue with the next one. For a use packet, we start a fight since we just had a health potion.
 185
 186 Later, I also added [a mechanism](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/fake_fight_server.py#L287) to initiate a new connection once the key is exhausted or the server disconnects.
 187
 188 Note that for this to work with higehr levels, at some point, stronger weapons need to be bought manually using the genuine server.
 189
 190 I later discovered that we can fight more efficiently by [setting both the fight and potion-use packets in a single request](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/fake_fight_server.py#L161). This reduces the amount of requests we need to send, which is a great deal beacause the main limiting factor on performance is the network RTT for every request (not the processing of packets). Conveniently, the server only includes the fight packet in the response in this case, which saves us some special handling.
 191
 192 ![Bot output](otw19/02-bot.png)
 193
 194 To estimate the amount of time required to bot the game, I used [a GeoGebra file](https://www.geogebra.org/graphing/tusewwdw) to find the relation of player/monster level to coin gain. Factoring in response times, cooldown times and level increase, I created a formula to estimate the time left. This revealed that a huge amount of cooldown time (5 hours) is caused by our short key.
 195
 196 Hence, I made an effort to recover a longer key. For this, I used the same mechanism as before, but additionally a small piece of JavaScript in Chrome DevTools to automate clicking the login button:
 197
 198 ```
 199 const loginButton = document.getElementsByClassName("login")[0];
 200 window.setTimeout(100, () => loginButton.click());
 201 ```
 202
 203 This quickly yielded 200 MB of key stream, which helped reduce cooldown times significantly.
 204
 205 After some waiting, we reached the required 10 million coins:
 206
 207 ```
 208  * Level 1406 [20070/140600] 🗡️ 1406 [❤️ 4299/28320] 💰10021605 +💰432.
 209 ```
 210
 211 Connecting to the genuine server and buying the Scroll of Secrets yielded the following message:
 212
 213 ```
 214 Congratulations! Here is the server-side flag: _is_f0R_Th3_13373sT} The client-side flag is clearly written on a piece of paper that was lost by the shopkeeper some time ago. If only you could find it...
 215 ```
 216
 217 #### Client-side flag
 218 While reversing the protocol, I noticed that item id 7 was not used. This seemed like the perfect use-case for that information. Indeed, [adding this item to the inventory](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/client-side-flag.py) caused the client to reveal its part of the flag in the item description:
 219
 220 ```
 221 Mystery Letter
 222 A letter which reads: 'Here is the client side flag: AOTW{B14ckbOx_N3tw0rK_r3v
 223 ```
 224
 225 This completes the flag to: `AOTW{B14ckbOx_N3tw0rK_r3v_is_f0R_Th3_13373sT}`. Yay!
 226
 227 ### Intended Solution
 228 As `@Hetti` revealed in Mattermost, the intended solution was to use an item duplication bug, as was done by SIGFLAG. `@Felix Kehrer` suspected such a bug, but we discarded this idea too fast.
 229
 230 The way this bug worked was that the server accepted a list of inventories as move target. So, the player was able to move a single item to two inventories at the same time, duplicating it. This can be repeated to obtain expensive items, which have a very large value margin, yielding funds for the flag quickly. I created a [Proof of Concept server](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-02/dupe_server.py#L117), which duplicates items reliably. Those can be sold in the real client, but I wasn't able to get it to work automatically (probably some dumb mistake). However, we already had the flag at this time, so I did not put in further effort.
 231
 232 ### Lessons Learned
 233  * Just because the encryption *seems* like a (reused) One-Time-Pad, doesn't mean it is
 234  * Discovering a very weird format might just mean you're not thinking outside of the box enough, consider how likely challenges could be solved (e.g. here, if I want a standardised protocol, I'll probably use a library that can use the same model on server and client)
 235  * It's always an item duplication
 236  * Python is cool
 237  ---
 238
 239 day-23 Gr8 Escape
 240 -----------------
 241
 242 OverTheWire Advent 2019, day 23
 243
 244 Time spent for this challenge: 0.75 hours
 245
 246  * December 24: 0.75 hours (05:30-06:15)
 247
 248 Writeup TBD
 249
 250 ---
 251
 252 day-24 Got shell?
 253 -----------------
 254 OverTheWire Advent 2019, day 24
 255
 256 Time spent for this challenge: 2.25 hours
 257
 258  * December 24: 2.25 hours (13:30-15:45)
 259
 260 Writeup TBD
 261
 262 ---
 263
 264 day-25 Lost in Maze
 265 -------------------
 266 OverTheWire Advent 2019, day 25
 267
 268 Time spent for this challenge: 16 hours
 269
 270  * December 25: 7 hours (15:30-19:30, 21:00-00:00)
 271  * December 26: 9 hours (00:00-09:00)
 272
 273 Writeup TBD
 274
 275 ---
 276