How honest are you?
Running here
Summary: breaking a weak PRNG
On the main page we see the text:
You are coming back home from a hard day sieving numbers at the river.
Unfortunately, you trip and all your numbers fall in a nearby lake.Continue.
We click Continue and then:
From the lake a god emerged carrying a number on each hand.
He looked at you and asked the following question…Continue.
Again, click Continue:
Did you drop 4452678531 or 754311689?
If we enter one of the numbers, we either get another question or start from the beginning. So it seems that we need to guess the correct numbers many times.
The numbers look random and the challenge looks like pure guessing. But after looking around, we can find a snippet of code hidden in the html source of the second page. It is hidden in a html comment and padded down with 500 empty lines. Here’s the snippet:
class SecurePrng(object): def __init__(self): # generate seed with 64 bits of entropy self.p = 4646704883L self.x = random.randint(0, self.p) self.y = random.randint(0, self.p) def next(self): self.x = (2 * self.x + 3) % self.p self.y = (3 * self.y + 9) % self.p return (self.x ^ self.y) |
It is a quite simple PRNG: it consists of two LCG combined with xor.
We can guess the first few values and then attack the PRNG to recover the seed and predict next outputs.
The simplest solution is to bruteforce all candidates for $x$, deduce $y$ as xor of PRNG output with $x$ and check if the numbers match. But I will describe another solution, which exploits the fact that the multipliers are very small (2 and 3). This solution would work for much larger $p$.
The idea is to reconstruct $x$ bit-by-bit from least significant to most significant bits. Since we also know $x \oplus y$, we immediately obtain value of the same bits of $y$. Then, to account the modulus $p$ we simply guess how many $p$ we subtract on overflow. This number is not greater the multiplier constants and since they are small, there are quite few possible values. So we compute least significant bits of $x’ = 2x + 3 – k_xP$, then we obtain least significant bits of $y’$ from known $x’ \oplus y’$ and we check if for some $k_y$ the congruence $y’ \equiv 3y + 9 -k_yP\pmod{2^t}$ works.
Note that when we guess a bit of $x$, it possible that both bit values pass the test, leading to exponential explosion. One option is to compute next values (the same LSBs) and check if they match the third generated value (and for this we need to guess the modulus reductions again). But it seems that when one of the multipliers is even, there are at most one candidate per $k_x,k_y$ guess. I haven’t proved this, just observed experimentally. So for the multipliers 2,3 it works perfectly.
Here’s POC:
import random from itertools import product P = 2**256 + 7 NBITS = P.bit_length() Ax, Cx = 2, 5 Ay, Cy = 3, 7 def next(x, y): x = (Ax*x + Cx) % P y = (Ay*y + Cy) % P return x, y # generate two values X0, Y0 = random.randint(0, P-1), random.randint(0, P-1) print "X0", hex(X0) print "Y0", hex(Y0) realkx = (Ax*X0 + Cx) / P realky = (Ay*Y0 + Cy) / P print "REAL KX KY", realkx, realky X1, Y1 = next(X0, Y0) X2, Y2 = next(X1, Y1) prng = [X0 ^ Y0, X1 ^ Y1, X2 ^ Y2] # guess modulo reductions for kx, ky in product(range(Ax), range(Ay)): xs = {0} # go from LSB to MSB for b in xrange(NBITS): if not xs: break xs2 = set() mask = 2**(b+1) - 1 mod = 2**(b+1) for x, bx in product(xs, range(2)): x |= bx << b y = (prng[0] ^ x) & mask if x >= P or y >= P: continue x1 = (Ax*x + Cx - kx * P) % mod y1 = (Ay*y + Cy - ky * P) % mod if (x1 ^ y1) & mask == prng[1] & mask: xs2.add(x) xs = xs2 else: print kx, ky, ":", len(xs), "candidates" for x0 in xs: y0 = prng[0] ^ x0 assert x0 < P if y0 >= P: continue x1, y1 = next(x0, y0) if x0 ^ y0 == prng[0] and x1 ^ y1 == prng[1]: print "GOOD", hex(x0), hex(y0) |
The flag: CTF{_!_aRe_y0U_tH3_NSA_:-?_!_}
