its-prime-time

Task description

Can you enter the correct flag?

The original was in Croatian; this is my translation.

First pass

checker is a stripped, statically linked x86-64 ELF. strings on it turns up the flag format, Correct Password! and Wrong Password!, and two enormous 446-digit numbers that differ by only 24, alongside references to /proc/self/status and TracerPid:, the standard way a Linux process checks whether a debugger is attached to it.

Reading the disassembly

Tracing main by hand (no decompiler, straight objdump -d) turned up, in order:

1. Input validation. Confirms the input is 21 characters, starts with CTF2026[ and ends with ], and pulls out the 12 characters between the brackets.
2. Anti-debugging. Reads /proc/self/status and checks TracerPid:, exits quietly if a debugger is attached. It also scans the functions it’s about to run for 0xCC bytes (the x86 breakpoint instruction) and checks how long execution has taken, exiting if either looks tampered with.
3. A constant, computed the hard way. A chain of obfuscated arithmetic involving a randomly chosen prime always lands on the same result, 1224, regardless of which prime was picked.
4. Picking a prime. rand() is seeded with the current time and used to choose between two hardcoded 446-digit starting numbers, then the program searches outward from that number (adding or subtracting 2 at a time) for the nearest actual prime.
5. Generating code from the prime. The constant 1224 is subtracted from that prime, and the resulting big number’s bytes, read little-endian, turn out to be valid x86-64 machine code. That generated function is then called directly, with the user’s 12 input bytes as its argument.

There’s no “check” function written anywhere in the binary; it’s manufactured at runtime out of a number that looks, at a glance, like cryptographic filler.

Why the random seed doesn’t matter

Both hardcoded starting numbers, N1 and N2, differ by only 24. Testing primality on the candidates between them (N2+2, N2+4, and so on) with sympy.isprime() shows that both searches, whichever one the random seed happened to pick, converge on the exact same prime: N2 + 10. So although the choice between N1 and N2 depends on an unpredictable timestamp-derived seed, the actual function generated at runtime is identical either way, and deterministic from the binary alone.

Extracting the generated cipher

Subtracting 1224 from N2 + 10 and reading the result as x86-64 instructions reveals a small, custom 4-round block cipher operating on the 12 input bytes, read as three 32-bit little-endian words. Each round, with a fixed key s, transforms the state (a, b, c):

t     = ROL((a ^ s) * 3, 5) + b
b_out = ROL((c + s) * 5, 7) ^ a
a_out = ROL((s ^ t) * 7, 11) + c
c_out = t

using four fixed round keys (0xa5a5a5a5, 0x3c4d5e6f, 0x9e3779b9, 0x1f2e3d4c), and the binary checks the result against three fixed target values.

Inverting it

Every operation in a round (rotate, add, multiply by an odd constant, XOR) is invertible, so each round can be undone given the output and the round’s key:

def invert_round(a_out, b_out, t, s):
    s_new = (s ^ t) & M
    c = (a_out - rol32((s_new * 7) & M, 11)) & M
    a = (b_out ^ rol32(((c + s) & M) * 5 & M, 7)) & M
    b = (t - rol32(((a ^ s) & M) * 3 & M, 5)) & M
    return a, b, c

Running all four rounds in reverse from the three target values recovers the three 32-bit words, which as little-endian ASCII spell out 9706, 8326, 3595, concatenating to the 12-character flag content: 970683263595.

What made this one hard

The check function genuinely doesn’t exist as static code in the binary; it has to be derived at runtime from a number that otherwise looks like crypto noise, which means recognising the pattern (subtract a constant, interpret as machine code) before any of the actual cipher-inversion work could even start.