Recur, Peeb Poob writeups [UTCTF 2021]

Recur, Peeb Poob writeups [UTCTF 2021]

2021/03/14
CTF Writeup
utctf-2021, reverse engineering, cutter

This weekend, I participated in UTCTF 2021 with my team, xtal. Here’s a quick writeup for 2 of the reverse engineering challenges - Recur and Peeb Poob.

I solved both of these mostly by using Cutter, a GUI frontend to the Radare2 / Rizin binary analysis tool, and which has a very useful Ghidra decompiler built in.

Recur #

I found this binary that is supposed to print flags.

It doesn’t seem to work properly though…

by hukc

Binary here

I downloaded and ran the program, and noticed that only the first 7 chars (utflag{) are printed.

$ ./recur
utflag{

At first, I thought there was some hardcoded limit on the flag printing that had to be removed. On my machine, there is a noticable delay between when the ‘g’ gets printed and when the ‘{’ gets printed, which suggests that something else is going on.

Opening up in Cutter, and doing some analysis, we can see that the program is very simple. It iterates through the contents of a buffer, and xors those contents with the least significant byte of a value provided by a function which I’ll call recurrence.

Here’s the output from the Ghidra decompiler built in to Cutter, with some annotations / variable names / function names added by me:

undefined8 main(void)
{
    code cVar1;
    uint8_t uVar2;
    undefined8 flag_index;
    int64_t var_8h;

    flag_index._0_4_ = 0;
    while ((int32_t)flag_index < 0x1c) {
        cVar1 = flag[(int32_t)flag_index];
        uVar2 = recurrence((int32_t)flag_index * (int32_t)flag_index);
        putchar((int32_t)(char)(uVar2 ^ (uint8_t)cVar1));
        fflush();
        flag_index._0_4_ = (int32_t)flag_index + 1;
    }
    return 0;
}

int32_t recurrence(uint32_t recur_index)
{
    int32_t iVar1;
    int32_t iVar2;
    uint32_t var_14h;
    int64_t var_8h;

    if (recur_index == 0) {
        iVar1 = 3;
    } else {
        if (recur_index == 1) {
            iVar1 = 5;
        } else {
            iVar1 = recurrence(recur_index - 1);
            iVar2 = recurrence(recur_index - 2);
            iVar1 = iVar2 * 3 + iVar1 * 2;
        }
    }
    return iVar1;
}

The flag buffer that we see in main contains the following data; it seems like there’s only 0x1c bytes of useful information there, suggesting the problem isn’t that we’re reading too little data, since we’re already iterating through the entire 0x1c bytes in the flag buffer in main.

Hexdump of flag buffer in recur binary

The first 7 characters printed are correct, and I noticed the slowdown between the last few characters printed, so this suggests that the issue is that the recursive function is taking too long.

We can recreate the program in Python, and replace the recursive recurrence function with an iterative version:

#!/usr/bin/python3

from pwn import *

flag_raw = b"\x76\x71\xc5\xa9\xe2\x22\xd8\xb5\x73\xf1\x92\x28\xb2\xbf\x90\x5a\x76\x77\xfc\xa6\xb3\x21\x90\xda\x6f\xb5\xcf\x38"

def recurrence(n):
    if n == 0:
        return 3
    elif n == 1:
        return 5
    else:
        return recurrence(n - 1) * 2 + recurrence(n - 2) * 3

# shamelessly stolen from https://stackoverflow.com/a/15047402/10411427 b/c I can't computer science
def recurrence_iter(n):
    recurrence_iter = [3, 5]
    for f in range(1, n):
        recurrence_iter.append(recurrence_iter[-1]*2 + recurrence_iter[-2]*3)
    return recurrence_iter[n]

data_buf = bytearray()
for flag_index in range(0x1c):
    flag_data = flag_raw[flag_index]
    recurrence_data = recurrence_iter(flag_index * flag_index)
    recurrence_data_lsb = pack(recurrence_data, word_size = 'all')[0]
    info(f"flag_index: {flag_index}, flag_data: {flag_data:x}, recurrence_data: {recurrence_data:x}, recurrence_data_lsb: {recurrence_data_lsb:x}")
    data = xor(flag_data, recurrence_data_lsb)
    data_buf.append(u8(data))

print(data_buf)

$ ./recur.py
[*] flag_index: 0, flag_data: 76, recurrence_data: 3, recurrence_data_lsb: 3
[*] flag_index: 1, flag_data: 71, recurrence_data: 5, recurrence_data_lsb: 5
[*] flag_index: 2, flag_data: c5, recurrence_data: a3, recurrence_data_lsb: a3
[*] flag_index: 3, flag_data: a9, recurrence_data: 99c5, recurrence_data_lsb: c5
[*] flag_index: 4, flag_data: e2, recurrence_data: 521ae83, recurrence_data_lsb: 83
[*] flag_index: 5, flag_data: 22, recurrence_data: 18a8cac5545, recurrence_data_lsb: 45
[*] flag_index: 6, flag_data: d8, recurrence_data: 42a7c8d17238da3, recurrence_data_lsb: a3
[*] flag_index: 7, flag_data: b5, recurrence_data: 6558e2a0921fe0694285, recurrence_data_lsb: 85
[*] flag_index: 8, flag_data: 73, recurrence_data: 56ada95f1ef2644f18f2fd7a03, recurrence_data_lsb: 3
[*] flag_index: 9, flag_data: f1, recurrence_data: 29b31ab9d4293d0696d7e18d3aadaf985, recurrence_data_lsb: 85
[*] flag_index: 10, flag_data: 92, recurrence_data: b48ca794ce6ed0acb683eeebad28faab9e7027a3, recurrence_data_lsb: a3
[*] flag_index: 11, flag_data: 28, recurrence_data: 1b7b9fa479a7a82ad3a26b5912556262245a5ed8625959a45, recurrence_data_lsb: 45
[*] flag_index: 12, flag_data: b2, recurrence_data: 25a68c45eaab731e200d7b0d3e1685a6cf2fed9b2137e5f1a77e57a283, recurrence_data_lsb: 83
[*] flag_index: 13, flag_data: bf, recurrence_data: 1d038228611fa616461f4f62ce5b8763182cd704a695b621d689854ece49f621ccc5, recurrence_data_lsb: c5
[*] flag_index: 14, flag_data: 90, recurrence_data: c9390af810fe954d7bea5b84846d1da11f4e0fc27b035384d6718dff532710a69de6b1beb0cea3, recurrence_data_lsb: a3
[*] flag_index: 15, flag_data: 5a, recurrence_data: 31101ecc323803eaaead5df2d907f65906c2f9af6350d1452145fac1f69dcad6338c5abb4ace31a8a00ad1c105, recurrence_data_lsb: 5
[*] flag_index: 16, flag_data: 76, recurrence_data: 6baa23572f8990a311692c95eb1698b2df1bb98f5bdd701a9fff03fda48502bcab7906eb440bbc0eb2faa3a420be5e0e61e803, recurrence_data_lsb: 3
[*] flag_index: 17, flag_data: 77, recurrence_data: 84e5959a40daa15ccac866f3f60164ad532e939a13a63ea0cf5295f319a28107c74908c32051e612cbf0646de134635b16383dbc15dbd472f05, recurrence_data_lsb: 5
[*] flag_index: 18, flag_data: fc, recurrence_data: 5c461c3bdfe02fbbed8f6c62dfde1083dfd7cd768a1475bdda98c2c4490248b0f6c29dc8249c6f9892f8e1c701747a087e7d4c1d1135c7c1fa56483237df602a3, recurrence_data_lsb: a3
[*] flag_index: 19, flag_data: a6, recurrence_data: 2409d4192edd92cde0a3166cd1d4c8bfe4b8295309f731bbece20fed2d2935d1c8abd7b3b4e7b95cae244396bf45f364f3b46f93b8bad741bc523d45481f52e976882a66aeea56c5, recurrence_data_lsb: c5
[*] flag_index: 20, flag_data: b3, recurrence_data: 7ead1367ba4447be635324bea7a532d507c7d9ff52a539d95d6af70c81da8d45f039a7d73bd7912249b0fcd76fe44eb6d486746962ac1732af603c7cb4702946aa9910f8fd13caec99abfd10b9b8a83, recurrence_data_lsb: 83
[*] flag_index: 21, flag_data: 21, recurrence_data: fa76ef151aac08d8f7e262e29de695a4fb7f452f8c583ab7d6d5fc32578bb6e8cbb97fd66fc97959b3db84c6e40b4dafd3f21a5dc0150b6e4a0be3ea457ec7fb75bfcc98443fca2f3928fb9d22eca85a7cec96024f20045, recurrence_data_lsb: 45
[*] flag_index: 22, flag_data: 90, recurrence_data: 1168fa8bb1e3ed54d896ddf19c6b49752bcf438571b4b34482ed373aa1d37cbb6fe509aaf6ea40d5333ffd090b401b75376078e5dc94c5d7e0fa3a0436da16974d38e9e28431fc2817e8f45af22b3487ad2d6f61a0dbdd92d63c9f16fa3d5c3a3, recurrence_data_lsb: a3
[*] flag_index: 23, flag_data: da, recurrence_data: ae4493d5eb75a64503a55815b8939dafa17bbc95f04dff42949e843622ac5b1df9b09ea7143b24c07f3ca9c46fe0e6ea69733b212a44e0c60c309ddd93b8d99817283fe8b0dc542767e32d98888ea5f9dfbe6087de4f3f6c612fc827c224cfd5a2033bbccf3efc7b85, recurrence_data_lsb: 85
[*] flag_index: 24, flag_data: 6f, recurrence_data: 3d532ad1d593ec6f15b89525e754489addb1035389c99025fbb07175f345dbc1274427eb56bf32312a8e73b5a2256369d2d4ecd8c7ceed1ba13a04a31bd6b7347e39bd9d4bc5784a7b2f36135aa3763ab17f6d38483c175925acc5c2a6f0fe5bcfe8ec74723b6e27bfdae9c61304f71714a03, recurrence_data_lsb: 3
[*] flag_index: 25, flag_data: b5, recurrence_data: c238d62b216ed0982550815a3cf3a7244f9c22741b4ced6b1824427719463dfaaff4399e0920a02234a490bad59edb375c4b0f2d862c9c030a41775a38393102d24e81a7fdbc5a2e8588826cd863a1bab99fb32bc1e8b7b04809d90b3e471784568df6e7fb93eefac8b5e282a17d025dde02247f4dacc3a5d899a085, recurrence_data_lsb: 85
[*] flag_index: 26, flag_data: cf, recurrence_data: 15a015ddedb1f57a4998ce625bf847c2eacf50f8ca0c4c253921fa17792eb8743c19b95d6e4299353eb15f854d1e4e13125f34e1388d7c77ee4154ae665266b20f1174d0ee3c45bd6c5533e9c26f7c1105b43a55bdd27e532ecbf4297f52c0f6bf5cb2c12ce70f8d33c2245b6bfc1ac51c7a150f271da9da826c72901bb8720f24e90d46b91a3, recurrence_data_lsb: a3
[*] flag_index: 27, flag_data: 38, recurrence_data: 15aba856d0a1626ebc725146b565124bc74f37bc8fe06c86cb56f85d65412f10cc66a29836a078d15d4548e707abfcd4595680536a0dbceca0e1506f9bfba67bd5135804695bb3d09ca44b3905f77cdcbfc24bd92e26ca3ac19f6ac85c936695527a445448187f73e8a82a99bb5abd4d4786d6c7e2d9a2f17114c3f06070acaa5904a952176a6ed8a9c675dbf6d785cf45, recurrence_data_lsb: 45
bytearray(b'utflag{0pt1m1z3_ur_c0d3_l0l}')

The flag is utflag{0pt1m1z3_ur_c0d3_l0l}.

Peeb Poob #

Computers usually go beep boop, but I found this weird computer that goes peeb poob.

by hukc

Binary here

$ file peeb_poob
peeb_poob: ELF 32-bit MSB executable, Renesas SH, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 5.10.7, with debug_info, not stripped

This is an executable built for the SuperH architecture. Radare2 / Rizin, which backs Cutter, supports this architecture, so Cutter is able to disassemble / decompile this just fine. Because the decompiler output was quite good in this case, I didn’t really have to understand how to read the SuperH assembly - a learning opportunity lost, but it meant I got this done much faster.

There’s only 2 interesting functions:

  • main
  • A function I’ve called encode, which is called from the jsr instruction at 0x00400800.

Decompiled output:

undefined4 main(void)
{
    uint32_t uVar1;
    char acStack52 [32];
    undefined4 uStack20;
    uint32_t uStack16;
    int32_t iStack12;

    uStack20 = 0;
    iStack12 = 0;
    while (iStack12 < 0x20) {
        acStack52[iStack12] = '\0';
        iStack12 = iStack12 + 1;
    }
    (*_printf)(*(undefined4 *)0x40087c, 0);
    (*_fgets)(acStack52, 0x20, **(undefined4 **)0x400884);
    (*_encode)(acStack52);
    uStack16 = 0;
    while (uVar1 = (*_strlen)(acStack52), uStack16 < uVar1) {
        if (acStack52[uStack16] != *(char *)(uStack16 + *(int32_t *)0x400890)) {
            (*_puts)(*(undefined4 *)0x400894);
            (*_exit)(0xffffffff);
        }
        uStack16 = uStack16 + 1;
    }
    (*_puts)(*(undefined4 *)0x4008a4);
    return 0;
}

void encode(int32_t param_1)
{
    uint32_t uVar1;
    uint32_t uStack16;

    uStack16 = 0;
    while (uVar1 = (*_strlen)(param_1), uStack16 < uVar1) {
        uVar1 = (uint32_t)((int32_t)uStack16 < 0);
        uVar1 = ((uStack16 ^ -uVar1) + uVar1 & 3 ^ -uVar1) + uVar1;
        if (uVar1 < 4) {
            switch(uVar1) {
            case 0:
                *(uint8_t *)(uStack16 + param_1) = *(uint8_t *)(uStack16 + param_1) ^ 0x21;
                break;
            case 1:
                *(uint8_t *)(uStack16 + param_1) = *(uint8_t *)(uStack16 + param_1) ^ 7;
                break;
            case 2:
                *(uint8_t *)(uStack16 + param_1) = *(uint8_t *)(uStack16 + param_1) ^ 0x23;
                break;
            case 3:
                *(uint8_t *)(uStack16 + param_1) = *(uint8_t *)(uStack16 + param_1) ^ 5;
            }
        }
        uVar1 = (*_strlen)(param_1);
        if (uStack16 + 1 < uVar1) {
            *(uint8_t *)(uStack16 + 1 + param_1) =
                 *(uint8_t *)(uStack16 + param_1) ^ *(uint8_t *)(uStack16 + 1 + param_1);
        }
        uStack16 = uStack16 + 1;
    }
    return;
}

I don’t have an emulator for the SuperH architecture handy (and even if I did, I would need a libc compiled for SuperH as well, since this executable is dynamically linked). Since this program is very simple, it’s easier to just write a version of it in Python, run it, and observe its behaviour.

Here’s the encode function, written pretty much directly from the decompiled output:

#!/usr/bin/python3

from pwn import *

def strlen(data):
    return data.index(b'\x00')

def encode(data):
    counter = 0
    limit = strlen(data)
    while counter < limit:
        if counter < 0:
            tmp = ((counter ^ -1) + 1 & 3 ^ -1) + 1
        else:
            tmp = ((counter ^ -0) + 0 & 3 ^ -0) + 0

        if tmp < 4:
            if tmp == 0:
                data[counter] = data[counter] ^ 0x21
            if tmp == 1:
                data[counter] = data[counter] ^ 0x07
            if tmp == 2:
                data[counter] = data[counter] ^ 0x23
            if tmp == 3:
                data[counter] = data[counter] ^ 0x05

        tmp2 = strlen(data)
        if counter + 1 < tmp2:
            data[counter+1] = data[counter] ^ data[counter+1]

        counter = counter + 1
        limit = strlen(data)

data = bytearray(b"utflag{\x00")
encode(data)
print(hexdump(data))

If we look at main again, it just takes the string that a user inputs, passes it through encode, and compares the result to the flag, which is somewhere in the binary and which is 0x20 bytes long. The address that the disassembly gave for the encoded flag was incorrect (there might have been something weird going on with the address mapping when disassembling), but we can run the script above, and we should get the first few bytes of the encoded flag:

$ ./peeb_poob.py
00000000  54 27 62 0b  4b 2b 73 00                            │T'b·│K+s·│
00000008

Search for the string “K+s” in the binary, and we find the encoded flag at 0x411010. Let’s copy it out to our python script:

encoded_flag = b"\x54\x27\x62\x0b\x4b\x2b\x73\x14\x06\x32\x61\x3b\x78\x4f\x5c\x29\x57\x20\x30\x06\x45\x1d\x4e\x7b\x6a\x0f\x51\x5e\x00\x00\x00\x00"

Now we just have to write a version of the encode function that performs its operations in reverse, and pass the encoded flag to it:

def reverse_encode(data):
    decoded_data = bytearray([x for x in data])
    counter = 0
    limit = strlen(data)
    while counter < limit:
        if counter < 0:
            tmp = (((counter ^ -1) + 1) & 3 ^ -1) + 1
        else:
            tmp = (((counter ^ -0) + 0) & 3 ^ -0) + 0

        if counter > 0:
            decoded_data[counter] = data[counter-1] ^ decoded_data[counter]

        if tmp < 4:
            if tmp == 0:
                decoded_data[counter] = decoded_data[counter] ^ 0x21
            if tmp == 1:
                decoded_data[counter] = decoded_data[counter] ^ 0x07
            if tmp == 2:
                decoded_data[counter] = decoded_data[counter] ^ 0x23
            if tmp == 3:
                decoded_data[counter] = decoded_data[counter] ^ 0x05

        counter = counter + 1

    return decoded_data

encoded_flag = bytearray(b"\x54\x27\x62\x0b\x4b\x2b\x73\x14\x06\x32\x61\x3b\x78\x4f\x5c\x29\x57\x20\x30\x06\x45\x1d\x4e\x7b\x6a\x0f\x51\x5e\x00\x00\x00\x00")
decoded_flag = reverse_encode(encoded_flag)
print(decoded_flag)

The flag is utflag{b33p_b00p_p33b_p00b}.