The Fortune Teller + The Fortune Teller's Revenge - Crypto

Points: 500 + 750 | Difficulty: Medium + Hard | Author: SwitchCaseAdvocate Flags: 0xfun{trunc4t3d_lcg_f4lls_t0_lll} / 0xfun{r3v3ng3_0f_th3_f0rtun3_t3ll3r} Solved by: Smothy @ 0xN1umb

what we got

two challenges, same Fortune Teller, escalating difficulty. both give us a python source for a custom PRNG - a 64-bit Linear Congruential Generator (LCG) with known constants:

M = 2**64
A = 2862933555777941757
C = 3037000493
state = (A * state + C) % M

the catch? we only see the upper 32 bits of each state (state >> 32). classic truncated LCG.

Part 1 gives us 3 consecutive truncated outputs, wants us to predict the next 5 full 64-bit states.

Part 2 (Revenge) adds a twist - 100,000 step jumps between each glimpse. so the 3 outputs we see are spaced ~100k states apart. way harder to brute force... or is it?

the solve - part 1

ngl this is a classic crypto CTF pattern. 64-bit LCG, 32-bit truncation. the description literally says "64-bit truths but only reveals 32-bit glimpses".

the idea: if we know the upper 32 bits of state s1, the unknown lower 32 bits l1 is only 32 bits. for each candidate l1:

• compute full s1 = (h1 << 32) | l1
• compute s2 = A * s1 + C mod 2^64
• check if upper 32 bits of s2 match h2
• if yes, verify with h3 too

2^32 candidates sounds like a lot but in C with -O3 it rips through in under 2 seconds lmao

for (uint64_t l1 = 0; l1 < (1ULL << 32); l1++) {
    uint64_t s1 = (h1 << 32) | l1;
    uint64_t s2 = A * s1 + C;
    if ((s2 >> 32) != h2) continue;
    uint64_t s3 = A * s2 + C;
    if ((s3 >> 32) != h3) continue;
    // found it, predict forward from s3
}

once you have the full s3, predicting the next 5 is just state = A * state + C five times. ez.

first blood material fr

the solve - part 2 (revenge)

ok so now there's a 100k step jump between glimpses. the sequence looks like:

the jump uses precomputed constants:

A_JUMP = pow(A, 100000, M)  # = 3297373631046652033
C_JUMP = 8391006422427229792

key insight: jump() then next() is just another LCG step with combined constants. if you chain them:

so the observed states s1, s2, s3 form their OWN effective LCG:

A_eff = (A * A_JUMP) % 2**64  # = 8810128861561192317
C_eff = (A * C_JUMP + C) % 2**64  # = 1496106642115246093

same exact brute force works - just swap in A_eff and C_eff. still ~1-2 seconds in C.

the only gotcha was figuring out what "next 5 states" the server wanted. tried the effective (jumped) states first - nope. turns out it wanted plain .next() continuations from s3. makes sense since once you have the full internal state you can do whatever.

# recover s3 with bruteforce, then just:
state = s3
for i in range(5):
    state = (A * state + C) % M  # simple next()

tldr

the jumps don't help at all defensively. once you figure out that jump+step = one big LCG step with different constants, it collapses to the exact same problem. truncated LCGs are just cooked no matter how you space the outputs.

ironic that the first flag references LLL (lattice reduction) but brute force was fast enough. sometimes the dumb approach wins.

flags

smothy out ✌️