THE GARDEN

Dual EC-Style PRNG Backdoor (Chosen Related Points)

Updated 19 Sep 2026

• •

  What it is

  • •

    A Dual EC-style construction becomes predictable when an attacker can choose specially related curve points. The supplied challenge allows Q=P, turning a truncated output into almost all of a later internal state.

• •

  When to apply

  • •

    The source exposes a point-selection interface and updates state from elliptic-curve x-coordinates. Establish the exact state and output timing before searching missing bits.

• •

  Symbols and assumptions

  • •

    $X(R)$ means the integer x-coordinate of point R on a curve over $\mathbb F_p$. At step i, $s_i=X(t_iP)$, stored next state $t_{i+1}=s_i$, and output $r_i=X(s_iQ)\bmod2^{240}$.

• •

  Math — step by step

  • •
    1. Choose Q=P. Then $r_i=X(s_iP)\bmod2^{240}=s_{i+1}\bmod2^{240}$. So output r_i reveals the low 240 bits of the next s-value. It does not reveal the entire state instantly.
  • •
    2. After reconstructing r1 from its base-37 digits, enumerate $\widehat s_2=r_1+h2^{240}$ for $0\le h<2^{16}$ on this 256-bit field. Reject candidates $\widehat s_2\ge p$: x-coordinates are field elements, so the bound is p, not the curve group order.
  • •
    3. Predict $\widehat r_2=X(\widehat s_2P)\bmod2^{240}$ and compare its base-37 prefix to observed next-block spins. More digits remove accidental matches. Continue until the candidate is uniquely supported; a fixed four-digit prefix is not a proof.
  • •
    4. With the correct s2, compute the full next state $s_3=X(s_2P)$ and repeat. No y-sign guessing is needed for this Q=P shortcut because each known integer is used as a scalar in the next multiplication.
  • •
    5. For speed, precompute $T=2^{240}P$ and $R=r_1P$. Candidate multiplication is $R+hT$ by distributivity. Retain only valid field-coordinate candidates and independently validate their predictions.
• •

  Worked example

  • •

    A small truncation example illustrates enumeration: suppose a field coordinate is below p=251 and only its low 4 bits, r=11, are visible. Candidates are $11+16h$ for h=0,…,15, rejecting 251 and above; here h=15 gives 251 and is rejected.

  • •

    If the real coordinate is 171, it appears at h=10 because $171=11+16\cdot10$. Enumeration only proposes this candidate; predicting the next observed output is what identifies it. This toy arithmetic illustrates truncation, not an independently secure curve.

• •

  Checks and pitfalls

  • •

    In the pasted roulette source, Game.init does not assign the returned digit count to num_spins. The old writeup’s “spurious round-2 croupier message” explanation is therefore inconsistent with this source.

  • •

    A boundary message follows the spin that exhausts a block, after the next block has already been loaded. At most 47 digits occur per block; shorter blocks are possible. Follow the source’s state transitions rather than the old len>30 heuristic.

  • •

    This is a challenge-specific clone and chosen-point vulnerability. Historical background: NIST’s 2014 removal of Dual_EC_DRBG.

• •

  Related

  • •

    Recovering PRNG Outputs from Base-N Digits

  • •

    Elliptic Curves (Group Law Basics)

  • •

    Point Compression (Elliptic Curve X-Coordinate + Parity Bit)

• •

  Python

  • •

    def base_digits(value, base):
        if value == 0: return [0]
        out = []
        while value:
            out.append(value % base); value //= base
        return out[::-1]
    
    def candidates(r1, observed_prefix, P, field_p):
        R, T = r1*P, (1 << 240)*P
        for high in range(1 << 16):
            state = r1 + (high << 240)
            if state >= field_p: continue
            point = R + high*T
            if point.is_zero(): continue
            predicted = int((int(point[0]) * P)[0]) & ((1 << 240) - 1)
            if base_digits(predicted, 37)[:len(observed_prefix)] == observed_prefix:
                yield state
    

◌ Explore connections in Graph view