PoC in Python for Dual_EC_DRBG Backdoor

backdoor_poc.py

import time
from pwn import log
from random import randint
from fastecdsa.curve import P256
from fastecdsa.point import Point


""" UTIL FUNCTIONS """
def mod_inv(a, m): # For prime number m
    return pow(a, m-2, m)

def p256_mod_sqrt(z): # Based on the identity: when p = 3 (mod 4)
    return pow(z, (P256.p + 1) // 4, P256.p)

class Dual_EC_DRBG(object):
    def __init__(self, seed):
        self.seed = seed
        #Use the generator point specified in the standard
        self.P = P256.G
        self.backdoor()

    def backdoor(self):
        # Pick a random number between that in is in the set E
        self.d = randint(2, P256.q)
        # Calculate the inverse mod and generate our Q from P
        # We do this to perform Elliptic Cuve multiplication using regular algebra
        # This is the value that allows the backdoor and that the attacker knows
        e = mod_inv(self.d, P256.q)
        self.Q = e * self.P
        log.info("Generated point Q: \n"+str(self.Q))
        log.info("Hidden relationship Q=P*d with d: "+str(self.d))

    def gen(self, seed=None):
        if seed == None:
            seed = self.seed
        # Calculate r which will also be the next seed
        r = (seed * self.P).x
        # Get the pseudo-random number generated by the curve
        x = (r * self.Q).x
        # LSB
        return x & (2**(8 * 30) - 1), r

    def update(self, seed):
        self.seed = seed

# This checks if the x_coordinate corresponds to a valid Y on the curve
def valid_point(x_coordinate):
    # y^2 = x^3 - Ax + B (mod p)
    y_2 = ((x_coordinate**3) - (3 * x_coordinate) + P256.b) % P256.p
    y = p256_mod_sqrt(y_2)

    # Check mod_sqrt function fit the function and got the right y
    if y_2 == y**2 % P256.p:
        return y
    else:
        return False

# The attacker has the two intercepted Xs, the secret d backdoor and
# obviously the public Q
def brute(intercepted, d, Q):
    possible_points = []
    # If the 2 bytes generated are the same as the one intercepted
    # we have the correct state
    check = intercepted & 0xffff
    bits = 2**16
    progress = log.progress("Bruteforcing "+str(bits)+" possibilites")
    start = time.time()
    for lsb in range(bits):
        # Reconstruct lsb that were discarded
        output = (lsb << (8 * 30)) | (intercepted >> (8 * 2))
        y = valid_point(output)
        if y:
            # Check if values actually fit
            try:
                point = Point(output, y, curve=P256)
                s = (d * point).x # Calculate possible state
                val = (s * Q).x & (2**(8 * 30) - 1) # Derive possible x
                possible_points.append(point)
                if check == (val >> (8 * 28)):
                    # Got the predicted x and the predicted state
                    progress.success("Took "+str(time.time()-start)+"s")
                    return val & (2**(8 * 28) - 1), s, possible_points
            except:
                continue
        else:
            continue

    progress.failure("Took "+str(time.time()-start)+"s")
    return None, None, None


if __name__ == '__main__':
    s = 0x1fc95ca948ecc306 # Original state of the system, generated arbitrarely
    E = Dual_EC_DRBG(s)
    our_x, new_state = E.gen()
    log.success("Got pseudo random number: "+str(our_x))
    E.update(new_state)
    log.success("Updated state "+str(s)+" -> "+str(E.seed))
    input()
    # Now the user has generated a random number and updated the state
    # using the new r. The user sent the x (for example the Nonce in TLS)
    # This x gets intercepted by an attacker, this would not mean anything
    # but he is aware of the value of d (e is mod_inv of d) in the backdoor
    new_x, third_state = E.gen()
    log.success("Generated second pseudo random number: "+str(new_x))
    log.info("New state: "+str(third_state))
    input()
    # The attacker now has two random numbers generated, now he can try and
    # find out what the state was to prediuct the next state and thus the next x
    observed = (our_x << (2 * 8)) | (new_x >> (28 * 8))
    _, attacker_state, points = brute(observed, E.d, E.Q)
    if attacker_state != None:
        log.warning("Attacker derivated the internal state!")
        print("State predicted: "+str(attacker_state))
        input()
        # The user now, unaware, generates his new number using the state
        # which was predicted by the attacker. If the attack was successful
        # the X predicted will be the same as the one from the attacker
        E.update(third_state)
        user_x, _ = E.gen()
        log.info("User generated: "+str(user_x))
        attacker_x, _ = E.gen(seed=attacker_state)
        log.info("Attacker generated: "+str(attacker_x))