Dual_EC_DRBG backdoor: a proof of concept

SSL certificates can be revoked.

Here's an example in Sage, if the verbosity of OpenSSL code annoys you as much as it does me:

    n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    p = 2^256 - 2^224 + 2^192  + 2^96 - 1
    a = -3
    b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
    E = EllipticCurve(GF(p), [a,b])
    P = E(48439561293906451759052585252797914202762949526041747995844080717082404635286, 
          36134250956749795798585127919587881956611106672985015071877198253568414405109)
    """
    Q = E(91120319633256209954638481795610364441930342474826146651283703640232629993874, 
          80764272623998874743522585409326200078679332703816718187804498579075161456710)
    """
    e = 0x12345678
    ei = inverse_mod(e, n)
    Q = e*P

    def to_bin(x): return ("%060x" % x).decode('hex')

    def from_bin(x): return int(x.encode('hex'), 16)

    def dual_ec_drbg(s, len):
        out = ''
        for i in range(0, len, 30):
            x, y = (s*P).xy()
            s = Integer(x)
            x, y = (s*Q).xy()
            r = Integer(x) % 2**240
            out += to_bin(r)
        return out[0:len]

    def recover_s(s0, s1):
        for i in range(2**16):  # For all possible 256-bit x
            r = i*2**240 + s0   # 
            if E.is_x_coord(r): # is valid x?
                R = E.lift_x(r) # Lift it to a point
                x, y = (R*ei).xy() # Undo s*Q
                s = Integer(x)
                x, y = (s*Q).xy() # Check if it matches next observed block
                if (Integer(x) % 2**240) == s1: 
                    return s # done
        return None

    import os
    # Get 3 blocks: 2 are for the break, the other to confirm prediction
    s = dual_ec_drbg(from_bin(os.urandom(16)), 30*3)
    s0 = from_bin(s[ 0:30])
    s1 = from_bin(s[30:60])
    s2 = from_bin(s[60:90])
    # Recover internal state
    s = recover_s(s0, s1)
    # Now try predicting something
    t = dual_ec_drbg(s, 30)
    assert( from_bin(t) == s2 )
    print "Done"

TLS provides forward secrecy though, so leaking the SSL keys doesn't mean anything for those exabytes of recorded transactions the NSA is presumably saving for a rainy day. If the secret keys for the default Dual_EC_DRBG configuration are leaked, aren't there more serious implications?

Dual_EC_DRBG is a pseudo random number generator, so if it's compromised you could use the internal state to recreate the sequence of pseudo random digits from that point forward. SSL/TLS is protocol which incorporates a suite of algorithms for authentication, key exchange and encryption. So on that level, like the sibling comment mentions, they aren't really comparable. The part of the SSL/TLS protocol that really depends on the certificate is the authentication, though - Diffie Helmann can be done in the clear without compromising its security, and once you've established the key any algorithm can be used to encrypt. When you revoke a certificate, you're essentially saying that you suspect someone else may be able impersonate you on the internet, so don't trust anyone authenticating with it. The algorithm is secure, but the certificate is not.

The point I was trying to make is that if you suspect someone has compromised your certificate, you can revoke it to reestablish secure communications. If you suspect your random number generator has been compromised, you can likewise just change the configuration (assuming it's not hardcoded into some piece of cryptographic equipment).