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 (+ 6.5 hours for writeups) -- More effort TBD
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 Time spent for this challenge: 2.25 hours
461 * December 24: 2.25 hours (13:30-15:45)
469 OverTheWire Advent 2019, day 25
471 Time spent for this challenge: 16 hours
473 * December 25: 7 hours (15:30-19:30, 21:00-00:00)
474 * December 26: 9 hours (00:00-09:00)
SomeNet / public repos / pub / jan / ctf-seminar.git / blob