splatter calc

Reverse this binary to determine the input number required to read the flag on the remote server.

nc challenges.tamuctf.com 60032

Download: tamu2020-splatter-calc

Linear congruential generator

Looks like a rust bin with LCG. Binary implements an LCG seeded with user input, it then applies a binary operation to the output of the LCG and a starting fixed point 0xcafebabe.

It repeats this process 8 times in total, and every time it would use the next output from the LCG and the result of the previous binary operation. At the end of the routine it asserts that the output from the operation and the LCG each have a specific value.

Our goal is to get the initial seed that would lead to this state.

Reversed code

#include <stdio.h>
#include <stdlib.h>

unsigned long long transform(unsigned long long prev_trans, unsigned long long prev_lcg) {
    int choice = (int)(prev_lcg & 0x7);
    switch(choice) {
        case 0:
            return prev_trans;
        case 1:
            return prev_trans + prev_lcg;
        case 2:
            return prev_trans - prev_lcg;
        case 3:
            return prev_trans * prev_lcg;
        case 4:
            return (prev_trans * prev_trans);
        case 5:
            return (prev_trans << (prev_lcg & 0xFF));
        case 6:
            return (prev_trans >> (prev_lcg & 0xFF));
        case 7:
            return (prev_trans ^ prev_lcg);

    }
    return 0;
}

int main() {

    unsigned long long seed;
    scanf("%llu", &seed);
    printf("Got seed: %llu\n", seed);
    unsigned long long start = (long long)(seed & 7);
    unsigned long long prev_trans = transform(0xcafebabe, seed);
    unsigned long long prev_lcg = (seed * 0x83f66d0e3) + 0x24a452f8e;
    for (int i = 0; i < 7; ++i) {
        prev_trans = transform(prev_trans, prev_lcg);
        prev_lcg = (prev_lcg * 0x83f66d0e3) + 0x24a452f8e;
    }
    if (prev_lcg == 0x471de8678ae30ba1 && prev_trans == 0xacdee2ed87a5d886) {
        printf("%llu %llu\n", prev_trans, prev_lcg);
        printf("YES");
        return 0;
    } else {
        printf("%llu %llu\n", prev_trans, prev_lcg);
        printf("NO");
        return 1;
    }
}

Solution

from gmpy2 import isqrt, mpz
from Crypto.Util.number import inverse
from sympy.ntheory.residue_ntheory import sqrt_mod

MAX = 2 ** 64

def unl(p):
    return ((p - 0x24a452f8e) * inverse(0x83f66d0e3, MAX)) % MAX


def unt(t, p):
    choice = p & 0x7
    mapz = {
            0: lambda x: x[0],
            1: lambda x: x[0] - x[1] % MAX,
            2: lambda x: x[0] + x[1] % MAX,
            3: lambda x: (x[0] * inverse(x[1], MAX)) % MAX,
            4: lambda x: sqrt_mod(x[0], MAX),
            5: lambda x: (x[0] >> (x[1] & 0xFF)) % MAX,
            6: lambda x: (x[0] << (x[1] & 0xFF)) % MAX,
            7: lambda x: (x[0] ^ x[1])
    }
    return mapz[choice]((t, p)) % MAX


def rel(p):
    return ((p * 0x83f66d0e3) + 0x24a452f8e) % MAX

def ret(t, p):
    choice = p & 0x7
    mapz = {
            0: lambda x: x[0],
            1: lambda x: x[0] + x[1] % MAX,
            2: lambda x: x[0] - x[1] % MAX,
            3: lambda x: (x[0] * x[1]) % MAX,
            4: lambda x: (x[0] ** 2) % MAX,
            5: lambda x: (x[0] << (x[1] & 0xFF)) % MAX,
            6: lambda x: (x[0] >> (x[1] & 0xFF)) % MAX,
            7: lambda x: (x[0] ^ x[1])
    }
    return mapz[choice]((t, p)) % MAX

prevl = 0x471de8678ae30ba1
prevt = 0xacdee2ed87a5d886

for i in range(8):
    y = unl(prevl)
    x = unt(prevt, y)
    print(y, x)
    assert rel(y) == prevl
    assert ret(x, y) == prevt
    print(i)
    prevl = y
    prevt = x

print(hex(prevl), hex(prevt))
print(prevl, prevt)

Flag

$ python solve.py 
7515707083221606161 4940936045942684021
0
17764897228028070113 5622782891624165524
1
4054891027388248273 1567891864235917251
2
16487616737524898849 3527019200420570018
3
269053440828241041 3257965759592328977
4
564860419845330273 2693105339746998704
5
2693104353610717777 986136280927
6
982730589345 3405691582
7
0xe4cf4ec4a1 0xcafebabe
982730589345 3405691582

$ nc challenges.tamuctf.com 60032
Please enter an initial rng: 982730589345
gigem{00ps_ch3ck_y0ur_7upl35}

Flag

gigem{00ps_ch3ck_y0ur_7upl35}