CTF:GitS-2013/Writeups/RTFM

Ghost in the Shellcode: RTFM Writeup

RTFM which usually stands for "Read the fucking manual" was used here for "Rich text for Morons". The challenge supplied a executable x86 ELF file and a data file.

First thing was to figure out that the executable was used to generate the data file. The data file included the header "RTFM", which we also found to be written at an allocated memory in the disassembly. Inside this function we also found the code that actually converts the data.

We did some testing with different input data, and figured out the the output file size can be less or more than the input data. For a one byte input we got either one or 1.5 bytes output. A repeating byte in the input from the readable charset was often compressed to less than input size. A repeating 0x01 was always encoded to repeating 1.5 bytes. On 0x00 in the input the executable stopped its execution. Similiar things happened to bytes above 0x80. Actually here is the point to see that more common/used character(sequences) are encoded to less, which hints to a huffman compression.

Anyway we thought it is easier to use a different approach instead of reversing the huffman code including the tables. So we wrote a small application using bruteforce. We put a new byte to the input and then compare if it matches more bits on the output than any other input byte. We use that in a recursive functions to make sure, that it will also follow repeating bytes that get mapped to the same length as the input string one byte before.

Our none-error-tolerant code in not-best-coding-style: ...

During bruteforcing you see the current output. Excitement! The overhead of the "Rich Text Format" was more annoying than ever before ;-) The key "Did I have Vari-good-code?" is again a nice wordplay.

The process of decompressing using bruteforce took more than one hour. Most of the CPU power was used for system calls, since we did not copypaste the encryption routine.