writeups/litplus/otw19/Adv-02.md

   1 day-02 Summer ADVENTure
   2 -----------------------
   3 OverTheWire Advent 2019, day 2
   4
   5 Discussion on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-02-summer-adventure)
   6
   7 Full exploit source code on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-02)
   8
   9 Time spent for this challenge: 20.75hours + 4 hours write-up
  10
  11  * December 10: 3.0 hours (21:00-00:00)
  12  * December 12: 3.0 hours (00:15-03:15)
  13  * December 22: 2.0 hours (22:00-00:00)
  14  * December 23: 6.5 hours (00:00-04:00, 17:00-19:30)
  15  * December 24: 6.25 hours (00:30-05:30, 06:15-06:30, 13:40-14:10)
  16
  17 ### Overview
  18 #### Challenge setup
  19 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.
  20
  21 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.
  22
  23 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.
  24
  25 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.
  26
  27 #### Gameplay
  28 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.
  29
  30 ![Login screen](02-login.png)
  31
  32 After logging in, a map is presented. Movement is possible via WASD keys.
  33
  34 ![Map](02-map.png)
  35
  36 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.
  37
  38 ![Fight](02-fight.png)
  39
  40 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.
  41
  42 ![Stash view](02-stash.png)
  43
  44 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.
  45
  46 ![Shop view](02-shop.png)
  47
  48 ### Exploitation
  49 **Note:** For brevity, full listings are omitted due to their complexity. Full exploit scripts are available in GitLab, linked above.
  50
  51 #### Basic protocol structure
  52 `@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.
  53
  54 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.
  55
  56 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.
  57
  58 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.
  59
  60 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.
  61
  62 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.
  63
  64 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.
  65
  66 `@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.'`.
  67
  68 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.
  69
  70 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.
  71
  72 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.
  73
  74 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.
  75
  76 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.)
  77
  78 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.
  79
  80 #### Packet models
  81 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.
  82
  83 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:
  84
  85 ```
  86 * (1) varint: 1
  87 * (2) object
  88   * (1) varint: level 4
  89   * (2) varint: exp 319
  90   * (3) varint: exp-max 400
  91   * (4) varint: weapon-strength 4
  92   * (5) varint: health 280
  93   * (6) varint: health-max 280
  94   * (7) varint: coins 220
  95 * (3) object
  96   * (2) object:
  97     * (2) varint: 10
  98     * (4) object:
  99       * (1) varint: 2
 100       * (2) varint: 1
 101       * (3) ???
 102     * (4) object, repeated:
 103       * (1) varint: 2
 104       * (3) ???
 105   * (2) object, repeated: ...
 106 * (3) object, repeated: ...
 107 * (3) object, repeated: ...
 108 ```
 109
 110 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.
 111
 112 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).
 113
 114 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.
 115
 116 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.
 117
 118 With this, the client now produced output of this readable form:
 119
 120 ```
 121 join {
 122   success: true
 123   state {
 124     level: 1
 125     expMax: 100
 126     weaponStrength: 1
 127     health: 220
 128     healthMax: 220
 129   }
 130   inventories {
 131     items {
 132       type: MAGICAL_POTION
 133       unknownHealRelated: 100000
 134       prices {
 135         unknownConstant: 2
 136         isBuy: true
 137         value: -10
 138       }
 139 ...
 140 ```
 141
 142 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.
 143
 144 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.
 145
 146 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 🙄.
 147
 148 #### The fight bot
 149 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.
 150
 151 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`.
 152
 153 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).
 154
 155 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.
 156
 157 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.
 158
 159 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.
 160
 161 Note that for this to work with higehr levels, at some point, stronger weapons need to be bought manually using the genuine server.
 162
 163 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.
 164
 165 ![Bot output](02-bot.png)
 166
 167 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.
 168
 169 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:
 170
 171 ```
 172 const loginButton = document.getElementsByClassName("login")[0];
 173 window.setTimeout(100, () => loginButton.click());
 174 ```
 175
 176 This quickly yielded 200 MB of key stream, which helped reduce cooldown times significantly.
 177
 178 After some waiting, we reached the required 10 million coins:
 179
 180 ```
 181  * Level 1406 [20070/140600] 🗡️ 1406 [❤️ 4299/28320] 💰10021605 +💰432.
 182 ```
 183
 184 Connecting to the genuine server and buying the Scroll of Secrets yielded the following message:
 185
 186 ```
 187 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...
 188 ```
 189
 190 #### Client-side flag
 191 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:
 192
 193 ```
 194 Mystery Letter
 195 A letter which reads: 'Here is the client side flag: AOTW{B14ckbOx_N3tw0rK_r3v
 196 ```
 197
 198 This completes the flag to: `AOTW{B14ckbOx_N3tw0rK_r3v_is_f0R_Th3_13373sT}`. Yay!
 199
 200 ### Intended Solution
 201 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.
 202
 203 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.
 204
 205 Possibly related, in the [suggested solution](https://github.com/OverTheWireOrg/advent2019/tree/master/advent-challenges/2019-12-02_rev3/solution), the bug is described as moving from an inventory to itself.
 206
 207 Also, the constant auxilliary stream we assumed is not quite correct. The [actual implementation](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-02_rev3/common/EncryptedStream.cs) uses AES in ECB mode. However, this amounts to the same behaviour as we assumed and is also the suggested solution.
 208
 209  ---
 210