hxp


BkPCTF 2013 - elbisrever (300)

After having finished the randomness solver, I decided that sleeping several hours would probably a good idea. (We’re based in Germany, where the CTF started at local time 11 pm.) When I got up again, several new reversing challenges had been published, amongst them elbisrever (it took me several hours to realize that the name is a pun btw …)

Now the standard procedure for any unknown file:

$> file randy
elbisrever: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, BuildID[sha1]=0xa07c38b37cd6059f1eccd431d7382494bd7b5d17, stripped

Hm … statically linked might result into problems, as we won’t recognize library functions. Let’s see what IDA has to say:

elbisrever

Whoa! “Statically linked” is a clear understatement. The binary consists of less than five percent executable code and a huge dataset. This clearly has been produced using hand-written assembler codes.

Immediately, we can spot two nested loops: The inner one between the blocks loc_40019E and loc_400190 (if you look close enough, you can spot the circle in the graph, there are no edges that bypass the second block when you start at the first block. The outer loop is from block loc_400164 to block loc_400156.

Additionally, we recognize another problem: The binary provides no means of input. It just deterministically spits out That was not the flag. and exits. Our best bet is to guess that the long hard-coded binary strings (I labeled them src1 and src2) should be patched such that the last check is true.

After taking a deep breath, let’s try to figure out what is happening here. The outer block obviously consumes the data in a block-wise pattern: The purpose of block loc_400164 is to copy 0x20 bytes of src1 into the workbuffer and then to append 0x20 bytes of the src2 binary string to the workbuffer.

The inner loop consumes what I will refer to as the opcodetable. It reads in each of the three-bytes opcodes which all are in the format (All offsets are relative to the beginning of the workbuffer)

(read_offset1, read_offset2, write_offset)

and compares if the bytes at read_offset1 and read_offset2 both are equal to 0x31 (ASCII for a one). If this is the case, it XORs the byte at write_offset with 0x01 (switches between 0x30 or 0x31). This is done until the whole list of opcodes is executed. Afterwards the outer loop loads the next datablock.

Alright. Even though we were pretty sure that there is an easy way to simplify the opcode table (which consists of 7072 of the mentioned triples, btw) I decided to recreate the whole program, but in reverse direction. To do this, we needed several ingredients.

Using gdb, I dumped the opcodetable from memory to a file and hexdump was so kind to convert it to a C array. The result is placed in opcodes.h.

The src1 and src2 strings were also ripped from the binary and are placed in the program as arrays called input1 and input2, respectively.

The correctResult buffer, also ripped from the binary, is placed in correct.

And, last but not least, the state of the workbuffer after executing both loops with the wrong input is used to initialize the final buffer. (Remember, we want to go from the last compare backwards to the input strings?)

Another brave assumption (or rather an observation during reversing) was that everything in the workbuffer except for the first 0x20 bytes stays constant across all invokes of the outer loop. (Which seems to be the case) In other words: It means that the src2 binary string is nothing more than a (somewhat constant) key which is used to process src1.

Thus, the final computation including a reinterpretation of the binary strings to ASCII format looks like this:

(opcodes.h is here)

#include <stdio.h>
#include <unistd.h>
#include "opcodes.h"

#define TOBIN(X) (X - 0x30)

char *input1 = 
    "01101001011100110101111101110100"
    "01101000011010010111001101011111"
    "01110100011010000110010101011111"
    "01100110011011000110000101100111";

char *input2 =
    "10010010000011000111111111000011"
    "10000101010010101111100110111001"
    "01101011001011110001111110100111"
    "00010101101010110111100110011011";

char *correct = 
    "11101101110010111111001000010101"
    "01111100101100101010101100011001"
    "11100001101100011010101001000111"
    "00000110110101110010010010011111";

char final[256] = {
    0x31, 0x31, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x31, 0x31, 0x31, 0x30, 0x31, 0x30, 0x31,
    0x31, 0x30, 0x31, 0x30, 0x31, 0x30, 0x30, 0x30,
    0x30, 0x31, 0x30, 0x31, 0x31, 0x31, 0x30, 0x31,
    0x30, 0x30, 0x30, 0x31, 0x30, 0x31, 0x30, 0x31,
    0x31, 0x30, 0x31, 0x30, 0x31, 0x30, 0x31, 0x31,
    0x30, 0x31, 0x31, 0x31, 0x31, 0x30, 0x30, 0x31,
    0x31, 0x30, 0x30, 0x31, 0x31, 0x30, 0x31, 0x31,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30,
    0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x31
};

struct opcodetable
{
    unsigned char source;
    unsigned char source2;
    unsigned char write;
} __attribute__((packed));

struct opcodetable *ops = (struct opcodetable *)opcodes;


int main() {
    int i = 0;
    char c = 0;
    int j = 0;
    char res[0x81];

    for (j = 3; j >= 0; j--) {
        memcpy(final, correct + j * 0x20, 0x20);
        memcpy(final + 0x20, input2 + j * 0x20, 0x20);

        for (i = sizeof(opcodes) / sizeof(struct opcodetable) - 1; i >= 0; i--) {
            if (final[ops[i].source] == 0x31 && final[ops[i].source2] == 0x31) final[ops[i].write] ^= 1;
        }

        memcpy(res + j * 0x20, final, 0x20);
    }

    res[0x80] = '\0';
    printf("%s\n", (char *)res);

    for (i = 0; i < strlen(res) / 8; i++) {
        c = TOBIN(res[i * 8 + 7]) << 0 |
            TOBIN(res[i * 8 + 6]) << 1 |
            TOBIN(res[i * 8 + 5]) << 2 |
            TOBIN(res[i * 8 + 4]) << 3 |
            TOBIN(res[i * 8 + 3]) << 4 |
            TOBIN(res[i * 8 + 2]) << 5 |
            TOBIN(res[i * 8 + 1]) << 6 |
            TOBIN(res[i * 8 + 0]) << 7;
            printf("%c", c);
    }

    printf("\n");

    return 0;
}

So it’s time to execute and win again. (Even with a little bit of luck, this time.) =)

$> ./dereverse
01000110010011000100000101000111011000010111000001101100011000010111100101101001011101000110000101110011010100000100001101001101
FLAGaplayitasPCM

To verify the result, I quickly patched the src1 string in the elbisrever binary to the result of the dereverse script and got:

$> ./elbisrever_src1
Congratulations!