Google CTF – Woodman (Crypto 100)

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.


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…


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:
        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:
            x1 = (Ax*x + Cx - kx * P) % mod
            y1 = (Ay*y + Cy - ky * P) % mod
            if (x1 ^ y1) & mask == prng[1] & mask:
        xs = xs2
        print kx, ky, ":", len(xs), "candidates"
        for x0 in xs:
            y0 = prng[0] ^ x0
            assert x0 < P
            if y0 >= P:
            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_:-?_!_}

Leave a Reply

Your email address will not be published.