writeups/litplus/otw19/Adv-23.md

   1 day-23 Gr8 Escape
   2 -----------------
   3
   4 OverTheWire Advent 2019, day 23
   5
   6 Statements on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-23-gr8-escape)
   7
   8 Time spent for this challenge: 0.75 hours + 2.5 hours write-up
   9
  10  * December 24: 0.75 hours (05:30-06:15)
  11
  12 ### Overview
  13 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.
  14
  15 ![Elves make Christmas toys, comic](https://mattermost.w0y.at/files/kbyt9uw7opncfqy4tyo9x1ogmc/public?h=PAVYjFNKSNs8V0JSGrStUyv8hrM2ZSpGpK2yOZ0tCvM)
  16
  17 A TCP service was provided at `nc 3.93.128.89 1223`. Upon connecting, it shows a banner and presents a prompt:
  18
  19 ![Gr8 Escape banner and "game:" prompt](23-start.png)
  20
  21 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.
  22
  23 ### Exploitation
  24
  25 `@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.
  26
  27 The first thing I did was try to input a lot of `A`s into the application. Sometimes, it did this:
  28
  29 ![blank screen with some kind of frame](https://mattermost.w0y.at/files/dk7z9zmawi8m5mjts6rjga9s9h/public?h=F0IifdSufQcIDBTSH8iVcI2LhXfz6dMbI9PoJ08daVc)
  30
  31 However, this was not always reproducible and also did not lead anywhere.
  32
  33 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.
  34
  35 The yielded a huge C++ file with huge unintelligible functions along the lines of this:
  36
  37 ```
  38  uint64_t rcx89;
  39     void** rax90;
  40     uint64_t rax91;
  41
  42     rsp4 = reinterpret_cast<void*>(reinterpret_cast<int64_t>(__zero_stack_offset()) - 8 - 8 - 8 - 8 - 8 - 8 - 0x198);
  43     v5 = rdi;
  44     rax6 = g28;
  45     v7 = rax6;
  46     v8 = reinterpret_cast<void**>(reinterpret_cast<uint64_t>(rsp4) + 15 & 0xfffffffffffffff0);
  47     if (!rsi || (r13_9 = rsi, rbx10 = reinterpret_cast<void**>(reinterpret_cast<unsigned char>(*reinterpret_cast<void***>(rsi)) & 0xfffffffffffffffe), rbx10 == 0)) {
  48         addr_44d6f4_2:
  49         *reinterpret_cast<int32_t*>(&rbx10) = 0;
  50         *reinterpret_cast<int32_t*>(&rbx10 + 4) = 0;
  51     } else {
  52         r15_11 = rdx;
  53         rax12 = rbx10;
  54         *reinterpret_cast<int32_t*>(&r14_13) = 0;
  55         *reinterpret_cast<int32_t*>(reinterpret_cast<int64_t>(&r14_13) + 4) = 0;
  56         v14 = 40;
  57         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) {
  58             rbx20 = reinterpret_cast<void**>(r14_13 * 8);
  59             if (v14 == *reinterpret_cast<int32_t*>(&r14_13)) {
  60                 v14 = v14 + 20;
  61                 rdx = rbx20;
  62 ```
  63
  64 To make matters more interesting, the program also includes numerous blocks of raw assembly instructions like this:
  65
  66 ```
  67     if (*reinterpret_cast<uint32_t*>(&rcx6) <= 48 && *reinterpret_cast<uint32_t*>(&rax7) <= 48) {
  68         __asm__("movlpd xmm1, [rdi]");
  69         __asm__("movlpd xmm2, [rsi]");
  70         __asm__("movhpd xmm1, [rdi+0x8]");
  71         __asm__("movhpd xmm2, [rsi+0x8]");
  72         __asm__("pxor xmm0, xmm0");
  73         __asm__("pcmpeqb xmm0, xmm1");
  74         __asm__("pcmpeqb xmm1, xmm2");
  75         __asm__("psubb xmm1, xmm0");
  76         __asm__("pmovmskb edx, xmm1");
  77         if (*reinterpret_cast<int32_t*>(&rdx) - 0xffff)
  78             goto 0x42b010;
  79         if (rdx <= 16)
  80             goto 0x42b024;
  81     }
  82 ```
  83
  84 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.
  85
  86 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:
  87
  88 ```
  89 uint32_t fun_40208d(void** rdi, void** rsi, void** rdx, void** rcx, void** r8, void** r9, int64_t a7) {
  90     void** rax8;
  91     void** v9;
  92     void** rax10;
  93     int32_t v11;
  94     int32_t v12;
  95     uint32_t ecx13;
  96     uint32_t eax14;
  97
  98     rax8 = fun_421e80(0x1000);
  99     v9 = rax8;
 100     if (v9) {
 101         fun_4117a0("game: ", rsi, rdx, rcx, r8, r9);
 102         rax10 = fun_44bf60(0, v9, 0xe00, rcx, r8);
 103         v11 = *reinterpret_cast<int32_t*>(&rax10);
 104         if (v11 > 0) {
 105             if (v11 <= 0xe00) {
 106                 v12 = 0;
 107                 while (v12 < v11) {
 108                     ecx13 = *reinterpret_cast<unsigned char*>(reinterpret_cast<unsigned char>(v9) + reinterpret_cast<uint64_t>(static_cast<int64_t>(v12)));
 109                     *reinterpret_cast<signed char*>(v12 + 0x200 + 0x6dbd4a) = *reinterpret_cast<signed char*>(&ecx13);
 110                     ++v12;
 111                 }
 112                 eax14 = 1;
 113             } else {
 114                 eax14 = 0;
 115             }
 116         } else {
 117             eax14 = 0;
 118         }
 119     } else {
 120         eax14 = 0;
 121     }
 122     return eax14;
 123 }
 124 ```
 125
 126 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.
 127
 128 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.
 129
 130 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.
 131
 132 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.
 133
 134 ### Intended solution
 135 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.
 136
 137 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.
 138
 139 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.
 140
 141 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.
 142
 143 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.
 144
 145 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.
 146
 147 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.
 148
 149 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.
 150
 151 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.
 152
 153 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.
 154
 155 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))
 156
 157  * `0x0---`: compound
 158    * `0x0-00`: SYS -- does nothing
 159    * `0x0-E0`: CLS -- clear screen and draw
 160    * `0x0-EE`: RET -- decrement stack pointer, jump to previous location.
 161  * `0x1***`: JP -- set program counter to `***`.
 162  * `0x2***`: CALL -- push current address to stack, jump to `***`
 163  * `0x3*~~`: SE -- if `cpu.v[*]` is `~~`, `pc+=4`, otherwise `pc+=2` (conditional)
 164  * `0x4*~~`: SNE -- same as SE but with not-equal
 165  * `0x5*~-`: SE -- compares `cpu.v[*]` to `cpu.v[~]`, otherwise like SE
 166  * `0x6*~~`: LD -- loads constant `~~` to `cpu.v[*]`
 167  * `0x7*~~`: ADD -- Adds `~~` to `cpu.v[*]`, overflow bit in `cpu.v[F]`.
 168  * `0x8---`: register operations
 169    * `0x8*~0`: LD -- from `cpu.v[~]` into `cpu.v[*]`
 170    * `0x8*~1`: OR -- `cpu.v[~]` into `cpu.v[*]`
 171    * `0x8*~2`: AND -- `cpu.v[~]` into `cpu.v[*]`
 172    * `0x8*~3`: XOR -- `cpu.v[~]` into `cpu.v[*]`
 173    * `0x8*~4`: ADD -- `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]`
 174    * `0x8*~5`: SUB -- `cpu.v[~]` into `cpu.v[*]`, underflow bit in `cpu.v[F]`
 175    * `0x8*-6`: SHR -- shift `cpu.v[*]` right, underflow bit in `cpu.v[F]`
 176    * `0x8*~7`: SUBN -- subtract `cpu.v[*]` from `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]`
 177    * `0x8*-8`: SHL -- shift `cpu.v[*]` left, overflow bit in `cpu.v[F]`
 178  * `0x9*~-`: SNE -- with two registers
 179  * `0xA***`: LD -- load `***` into memory address register
 180  * `0xB***`: JP -- set program counter to `***` plus `cpu.v[0]`
 181  * `0xC*~~`: RND -- generate random number, and with `~~`, and load the result into `cpu.v[*]`
 182  * `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.
 183  * `0xE---`: skips
 184    * `0xE*9E`: SKP -- if a key was pressed at time `cpu.v[*]`, jump over the next instruction
 185    * `0xE*A1`: SKNP -- like SKP, but negated
 186  * `0xF---`: compound
 187    * `0xF*07`: LD -- load DT into `cpu.v[*]`
 188    * `0xF-0A`: LD -- jump over as many instructions as keys were pressed.
 189    * `0xF*15`: LD -- load `cpu.v[*]` into DT
 190    * `0xF*18`: LD -- load `cpu.v[*]` into ST
 191    * `0xF*1E`: ADD -- Increment memory address register by `cpu.v[*]`
 192    * `0xF*29`: LD -- load `cpu.v[*] * 5` into memory address register
 193    * `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.
 194    * `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**)
 195    * `0xF*65`: LD -- Vector memory read. Read starting at the address stored in the memory address register, and write into the registers up to `*`.
 196    * `0xF-75`: Activate debug flag, i.e. call debug function pointer after draw
 197
 198
 199  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`.
 200
 201 Hence, it seems that the full intended exploit is:
 202
 203  * Fill the registers with the address of `highscore()`.
 204  * Use `0xF*55` (Vector memory write) to overwrite the debug function pointer with the registers' contents.
 205  * Use `0xF-75` to enable debug mode.
 206  * Clear the screen to force drawing using the `0x0-E0` instruction.
 207  * Debug function executes, calling `highscore()`. We have now exited the virtual CPU.
 208  * Use a ROP syscall with the name input to read the flag from the `flag` file.
 209
 210 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.
 211
 212 Also, the C++ hint from the comic in the challenge description was misleading.
 213
 214 ---
 215