# Challenge
* CTF: hxp 2017* Name: wreckme* Team: Top of the ROP* Points: 100 + variable points* Tags: rev baby misc
# Problem
Challenge binary (called "pain") is a 64-bit ELF executable. Running either `strings` or `ldd` on it shows that it is a Haskell dynamically linked program:
```bash$ ldd pain linux-vdso.so.1 =>  (0x00007ffd19381000)libHSbase-4.10.0.0-ghc8.2.1.so => not foundlibHSinteger-gmp-1.0.1.0-ghc8.2.1.so => not foundlibHSghc-prim-0.5.1.0-ghc8.2.1.so => not foundlibHSrts-ghc8.2.1.so => not foundlibgmp.so.10 => /usr/lib/x86_64-linux-gnu/libgmp.so.10 (0x00007fe8f6a7c000)libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007fe8f6773000)librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007fe8f656b000)libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007fe8f6367000)libffi.so.6 => /usr/lib/x86_64-linux-gnu/libffi.so.6 (0x00007fe8f615f000)libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fe8f5f42000)libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fe8f5b78000)/lib64/ld-linux-x86-64.so.2 (0x00007fe8f6cfc000)```
The missing shared objects are part of the GHC 8.2.1 runtime.
Since it is dynamically linked, `strings` (or, in this case, also `readelf --syms`) gives it away as a Haskell program via imports of e.g. `hs_main`, and all those `base_GHC*` functions.
There is no remote service for this challenge, so it is very likely that the flag is embedded in the binary. Thus, the "rev" tag. (Whether the "baby" tag is justified depends entirely on ones experience reversing Haskell binaries, I guess :-)
# Solution
There are at least two ways to solve this challenge: Monkey patching the binary to give the flag (quickest), or static reversal of all the relevant parts of the program. Here I will show the first one. It is properly also possible to solve this challenge without any Haskell knowledge at all, but I can't tell you how, because I don't know any techniques that are as quick to implement as the one I will show below.
First order of business is to get the program to actually run. Seeing as hxp later released a statically linked version of the program, I guess the missing GHC runtime shared objects posed a problem to quite a few teams during the CTF. Basically, you just need to install GHC 8.2.1 on your system and the libraries will follow. A quick hack is to get the GHC 8.2.1 distribution and simple extract the missing libraries, put them in your working directory and execute the binary with:
```bash$ LD_LIBRARY_PATH=`pwd` ./painhxp{not da flag}```
## Reversing Haskell Code
This will be more detailed than a "standard" write-up, since I wan't to use this opportunity to give a short introduction to "baby" Haskell reversing. It will not be a full tutorial on reversing Haskell code, nor on Haskell itself. Specifically, I will assume the reader to well versed in Haskell already.
There is actually excellent documentation on the GHC implementation of Haskell, both in terms of academic papers and actual implementation documentation (albeits parts of the GHC wiki are a bit outdated). Also the GHC source code is really nice. However, for this write-up to be of some minimal value to beginners, we have to learn a little bit about Haskell programs. The core concepts to grasp are:
* Haskell programs are executed in an abstract machine called the Spineless Tagless G-machine (or STG for short): [Commentary/Rts/HaskellExecution](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution)* GHC compiled binaries are a mix of "normal" C code (mostly the Runtime System, called RTS) and compiled Haskell functions (both the user-specified ones and RTS functions) (GHC compiles through multiple stages of intermediate languages that are not important here).* Haskell functions don't use any of the "normal" calling conventions. Haskell functions have a stack and a heap (and corresponding SP/HP pointers) that are separate from the "standard" program ones. The STG registers are mapped by GHC during compilation to machine registers. The mapping can be seen here: [stg/MachRegs.h](https://ghc.haskell.org/trac/ghc/browser/ghc/includes/stg/MachRegs.h#L158)* Most (all?) Haskell objects (functions, values, etc.) are represented using a single indirection as described in [Commentary/Rts/Storage](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects). Thus, in the code, a value is a pointer to an instance of one of a set of pre-defined `StgClosure` structs, which in turn usually contains a pointer to the actual code as the first qword. (Actually, the pointer is a pointer to the "info table" in STG lingo which describes the closure; as a compile-time optimization, the info table is usually compiled next to the actual function code saving another pointer to the code.)
* Roughly speaking, the STG evaluates such objects (closures) if and when they are needed. Evaluation happens by setting up the required arguments and jumping (literally a `jmp` instruction) to the code suitable for evaluating the closure.
* The GHC wiki is full of good documentation. Another good resource is [Debugging/CompiledCode](https://ghc.haskell.org/trac/ghc/wiki/Debugging/CompiledCode)
* Learn more about the STG execution model with this awesome tool: [STGi](https://github.com/quchen/stgi)
## In Practice - Baby Steps
Phew, how theoretical! Let's dive into the actual reversing and figure out what this program does.
Usually this means firing up IDA, or BinaryNinja (or for some hardcore oldies, `objdump`). All these tools have the necessary features to get the job done. However, loading the binary in any of these tools reveals a depressing sight: very few functions, and almost none of the interesting ones, show up in auto-analysis. Very few reversing tools (actually, none that I know of) are familiar with GHC's conventions for Haskell code. Luckily most of them can by default tell you where the `main` function is and what it's instructions are. At least a starting point.
We see that the challenge program's `main` does a lot of initial stuff (that are not that interesting in this case), and then calls the imported function `hs_main` (using a standard amd64 calling convention):
```.text:4026DA   lea     rdx, off_4041A0.text:4026E1   mov     rsi, rcx.text:4026E4   mov     edi, eax.text:4026E6   call    _hs_main```
This function, found in [rts/RtsMain.c](https://ghc.haskell.org/trac/ghc/browser/rts/RtsMain.c), actually kicks off Haskell execution (eventually):
```C// The rts entry point from a compiled program using a Haskell main// function.  This gets called from a tiny main function generated by// GHC and linked into each compiled Haskell program that uses a// Haskell main function.//// We expect the caller to pass ZCMain_main_closure for// main_closure. The reason we cannot refer to this symbol directly// is because we're inside the rts and we do not know for sure that// we'll be using a Haskell main function.//// NOTE: This function is marked as _noreturn_ in Main.h
int hs_main ( int argc, char *argv[],       // program args              StgClosure *main_closure,     // closure for Main.main              RtsConfig rts_config)         // RTS configuration
{    ...```
Aha! So, the third argument to `hs_main` is actually a pointer to a `StgClosure` - most likely the actual Haskell entrypoint function, i.e. `main` in something like:
```Haskellmodule Main where
main :: IO ()main = ...```
This means that the structure @ `0x4041a0` must be a closure, and that the first qword in this structure will point to the actual code defining `Main.main`. Indeed it does contain a value that could be a pointer to a function:
```.data:4041A0 off_4041A0      dq offset sub_4025D0    ; DATA XREF: main+B7?o.data:4041A8                 align 20h```
In this case, IDA has already recognized this location as a function pointer. Going deeper into the tree of closures, even IDA has to give up automatically recognizing all the functions. Also, my version of BinaryNinja did not even recognize `0x4025d0` as the location of a function. Understandably so, since there are no actual `call`s to these locations.
So, whenever we come across such a `StgClosure`, we must manually tell our tool of choice that there actually is a function at the location of the corresponding info table (pointed to by the closure).
Forcing a function definition, if need be, at address `0x4025d0` reveals this code:
```sub_4025D0 proc nearlea     rax, [rbp-10h]cmp     rax, r15jb      short loc_40261F          /\  .------'  `------------.  V                      Vsub     rsp, 8          loc_40261F:mov     rax, r13        jmp     qword ptr [r13-10h]mov     rsi, rbx        sub_4025D0 endpmov     rdi, raxxor     eax, eaxcall    _newCAFadd     rsp, 8test    rax, raxjz      short loc_40261D          /\  .------'  `----------------------------------------------------.  V                                                              |mov     rbx, cs:stg_bh_upd_frame_info_ptr                        |mov     [rbp-10h], rbx                                           |mov     [rbp-8], rax                                             |lea     r14, off_404180                                          |mov     rbx, cs:base_GHCziTopHandler_runMainIO_closure_ptr       |add     rbp, 0FFFFFFFFFFFFFFF0h                                  |jmp     cs:stg_ap_p_fast_ptr                                     |                                                                 V                                                                loc_40261D:                                                                jmp     qword ptr [rbx]```
This is actually quite a common template for Haskell code. We can ignore all the blocks except the lower left one (ending in a `jmp cs:stg_ap_p_fast_ptr` instruction), as these relate to various runtime subsystems (heap allocation failures, etc).
So what does this function do? Well, it ends with an unconditional jump to `stg_ap_p_fast_ptr`. This function is one of many pre-compiled runtime functions that implement function application in the STG. So basically, it means "[in the] stg, ap[ply] [first argument (that must be a pointer to a function closure type) to a value passed as a] p[ointer]" (this is properly to simplified a description to STG purists, but it works for us, now).
What, then, is the function being applied, and what is the argument? Again referring to `MachRegs.h`, we learn that `rbx` is `R1` and `r14` is `R2` meaning that `base_GHCziTopHandler_runMainIO_closure_ptr` is applied to `off_404180` (which we can then infer must be another closure pointer of some type). And that's really all there is to it! Now you know enough Haskell reversing to solve this challenge.
(Side note: Before making the `jmp`, the code sets up some values on the Haskell stack (`rbp` is the STG `SP` pointer) which is what makes the STG work properly without the return address also pushed to the stack. This is what's called continuation frames, I think, and in essence, the `stg_ap_*` family pops from the stack to determine what to do next).
## Mapping Out Program
As we saw above, having all the symbols to the library functions helps a lot in reversing Haskell code, as a lot of user code will call into built-in functions. By the way, GHC uses something called Z-encoding to encode symbol names with special characters, see [compiler/utils/Encoding.h](https://ghc.haskell.org/trac/ghc/browser/ghc/compiler/utils/Encoding.hs) to learn how to decipher it.
What remains is to find the closures in the program that are user-defined and not just standard runtime functions. Going to the address we uncovered above and extracting yet another indirect function pointer leads to `0x402550`:
```0x402576:mov     rbx, cs:stg_bh_upd_frame_info_ptrmov     [rbp-10h], rbxmov     [rbp-8], raxlea     rdi, off_404140lea     rsi, off_404160mov     r14, cs:base_SystemziIO_putStrLn_closure_ptrmov     rbx, cs:base_GHCziBase_zi_closure_ptradd     rbp, 0FFFFFFFFFFFFFFF0hjmp     cs:stg_ap_ppp_fast_ptr```
This is the body of the Haskell program's `main :: IO` function. Let's consider what Haskell code might have lead to this compilation. Decoding the named symbols and re-constructing the arguments according to the `stg_ap_ppp_fast_ptr` jump target results in:
```Haskellimport GHC.Base((.))import System.IO (putStrLn)
val_404160 :: Stringval_404160 = ...
val_404140 :: Stringval_404140 = ...
main :: IO ()main = (.) putStrLn val_404160 val_404140```
We know that the program prints the string `hxp{not da flag}` when run, so let's first see if we can determine how that came to be. Of course, `putStrLn :: String -> IO()` is responsible for putting the string to stdout. Examining first the closure @ `0x404160`, we can pretty quickly (just a couple of nested functions) reverse that into the following Haskell:
```Haskellval_404160 :: b -> Stringval_404160 = const "hxp{not da flag}"```
So this value is actually a function value, that takes a single argument which it discards, before returning a string literal: `hxp{not da flag}`. Looking closer at the other closure - the one that no function in the program really cares about - reveils something a little more interesting:
```Haskellval_4040c0 :: Stringval_4040c0 = ...
val_404140 :: Stringval_404140 = concat ["hxp{", val_4040c0, "}"]```
In Haskell, list literals are syntactic sugar for a sequence of applications of the cons constructor (`(:)`, e.g. `1:2:[]` is de-sugared version of `[1,2]`). Looking at how the list literal is compiled teaches a lot about how Haskell closures and evaluation works. In this case, the info table pointer of the closure corresponding to the list literal points to the `(:)` operator and has two value (closure) pointers as "payload", i.e. in this case the two arguments to the constructor: the head and the tail values. The tail value is another closure with the `(:)` constructor and a head and a tail, and so on, until you reach the `[]` constructor which is the empty list.
While an interesting challenge, we don't really need to go into this much detail about reversing the Haskell value @ `0x404140`. Assuming that this value holds the real flag, our job is to force evaluation of the closure and dump the resulting value (as opposed to the `const` function discarding it). Expressed in Haskell, we need a different `main`:
```Haskellval_404140 :: Stringval_404140 = concat ["hxp{", val_4040c0, "}"]
main :: IO ()main = putStrLn val_404140``` 
How would that look in compiled Haskell? Well, compile it and see:
```Bash$ cat Main.hsflag = "placeHolder"main = putStrLn flag
$ /opt/ghc/8.2.1/bin/ghc -o Main Main.hs [1 of 1] Compiling Main             ( Main.hs, Main.o )Linking Main ...```
Decompile the `Main_main_info` function, and extract the code. Changing the closure offset to fit with the challenge program yields this snippet:
```mov     rbx, cs:stg_bh_upd_frame_info_ptrmov     [rbp-10h], rbxmov     [rbp-8], raxmov     r14d, offset off_404140mov     rbx, ds:base_SystemziIO_putStrLn_closure_ptradd     rbp, 0FFFFFFFFFFFFFFF0hjmp     ds:stg_ap_p_fast_ptr```
Patch that into the main closure code (overwriting the current code @ `0x402576`), run the binary and see the flag appear :-)
```bash$ LD_LIBRARY_PATH=`pwd` ./patched_painhxp{HASSASINHASKELL}```