cheat

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-07-02 | Status: Solved Techniques: arithmetic_inversion, keygen, modular_inverse, static_disassembly, two_adic_congruence

Summary

Task: crack a license/activation check in a not-stripped x86-64 ELF; key form xxxx-xxxx-xxxx-xxxx, 4 checks each XOR a scaled sum against a constant. Solution: static-analyze the four check functions, invert the additive/multiplicative arithmetic in Python (modular inverse, plus a 2-adic congruence for the even multiplier), and account for main negating three of the four arguments.

cheat — spbctf

Description

Я нашёл приватный чит, позволяющий получить 10 баллов на скорборде! Беда в том, что он просит его активировать, а у меня только ключ от старой версии — 31db-f14b-080a-b491. К этой версии тоже должен быть xxxx-xxxx-xxxx-xxxx. Помогите крякнуть! Флаг — ключ активации

English summary: A private "cheat" binary asks for an activation key of the form xxxx-xxxx-xxxx-xxxx. We're given an old-version key 31db-f14b-080a-b491 (a red herring — it only reveals the format) and must recover the new-version key. The flag is the activation key itself. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Recon

$ file cheat.elf
cheat.elf: ELF 64-bit LSB pie executable, x86-64, dynamically linked,
           not stripped, GCC (Debian 9.3.0-11) 9.3.0

Useful strings:

Please enter activation key:
%x-%x-%x-%x
Activation successful, enjoy your points
Activation failed

The binary is not stripped, so we have symbols:

Analysis

main logic

main reads the key with scanf("%x-%x-%x-%x", &w0, &w1, &w2, &w3) into four 32-bit ints, then calls the four check functions and sums their return values:

 c read-only • copy allowed Copy
r  = check0( w0);    // argument passed as-is
r += check1(-w1);    // argument NEGATED (neg eax) before call
r += check2(-w2);    // argument NEGATED
r += check3(-w3);    // argument NEGATED
if (r == 4) puts("Activation successful, enjoy your points");
else        puts("Activation failed");

Subtlety #1: main applies neg eax to the three high words before passing them to check1/check2/check3. Each check returns 1 on success, so all four must pass. When we recover the argument each check wants, words 1–3 must be negated back (word = (-arg) & 0xffffffff) to obtain the real key digits. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

sum(a, b)

sum looks scary — an increment/decrement loop — but it is just 32-bit addition:

sum(a, b) = (a + b) & 0xffffffff

Subtlety #2: don't waste time reversing the loop; it's a + b.

check pattern

Every check computes two sum calls, multiplies one product by a constant, XORs with the other, and compares to a 32-bit target. With M = 0xffffffff and s(a,b) = (a+b) & M:

check0(x): ebx = s(x, 0x8c29)
           eax = (s(0xffff777d, 0x48f) * 0x10be) & M
           ok iff (eax ^ ebx) == 0xf75f88ae
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

check1(x): ebx = s(0xffffe544, x)
           eax = (s(0x924e, 0xffff1503) * 0xcb6a) & M
           ok iff (eax ^ ebx) == 0x4677aa62

check2(x): ebx = s(0xffff646d, 0xffff5370)
           eax = (s(x, 0xb59e) * 0x1db6) & M
           ok iff (eax ^ ebx) == 0xffc8529b

check3(x): ebx = s(0xffffd55c, 0xe7f8)
           eax = (s(x, 0x85a0) * 0x3661) & M
           ok iff (eax ^ ebx) == 0xe74c7dec

In check0 / check1 the unknown x sits inside an additive sum, and the multiplied term is a constant. In check2 / check3 the unknown sits inside the multiplied sum. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

Additive blocks (check0, check1)

The constant side gives eax. Recover the required ebx = eax ^ target, then x = (ebx - additive_const) & M.

Multiplicative blocks (check2, check3)

Recover the product p = ebx_const ^ target, then solve mult * s(x,k) ≡ p (mod 2^32) and finally x = s - k.

• check3: mult = 0x3661 is odd, hence invertible mod 2^32 — just multiply by its modular inverse.
• check2: mult = 0x1db6 is even, so it is not invertible mod 2^32. Subtlety #3: solve the 2-adic linear congruence by stripping the common power of two: let g = gcd(mult, 2^32); the congruence is solvable iff g | p; divide through by g and invert the (now odd) reduced multiplier modulo 2^32 / g. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Python solver

 python read-only • copy allowed Copy
#!/usr/bin/env python3
M = 0xffffffff

def s(a, b):
    return (a + b) & M

# --- additive blocks: x lives inside a sum ---
def solve_additive(eax_const, target, add_const):
    ebx = eax_const ^ target
    return (ebx - add_const) & M

# --- multiplicative blocks: x lives inside a sum that is multiplied ---
def solve_mult(ebx_const, target, mult, k):
    p = ebx_const ^ target            # required product mod 2^32
    mod = 1 << 32
    g = mult
    m2 = mod
    # gcd(mult, 2^32) is a power of two -> strip it
    import math
    g = math.gcd(mult, mod)
    assert p % g == 0, "no solution"
    mult_r, p_r, mod_r = mult // g, p // g, mod // g
    inv = pow(mult_r, -1, mod_r)
    sx = (p_r * inv) % mod_r          # one representative for s(x,k)
    return (sx - k) & M
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# check0: eax = (s(0xffff777d,0x48f)*0x10be)&M ; ebx = s(x,0x8c29)
eax0 = (s(0xffff777d, 0x48f) * 0x10be) & M
w0 = solve_additive(eax0, 0xf75f88ae, 0x8c29)

# check1: eax = (s(0x924e,0xffff1503)*0xcb6a)&M ; ebx = s(0xffffe544,x)
eax1 = (s(0x924e, 0xffff1503) * 0xcb6a) & M
arg1 = solve_additive(eax1, 0x4677aa62, 0xffffe544)  # this is -w1
w1 = (-arg1) & M                                     # main negated it

# check2: ebx = s(0xffff646d,0xffff5370) ; eax = (s(x,0xb59e)*0x1db6)&M  (even mult)
ebx2 = s(0xffff646d, 0xffff5370)
arg2 = solve_mult(ebx2, 0xffc8529b, 0x1db6, 0xb59e)  # this is -w2
w2 = (-arg2) & M
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# check3: ebx = s(0xffffd55c,0xe7f8) ; eax = (s(x,0x85a0)*0x3661)&M  (odd mult)
ebx3 = s(0xffffd55c, 0xe7f8)
arg3 = solve_mult(ebx3, 0xe74c7dec, 0x3661, 0x85a0)  # this is -w3
w3 = (-arg3) & M

print("%04x-%04x-%04x-%04x" % (w0 & 0xffff, w1 & 0xffff, w2 & 0xffff, w3 & 0xffff))
# -> REDACTED

Recovered words:

Simulating main in Python (applying the negations to blocks 1–3) makes all four checks return 1, sum == 4 → "Activation successful". The old key 31db-f14b-080a-b491 from the prompt is a decoy; it only tells us the 4×16-bit xxxx-xxxx-xxxx-xxxx layout. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍