2021-07-18

GoogleCTF 2021 - I can't believe it's not crypto (314pts / 17 solves)

I can’t believe it’s not crypto

Description:

I played Google CTF 2021 with DiceGang last weekend and we placed 3rd. The challenges are always

Despite being labeled a misc problem, I think this challenge was actually one of my favorite reversing problems. One of the things you do frequently in reverse engineering, is recognizing signatures of computation. High level concepts can be rendered differently in different environments. For example, imagine the concept of appending to list.

In Python, we might see something straightforward like:

a = [1,2,3]
a.append(4)

In other languages, it is common to use a linked-list. For example in C:

typedef struct _list_node {
    list_node next;
    int item;
} list_node;

void foo() {
    // ...

    list_node head;

}

add

3 + 4

`lambda x: lambda

This challenge caught my attention because the provided code is so short:

SBOX = {
    (0, 0): (0, 0),
    (0, 1): (1, 0),
    (0, 2): (0, 1),
    (1, 0): (1, 1),
    (1, 1): (0, 2),
    (1, 2): (1, 2),
}

def step(l1, l2):
    if l1[0] == 0:
        l1.pop(0)
    else:
        l2.insert(0, 1)
    l1.append(0)

    for i in range(len(l1)):
        l1[i], l2[i] = SBOX[l1[i], l2[i]]

    while l1[-1] == l2[-1] == 0:
        l1.pop()
        l2.pop()

def count(l1, l2):
    n = 0
    while l1 + l2 != [1, 0]:
        step(l1, l2)
        n += 1
    return n

def read_lists():
    l1 = [ord(c) % 2 for c in input("> ")]
    l2 = [ord(c) % 3 for c in input("> ")]
    assert len(l1) < 24, "too big"
    assert len(l1) == len(l2), "must be same size"
    return l1, l2

if __name__ == "__main__":
    l1, l2 = read_lists()
    c = count(l1, l2)
    if c > 2000:
        print("You win")
        print(open("flag.txt").read())
    else:
        print("Too small :(")
        print(c)

After a quick read over, we can gleam the following:

• We provide two lists of identical length
• The first list will contain 0 or 1. The second list will contain 0, 1, or 2.
• The program will invoke step repeatedly on the lists until some end state.
• If the number of steps is over 2000, we get the flag.