Nothing Up My Sleeve

This challenge is about the Dual_EC_DRBG random number generator, which is famous for being backdoored by the NSA so they can predict the output after reading only 32 bytes of the random stream.

This excellent video should demonstrate how to generate the point $Q$$Q$ so that we can easily recover the state of the PRNG given that we know the relation of $P=dQ$$P = dQ$, where $d$$d$ is the secret component only known by the NSA. We can make our life easier by setting $d=1$$d = 1$, to make the output of the PRNG to be the next state that the PRNG uses.

The algorithm only returns the last 240 bits (basically truncates the first 16 bits), we have to do some guesswork of the states. The Shumow-Ferguson attack, mentioned by part 5.3 of the original paper about DUAL_EC_DRBG, should provide some insights on how to brute force the most significant 16 bits. Denote the two state, in chronological order that we can observe to be $s_1$$s_1$ and $s_2$$s_2$. We will brute force the most significant 16 bits of $s_1$$s_1$, and for each guess, we generate the next state from the guess, denoted by $s_1^{\prime }$$s'_1$. The correct guess of the most significant 16 bits will occur when $s_1^{\prime }=s_2$$s'_1 = s_2$ (truncated $s_1^{\prime }$$s'_1$ of course).

It takes around 47 spins for a full recovery of the 240 least significant bits of a state output (the 16 most significant bits truncated state). We can do a simple random choice between ODD and EVEN to recover 2 state outputs, and the remaining number of spins should be enough for 1000 points.

Python Implementation:

xxxxxxxxxx
from fastecdsa.curve import P256
from fastecdsa.point import Point
from Crypto.Random import random
from tqdm import tqdm 
from pwn import * 
import json 

io = remote('socket.cryptohack.org', 13387)
print(io.recvline())

class RNG:
    def __init__(self, seed, P, Q):
        self.seed = seed
        self.P = P
        self.Q = Q

    def next(self):
        t = self.seed
        s = (t * self.P).x
        self.seed = s
        r = (s * self.Q).x
        return r & (2**(8 * 30) - 1)

# The point Q sent follows P = Q, for an easier time
send_x = "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"
send_y = "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
to_send = {'x': send_x, 'y': send_y}
io.sendline(json.dumps(to_send).encode())
print(io.recvline())

# Recover the rng outputs from the spins observed
def recover_rng_output(spins):
    state = 0 
    for spin in spins:
        state *= 37
        state += spin
    return state 

# Reconstruct the output from the PRNG, the 240 least significant bits of 
# the RNG used for generating the spins
def reconstruct_rng_outputs():
    shuffle_states = []
    current_shuffle = []
    
    for _ in range(47 * 2):
        # Random choice should be enough for observing the values
        # if failed then restart the script
        pick = random.choice(['ODD', 'EVEN'])
        to_send = {'choice': pick}

        io.sendline(json.dumps(to_send).encode())
        response = json.loads(io.recvline().decode())
        msg = response['msg']
        spin = response['spin']
        current_shuffle.append(spin)
        
        # New set of spins 
        if 'Good evening' in msg:
            shuffle_states.append(current_shuffle)
            current_shuffle = []
        
        # Two states is needed for the recovery
        if len(shuffle_states) == 2:
            break 
    
    return shuffle_states

# Recover the full state of the RNG 
def recover_rng_state():
    outputs = reconstruct_rng_outputs()
    outputs = list(map(lambda x: recover_rng_output(x), outputs))

    # Brute force the MSB 16 bits of the first state observed
    for i in tqdm(range(2 ** 16)):
        # Possible state 
        possible = i * 2 ** 240 + outputs[0]
        send = Point(int(send_x, 16), int(send_y, 16))

        result = send * possible 
        # Comparing the next state generated to the next state output observed 
        if result.x & (2**(8 * 30) - 1) == outputs[1]:
            return possible

# Generate the spins
def rebase(n, b=37):
    if n < b:
        return [n]
    else:
        return [n % b] + rebase(n // b, b)

# The state used for the next batch of spins
state = recover_rng_state()
G = Point(int(send_x, 16), int(send_y, 16))
rng = RNG(state, G, G)

# Generate the next state used for the spins
next_state = rng.next()
spins = rebase(next_state & (2**(8 * 30) - 1))

# There are less than 50 spins left allowed, but too lazy to get
# the correct number of spins left
for _ in range(50):
    # Get the current spin, we go for the juicy 35 point guess
    current_spin = spins.pop()
    to_send = {'choice': current_spin}

    io.sendline(json.dumps(to_send).encode())
    response = json.loads(io.recvline().decode())
    msg = response['msg']

    # If flag is returned 
    if "flag" in msg: 
        print(msg)
        break 
    
    # If there is no spin left in the spins cycle
    if len(spins) == 0:
        next_state = rng.next()
        spins = rebase(next_state & (2**(8 * 30) - 1))