[Easy] Crushing

Crushing

5^th 03 24 / Document No. D24.102.18

Prepared By: clubby789

Challenge Author: clubby789

Difficulty: Easy

Classification: Official

Synopsis

Crushing is an Easy reversing challenge. Players will reverse engineer a 'compression' algorithm, then write a script to recover the original message.

Skills Required

- Basic decompilation skills

Skills Learned

- Basic scripting

Solution

We're given a binary, crush, and a large file containing mostly null bytes named message.txt.cz. If we open the binary in a decompiler, we can observe that it has not been stripped.

int32_t main(int32_t argc, char** argv, char** envp)
    void s
    __builtin_memset(s: &s, c: 0, n: 0x7f8)
    int64_t var_10 = 0
    while (true) {
        int32_t rax_2 = getchar()
        if (rax_2 == 0xffffffff) {
            break
        }
        add_char_to_map(&s, rax_2.b, var_10)
        var_10 = var_10 + 1
    }
    serialize_and_output(&s)
    return 0

We zero out a large stack array. For each character in the input (until EOF) we call add_char_to_map with the array, character and position.

Reversing add_char_to_map, there is a malloc'd structure. I have added a decompiler type and named some variables appropriately.

void add_char_to_map(struct struct_1** arg1, char c, int64_t pos)
    struct struct_1* entry = arg1[zx.q(c)]
    struct struct_1* new_entry = malloc(bytes: 0x10)
    *new_entry = pos
    new_entry->next = nullptr
    if (entry == 0) {
        arg1[zx.q(c)] = new_entry
    } else {
        while (entry->next != 0) {
            entry = entry->next
        }
        entry->next = new_entry
    }

The character is used as an index into our array, which appears to be an array of pointers. We then allocate a structure, storing the position and initializing a pointer to NULL. If the fetched pointer is NULL, we store our new entry there. Otherwise, we follow the next pointer until we find the end of the linked list, and insert our new entry.

This builds up a data structure where we have 255 linked lists - each corresponding to a byte and containing the positions in the input where that byte appears.

Serializing

void serialize_and_output(struct struct_1** arg1)
    for (int32_t i = 0; i s<= 0xfe; i = i + 1) {
        struct struct_1** head = &arg1[sx.q(i)]
        int64_t len = list_len(head)
        fwrite(buf: &len, size: 8, count: 1, fp: __TMC_END__)
        for (struct struct_1* entry = *head; entry != 0; entry = entry->next) {
            fwrite(buf: entry, size: 8, count: 1, fp: __TMC_END__)
        }
    }

We begin by calling list_len which contains the following:

int64_t list_len(struct struct_1** head)
    int64_t count_1
    if (*head == 0) {
        count_1 = 0
    } else {
        int64_t count = 1
        struct struct_1* next = *head
        while (next->next != 0) {
            count = count + 1
            next = next->next
        }
        count_1 = count
    }
    return count_1

Simply iterating the list to count the length.

We write out the length of the list to the output, before iterating the list and writing out every position stored in it.

Decoding

With this information, we can decode this 'compression' scheme.

We'll begin by importing struct.unpack (to parse the sizes from bytes) and making a byte array to contain our output.

from struct import unpack
content = bytearray(1024)

We then want to open the file and begin looping through it. We'll keep track of the highest position seen (so we know how much of the byte array to use), and the current ASCII byte.

fp = open("message.txt.cz", "rb")
highest = 0
for current in range(256):
    ...

For each entry, we'll parse the length. If it is non-zero, we can begin looping over the entries.

length_bytes = fp.read(8)
length = unpack("Q", length_bytes)[0]
for i in range(length):
    pos = unpack("Q", fp.read(8))[0]
    content[pos] = current
    highest = max(highest, pos)

Finally, we can print out our content:

print(content[:highest].decode())