Birds of Randomness — HackTheBox

Description

"You think you found your soulmate, but you lost the train ticket that your love gave you to meet again. The only thing that you remember is the coordinates of the departing station and your love disappearing into the steam of the train."

The server generates a random 256-bit "ticket number" as a seed for a Wichmann-Hill PRNG (three coupled LCGs with moduli 30269, 30307, 30323). It rotates the PRNG until all three components (x, y, z) are prime, computes scalar d = x·y·z, and returns the EC point d·G as the "departing station coordinates." It then does the same for the "destination" — which we must guess in at most 6 attempts.

Files provided: source.py, love_letter.txt (flavor text warning not to do stego on forologia.jpg).

Analysis

Elliptic Curve Parameters

E: y² = x³ + 2x + 3  over  F_p
p = 17101937747109687265202713197737423  (~113 bits)
G = (3543321030468950376213178213609418, 14807290861072031659976937040569354)
n = 17101937747109687496599931614463506  (curve order)

Critical Vulnerability: Smooth Curve Order

The curve order factors completely into small primes:

n = 2 × 3 × 7² × 1487 × 3761 × 176489 × 439693 × 3113111 × 43054831

The largest prime factor is only ~4.3×10⁷. This makes the ECDLP trivially solvable via the Pohlig-Hellman algorithm with Baby-step Giant-step in each subgroup. Total work is roughly √(largest_factor) ≈ 6500 EC operations — instant.

PRNG Structure (Wichmann-Hill 1982)

x = (171 * x) % 30269
y = (172 * y) % 30307
z = (170 * z) % 30323

...