From 4886754cd0d0b61c15133b24225fb4185d2a26c8 Mon Sep 17 00:00:00 2001 From: Philipp Nowak Date: Sun, 19 Jan 2020 15:35:32 +0100 Subject: [PATCH] Add writeup for OTW day 23: Gr8 Escape --- writeups/litplus/otw19.md | 212 +++++++++++++++++++++++++++- writeups/litplus/otw19/23-start.png | Bin 0 -> 5182 bytes writeups/litplus/otw19/A0Intro.md | 4 +- writeups/litplus/otw19/Adv-02.md | 2 +- writeups/litplus/otw19/Adv-23.md | 206 ++++++++++++++++++++++++++- 5 files changed, 416 insertions(+), 8 deletions(-) create mode 100644 writeups/litplus/otw19/23-start.png diff --git a/writeups/litplus/otw19.md b/writeups/litplus/otw19.md index 61c5148..f26d968 100644 --- a/writeups/litplus/otw19.md +++ b/writeups/litplus/otw19.md @@ -11,7 +11,7 @@ Challenges participated in: * day-24: Got shell? `solved` `web, linux` - 2.25 hours * day-25: Lost in Maze `solved` `misc` - 16.00 hours -Total time spent: 39.75 hours (+ 4 hours for writeups) -- More effort TBD +Total time spent: 39.75 hours (+ 6.5 hours for writeups) -- More effort TBD ### Personal Reflection 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`. @@ -23,6 +23,8 @@ Cooperation with other team members worked especially well with Suummer ADVENTur ### Note on Materials 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. +Thankfully, the organisers released source code for all challenges [on GitHub](https://github.com/OverTheWireOrg/advent2019), however most challenges do not have further explanation. + --- day-02 Summer ADVENTure @@ -33,7 +35,7 @@ Discussion on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/da Full exploit source code on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-02) -Time spent for this challenge: 20.75hours +Time spent for this challenge: 20.75hours + 4 hours write-up * December 10: 3.0 hours (21:00-00:00) * December 12: 3.0 hours (00:15-03:15) @@ -240,12 +242,214 @@ day-23 Gr8 Escape OverTheWire Advent 2019, day 23 -Time spent for this challenge: 0.75 hours +Statements on [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-23-gr8-escape) + +Time spent for this challenge: 0.75 hours + 2.5 hours write-up * December 24: 0.75 hours (05:30-06:15) -Writeup TBD +### Overview +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. + +![Elves make Christmas toys, comic](https://mattermost.w0y.at/files/kbyt9uw7opncfqy4tyo9x1ogmc/public?h=PAVYjFNKSNs8V0JSGrStUyv8hrM2ZSpGpK2yOZ0tCvM) + +A TCP service was provided at `nc 3.93.128.89 1223`. Upon connecting, it shows a banner and presents a prompt: + +![Gr8 Escape banner and "game:" prompt](otw19/23-start.png) + +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. + +### Exploitation + +`@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. + +The first thing I did was try to input a lot of `A`s into the application. Sometimes, it did this: + +![blank screen with some kind of frame](https://mattermost.w0y.at/files/dk7z9zmawi8m5mjts6rjga9s9h/public?h=F0IifdSufQcIDBTSH8iVcI2LhXfz6dMbI9PoJ08daVc) + +However, this was not always reproducible and also did not lead anywhere. + +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. + +The yielded a huge C++ file with huge unintelligible functions along the lines of this: + +``` + uint64_t rcx89; + void** rax90; + uint64_t rax91; + + rsp4 = reinterpret_cast(reinterpret_cast(__zero_stack_offset()) - 8 - 8 - 8 - 8 - 8 - 8 - 0x198); + v5 = rdi; + rax6 = g28; + v7 = rax6; + v8 = reinterpret_cast(reinterpret_cast(rsp4) + 15 & 0xfffffffffffffff0); + if (!rsi || (r13_9 = rsi, rbx10 = reinterpret_cast(reinterpret_cast(*reinterpret_cast(rsi)) & 0xfffffffffffffffe), rbx10 == 0)) { + addr_44d6f4_2: + *reinterpret_cast(&rbx10) = 0; + *reinterpret_cast(&rbx10 + 4) = 0; + } else { + r15_11 = rdx; + rax12 = rbx10; + *reinterpret_cast(&r14_13) = 0; + *reinterpret_cast(reinterpret_cast(&r14_13) + 4) = 0; + v14 = 40; + while (rsi15 = *reinterpret_cast(rax12), r12d16 = *reinterpret_cast(&r14_13), rsp17 = reinterpret_cast(reinterpret_cast(rsp4) - 8), *rsp17 = 0x44d6b5, eax18 = reinterpret_cast(r15_11(v5, rsi15, rdx)), rsp4 = reinterpret_cast(rsp17 + 1), r10d19 = eax18, !!eax18) { + rbx20 = reinterpret_cast(r14_13 * 8); + if (v14 == *reinterpret_cast(&r14_13)) { + v14 = v14 + 20; + rdx = rbx20; +``` + +To make matters more interesting, the program also includes numerous blocks of raw assembly instructions like this: +``` + if (*reinterpret_cast(&rcx6) <= 48 && *reinterpret_cast(&rax7) <= 48) { + __asm__("movlpd xmm1, [rdi]"); + __asm__("movlpd xmm2, [rsi]"); + __asm__("movhpd xmm1, [rdi+0x8]"); + __asm__("movhpd xmm2, [rsi+0x8]"); + __asm__("pxor xmm0, xmm0"); + __asm__("pcmpeqb xmm0, xmm1"); + __asm__("pcmpeqb xmm1, xmm2"); + __asm__("psubb xmm1, xmm0"); + __asm__("pmovmskb edx, xmm1"); + if (*reinterpret_cast(&rdx) - 0xffff) + goto 0x42b010; + if (rdx <= 16) + goto 0x42b024; + } +``` + +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. + +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: + +``` +uint32_t fun_40208d(void** rdi, void** rsi, void** rdx, void** rcx, void** r8, void** r9, int64_t a7) { + void** rax8; + void** v9; + void** rax10; + int32_t v11; + int32_t v12; + uint32_t ecx13; + uint32_t eax14; + + rax8 = fun_421e80(0x1000); + v9 = rax8; + if (v9) { + fun_4117a0("game: ", rsi, rdx, rcx, r8, r9); + rax10 = fun_44bf60(0, v9, 0xe00, rcx, r8); + v11 = *reinterpret_cast(&rax10); + if (v11 > 0) { + if (v11 <= 0xe00) { + v12 = 0; + while (v12 < v11) { + ecx13 = *reinterpret_cast(reinterpret_cast(v9) + reinterpret_cast(static_cast(v12))); + *reinterpret_cast(v12 + 0x200 + 0x6dbd4a) = *reinterpret_cast(&ecx13); + ++v12; + } + eax14 = 1; + } else { + eax14 = 0; + } + } else { + eax14 = 0; + } + } else { + eax14 = 0; + } + return eax14; +} +``` + +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. + +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. + +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. + +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. + +### Intended solution +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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)) + + * `0x0---`: compound + * `0x0-00`: SYS -- does nothing + * `0x0-E0`: CLS -- clear screen and draw + * `0x0-EE`: RET -- decrement stack pointer, jump to previous location. + * `0x1***`: JP -- set program counter to `***`. + * `0x2***`: CALL -- push current address to stack, jump to `***` + * `0x3*~~`: SE -- if `cpu.v[*]` is `~~`, `pc+=4`, otherwise `pc+=2` (conditional) + * `0x4*~~`: SNE -- same as SE but with not-equal + * `0x5*~-`: SE -- compares `cpu.v[*]` to `cpu.v[~]`, otherwise like SE + * `0x6*~~`: LD -- loads constant `~~` to `cpu.v[*]` + * `0x7*~~`: ADD -- Adds `~~` to `cpu.v[*]`, overflow bit in `cpu.v[F]`. + * `0x8---`: register operations + * `0x8*~0`: LD -- from `cpu.v[~]` into `cpu.v[*]` + * `0x8*~1`: OR -- `cpu.v[~]` into `cpu.v[*]` + * `0x8*~2`: AND -- `cpu.v[~]` into `cpu.v[*]` + * `0x8*~3`: XOR -- `cpu.v[~]` into `cpu.v[*]` + * `0x8*~4`: ADD -- `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]` + * `0x8*~5`: SUB -- `cpu.v[~]` into `cpu.v[*]`, underflow bit in `cpu.v[F]` + * `0x8*-6`: SHR -- shift `cpu.v[*]` right, underflow bit in `cpu.v[F]` + * `0x8*~7`: SUBN -- subtract `cpu.v[*]` from `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]` + * `0x8*-8`: SHL -- shift `cpu.v[*]` left, overflow bit in `cpu.v[F]` + * `0x9*~-`: SNE -- with two registers + * `0xA***`: LD -- load `***` into memory address register + * `0xB***`: JP -- set program counter to `***` plus `cpu.v[0]` + * `0xC*~~`: RND -- generate random number, and with `~~`, and load the result into `cpu.v[*]` + * `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. + * `0xE---`: skips + * `0xE*9E`: SKP -- if a key was pressed at time `cpu.v[*]`, jump over the next instruction + * `0xE*A1`: SKNP -- like SKP, but negated + * `0xF---`: compound + * `0xF*07`: LD -- load DT into `cpu.v[*]` + * `0xF-0A`: LD -- jump over as many instructions as keys were pressed. + * `0xF*15`: LD -- load `cpu.v[*]` into DT + * `0xF*18`: LD -- load `cpu.v[*]` into ST + * `0xF*1E`: ADD -- Increment memory address register by `cpu.v[*]` + * `0xF*29`: LD -- load `cpu.v[*] * 5` into memory address register + * `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. + * `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**) + * `0xF*65`: LD -- Vector memory read. Read starting at the address stored in the memory address register, and write into the registers up to `*`. + * `0xF-75`: Activate debug flag, i.e. call debug function pointer after draw + + + 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`. + +Hence, it seems that the full intended exploit is: + + * Fill the registers with the address of `highscore()`. + * Use `0xF*55` (Vector memory write) to overwrite the debug function pointer with the registers' contents. + * Use `0xF-75` to enable debug mode. + * Clear the screen to force drawing using the `0x0-E0` instruction. + * Debug function executes, calling `highscore()`. We have now exited the virtual CPU. + * Use a ROP syscall with the name input to read the flag from the `flag` file. + +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. + +Also, the C++ hint from the comic in the challenge description was misleading. + --- day-24 Got shell? diff --git a/writeups/litplus/otw19/23-start.png b/writeups/litplus/otw19/23-start.png new file mode 100644 index 0000000000000000000000000000000000000000..967aba9e54331669c487a7da782cae98e1a40545 GIT binary patch literal 5182 zcmd5=X*iVa-^OE2NoA{qR*@xCLd+DUD6&jMW@3_3wkBI6TmQ;f>)({JjmS1KgUTd~ zE#t{H$=Z;yWXY1<41;;E`+h#WpWYA8arEJx4>Q+s&9(fN^LL)V`zBnpGT*de#|8lb zflcSmn%N2n2-3lLKwK1j)AoD~13$vJQ|Ii(!6!ugT9kmmw#9R1C+&mKQ$O%e(C+ue zX4u|a2O}Sx6F*7RRmdeEg=$o2t?}Uj0ygb}o1R-r(1bL1ylIhEur+)=wK1w~qtMf< zA|jR^g?d)i0RnkC15#Tz?vva1&9_lOSTpbW?Go2*D!0)~C-6&?!R*mV)vzKDQseaU zY73ohAffszsa5ZT_UayFxPYKgrdc|kn9`;rA+3T8M^=XS?BJ?H_-p)aDY;^6!lj-foBmBLXrP=!)3zR5H!Rjudy8Vz-Hz?u#x4eB)V5vLHsmECr_FPT~IHHZQS4Owj}BOPKYtd{~^JSQg|63nq)gaKj(Q1kCL zM6Anq=dXO=yjetPqIwKb9p$%wM6*2ObD0L_q*pyw)FSyhXOz2Rxg9IYaJqwtwjZ_| zEwv35^_bFEd%e3(o6AIGaJ5BCmj@Cza6HM@1J%wOXFmU_I7U)MqAlTAUjfPK?K9jC zTo!*Xox32iv{Q>aBT|IGphjqxSf0aM7ncjw5Q+VmTN?&q(4O&Ke=&HNY27)&0Chvl{kA!dJHBAVE7T zh5;2A5-Ti>!8-j?fy{WaM}=!kjNJ|4n*m_Kc>nDrm`19cM$Tj%+-?eGCvJ;$NZie= z2k_?T@P11h-A7QScI*Yk(PkkAZORB3!(Qgc#NTEb7sgx-|;}$A*}W=8F1GnXS#qdIi4cEvyraGLu5HCQ*(v z48aR)u@(lrDxI`HR*(Nz0e?N3>EX$)igB-`d;B7}=g__Ssvq|{elb*w$qn|+B8P~w zv(~3OgA=BXR&cX^O;8Y(q5pCH9mL9WkfA)8D-J<{3>X)@!>AqYx@_%gdPwnN$C_RC zKI;(o_9i$!w?Uni6xbby(oF;b{WJ3rY>4ujcG2g9e;svCCF*!8UCC1?RR`wr%l!MW zYB`OqrRufh7BtG(e<`1wl&^c<0FT0w4e_t;otS-YqxTp}WHBI(?e7hbrH2xX@YGO(5AOt$$ zali@wo;@+pn5Ct{W%UV(zz9qQTy5orhuNzKM775`UErT9kTV^5UfR(3Mj44qPsPD96f$xDZL`9ugo7*DqntaivLses2*;M6J2i_mT2?P@CA@%9pVX#Cy< zaAJkX22eNx5r*Kp|8*kvLcvv_Jvma%p1nzu9w=L%coS5rvB(qa=x_bl@gsMAHul93 zr!ToXda&(UP#rJHAr0+A1Zr%O0p#tIg7E&v68{aV(8;>s`ad)8qIWNQDeHX7{jOTI z+70!+_$94}*m1?ekUC<`)SVN&lk6)lK@^}kQaw~(1=6XE8bQ={IdA)ca3X%Mdl|sW zs7DNmN^FrbIWYV#a7MNvtZN%4*hmj%ZBxM7u5HBgP%MW*H2%!|fB7OywTO@Rmt9I; zmL42t|sriiidIL0B|=50&54!Jf6mn*m zW#A7Rs0QHsN9H3a+l}pbw%0=!Q~HRm53$~rIIn@1WYPBJnrU=fmpv+A|Ab;NSL*p& z+%gKgp(}5^@9g*d!k3=~f#i3f3FZ^Iu25%{)53fq^OI~6c4r}Pd{V8&oe?y6DDyhZ z0M|f2QS6mk1GihT;r)MR9ywQ8720p|tnqDSM+#BiiI&tpBFQiIbvq?ehmAKH(wCU9 z*Spr2GI;M>fI6j=jNh9PM17wWW8QHY2l^}CO2gm-)DgG7l$){z_PuT7kUOil&z&53 zmT}}gP@P93?nfXFxCZD)*C%}rvi<4}&;{N=pMf(lA{41TFRD(0u=D7E%D>(4WL1c# zg%9(*aj3F(4F7^&tIxW-+;8fw(Q7bVHvox@Z>p6M?`96##u4|KSfdjns!AUB@K}x> zOsp28?prHEbtu}b&Z9=rzl2itiq%P0yw!8dle_Y?f(Cc0U7mpYYNR=!zxdlR84%4~ zeFHk~vtOJNA&U)dku(0+oMm8Q+`C_ed&Z*k6I>rp0rdCwWE_MbrvPB4Z(H2CAEK#v zK+3zm%bkXbqUx-~-R7}Zti)n20Lhz;jowXjvUS=waun6gN#vFm58nv#?>I%?b6X(# z4+6_s)0c+ryim0m&EY>j32~9Elc6 z zqy4DxjfFM!tD>NFNb|3(XRzOqpkqVo{s;0d33O~pZI-HVMT&*9FbDSG_Xs9d!p}4ucSXU{?`{wFIf;{89`S~bH^XL?7 z_V15B=_JM=h8jz%m~&j^KHWK#@ytY~$6M*}b+#S0`hg|(7ps2o_hb65#4Ew5-noU$ zqMw9hw-(ZG1t0HDW1S`ATcKC*>_NxkfM5-DsAUr(kpFUqamI%ma3LD8%j4a4Te7uJcu#oR>V0KNUErTv_6Af>#hTRF1WZo?oA1yZs1Nj!8I==Ojn8 zaps2nc!(=97=!V7zZz90K_rHjkSVVb_0B|>Qu$lQXnMPH-+liO&O1!B<#eb|$jBSD z*=KDY_3nYzgl$>~&Fc%BCkWedmD{?SQswgH(2AoWb3Z@+{B*R4nI(x`|1ym~q=->A z44@tFk1`%K-j>aHt=yx@XfMDb;3%db`I3_^M!RHlTKY88)>n#jI1REz>x(f%s&%9H ztYg18D=mM()UDCh$D0o&AdZg{dn5(%a{{;vU`0^%L`rS z<)~{K^!p?1&wQm$Sq_@_clM`}xAkFA2?#{&-moCX?ylg(ZH^1u?OitUD!4s%OEBHXOP0 zL1BKN|7t&z8MRY6Y^c?{Eu4-hS7dS!-YYPz3755!yo5tJ%cb>hU$im1B8NW(UF#$GvBJU( z)(02b1_$j9m@^-->tZTDBD@{%wDojdu2felAIjrS&bkyWsOG!j_M3J$UW7_OWhMY_ zGMv||(Hx3ueTF$R;lsPl@zg#;;?)U7H@=3==)$S}VC9%hL^EHB&F!9-#6;h$Gx`2^(pg?UNYF zKt?Ov1j_fVrW0<^ 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. + +The yielded a huge C++ file with huge unintelligible functions along the lines of this: + +``` + uint64_t rcx89; + void** rax90; + uint64_t rax91; + + rsp4 = reinterpret_cast(reinterpret_cast(__zero_stack_offset()) - 8 - 8 - 8 - 8 - 8 - 8 - 0x198); + v5 = rdi; + rax6 = g28; + v7 = rax6; + v8 = reinterpret_cast(reinterpret_cast(rsp4) + 15 & 0xfffffffffffffff0); + if (!rsi || (r13_9 = rsi, rbx10 = reinterpret_cast(reinterpret_cast(*reinterpret_cast(rsi)) & 0xfffffffffffffffe), rbx10 == 0)) { + addr_44d6f4_2: + *reinterpret_cast(&rbx10) = 0; + *reinterpret_cast(&rbx10 + 4) = 0; + } else { + r15_11 = rdx; + rax12 = rbx10; + *reinterpret_cast(&r14_13) = 0; + *reinterpret_cast(reinterpret_cast(&r14_13) + 4) = 0; + v14 = 40; + while (rsi15 = *reinterpret_cast(rax12), r12d16 = *reinterpret_cast(&r14_13), rsp17 = reinterpret_cast(reinterpret_cast(rsp4) - 8), *rsp17 = 0x44d6b5, eax18 = reinterpret_cast(r15_11(v5, rsi15, rdx)), rsp4 = reinterpret_cast(rsp17 + 1), r10d19 = eax18, !!eax18) { + rbx20 = reinterpret_cast(r14_13 * 8); + if (v14 == *reinterpret_cast(&r14_13)) { + v14 = v14 + 20; + rdx = rbx20; +``` + +To make matters more interesting, the program also includes numerous blocks of raw assembly instructions like this: + +``` + if (*reinterpret_cast(&rcx6) <= 48 && *reinterpret_cast(&rax7) <= 48) { + __asm__("movlpd xmm1, [rdi]"); + __asm__("movlpd xmm2, [rsi]"); + __asm__("movhpd xmm1, [rdi+0x8]"); + __asm__("movhpd xmm2, [rsi+0x8]"); + __asm__("pxor xmm0, xmm0"); + __asm__("pcmpeqb xmm0, xmm1"); + __asm__("pcmpeqb xmm1, xmm2"); + __asm__("psubb xmm1, xmm0"); + __asm__("pmovmskb edx, xmm1"); + if (*reinterpret_cast(&rdx) - 0xffff) + goto 0x42b010; + if (rdx <= 16) + goto 0x42b024; + } +``` + +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. + +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: + +``` +uint32_t fun_40208d(void** rdi, void** rsi, void** rdx, void** rcx, void** r8, void** r9, int64_t a7) { + void** rax8; + void** v9; + void** rax10; + int32_t v11; + int32_t v12; + uint32_t ecx13; + uint32_t eax14; + + rax8 = fun_421e80(0x1000); + v9 = rax8; + if (v9) { + fun_4117a0("game: ", rsi, rdx, rcx, r8, r9); + rax10 = fun_44bf60(0, v9, 0xe00, rcx, r8); + v11 = *reinterpret_cast(&rax10); + if (v11 > 0) { + if (v11 <= 0xe00) { + v12 = 0; + while (v12 < v11) { + ecx13 = *reinterpret_cast(reinterpret_cast(v9) + reinterpret_cast(static_cast(v12))); + *reinterpret_cast(v12 + 0x200 + 0x6dbd4a) = *reinterpret_cast(&ecx13); + ++v12; + } + eax14 = 1; + } else { + eax14 = 0; + } + } else { + eax14 = 0; + } + } else { + eax14 = 0; + } + return eax14; +} +``` + +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. + +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. + +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. + +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. + +### Intended solution +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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. + +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)) + + * `0x0---`: compound + * `0x0-00`: SYS -- does nothing + * `0x0-E0`: CLS -- clear screen and draw + * `0x0-EE`: RET -- decrement stack pointer, jump to previous location. + * `0x1***`: JP -- set program counter to `***`. + * `0x2***`: CALL -- push current address to stack, jump to `***` + * `0x3*~~`: SE -- if `cpu.v[*]` is `~~`, `pc+=4`, otherwise `pc+=2` (conditional) + * `0x4*~~`: SNE -- same as SE but with not-equal + * `0x5*~-`: SE -- compares `cpu.v[*]` to `cpu.v[~]`, otherwise like SE + * `0x6*~~`: LD -- loads constant `~~` to `cpu.v[*]` + * `0x7*~~`: ADD -- Adds `~~` to `cpu.v[*]`, overflow bit in `cpu.v[F]`. + * `0x8---`: register operations + * `0x8*~0`: LD -- from `cpu.v[~]` into `cpu.v[*]` + * `0x8*~1`: OR -- `cpu.v[~]` into `cpu.v[*]` + * `0x8*~2`: AND -- `cpu.v[~]` into `cpu.v[*]` + * `0x8*~3`: XOR -- `cpu.v[~]` into `cpu.v[*]` + * `0x8*~4`: ADD -- `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]` + * `0x8*~5`: SUB -- `cpu.v[~]` into `cpu.v[*]`, underflow bit in `cpu.v[F]` + * `0x8*-6`: SHR -- shift `cpu.v[*]` right, underflow bit in `cpu.v[F]` + * `0x8*~7`: SUBN -- subtract `cpu.v[*]` from `cpu.v[~]` into `cpu.v[*]`, overflow bit in `cpu.v[F]` + * `0x8*-8`: SHL -- shift `cpu.v[*]` left, overflow bit in `cpu.v[F]` + * `0x9*~-`: SNE -- with two registers + * `0xA***`: LD -- load `***` into memory address register + * `0xB***`: JP -- set program counter to `***` plus `cpu.v[0]` + * `0xC*~~`: RND -- generate random number, and with `~~`, and load the result into `cpu.v[*]` + * `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. + * `0xE---`: skips + * `0xE*9E`: SKP -- if a key was pressed at time `cpu.v[*]`, jump over the next instruction + * `0xE*A1`: SKNP -- like SKP, but negated + * `0xF---`: compound + * `0xF*07`: LD -- load DT into `cpu.v[*]` + * `0xF-0A`: LD -- jump over as many instructions as keys were pressed. + * `0xF*15`: LD -- load `cpu.v[*]` into DT + * `0xF*18`: LD -- load `cpu.v[*]` into ST + * `0xF*1E`: ADD -- Increment memory address register by `cpu.v[*]` + * `0xF*29`: LD -- load `cpu.v[*] * 5` into memory address register + * `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. + * `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**) + * `0xF*65`: LD -- Vector memory read. Read starting at the address stored in the memory address register, and write into the registers up to `*`. + * `0xF-75`: Activate debug flag, i.e. call debug function pointer after draw + + + 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`. + +Hence, it seems that the full intended exploit is: + + * Fill the registers with the address of `highscore()`. + * Use `0xF*55` (Vector memory write) to overwrite the debug function pointer with the registers' contents. + * Use `0xF-75` to enable debug mode. + * Clear the screen to force drawing using the `0x0-E0` instruction. + * Debug function executes, calling `highscore()`. We have now exited the virtual CPU. + * Use a ROP syscall with the name input to read the flag from the `flag` file. + +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. +Also, the C++ hint from the comic in the challenge description was misleading. + --- -- 2.43.0