• Let’s pretend I am the NSA
• Let’s pretend I wanted to influence or trick NIST along with the RSA (the organization, not the algorithm!) into approving:
• A new, very slow! (slow means good right?), secretly backdoored, non-obvious, non-provable, plausibly deniable PRNG standard
• Let’s also make it part of a mandatory suite so that it *must* be implemented in any software that’s requesting standards approval
• I would probably want this standard to be based on a common asymmetric encryption algorithm, say RSA, so that it appears normal and good

 

• First, I would calculate the following components in secret (and obviously with much larger, stronger numbers so that no one else can break our private key)

p=241 ; q=251
n = (p * q) ; n
phi = ((p - 1) * (q - 1)) ; phi
e = 239 ; n % e ; phi % e
print("http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+"+str(e)+"+mod+"+str(phi)+" # obviously we must do this step in private locally but I'm too lazy to implement the math...")
d = 38159 ; (e * d) % phi

• Then I declare the following algorithm and constants to be used publicly:

 

Define TwoBit_RSA_PRNG (or Dual_RSA_PRNG, sound familiar? :):

Defined Constants:

    let e be the prime integer used for exponentiation
    let n be the prime integer used as the modulus
    let ^ represent the exponentiation operator
    let % represent the modulus operator
    let & represent the binary AND operator
    let + represent the addition operator

Pseudo Code:

import sys
def powmod(a, b, c):
    return ((a ^ b) % c)
def Dual_RSA_PRNG(seed, init):
    e = 239;# Magic!
    n = 60491;# Magic!
    init = (init & 0xFFF)
    return powmod((seed + init), e, n)
def main(a, b):
    s = a
    r = Dual_RSA_PRNG(s, b)
    for x in range(0, 9):
        r = Dual_RSA_PRNG(s, r)
        sys.stdout.write(str(r)+" ")
    sys.stdout.write("\n")
main(int(sys.argv[1]), int(sys.argv[2]))

• Example Output:

main(31337, 0) = 41308 34055 21755 59599 44528 47001 55179 46730 24863

• So what does the above mean?
• The output bytes above appear to be random and even acquiring them doesn’t leak the next set of bytes, assuming the seed stays secret
• One should not be able to break the private key, assuming it is large and secure enough
• Even if someone discovers the private key, they still cannot prove that we have the key, assuming we keep it secret
• With the private key, we can determine the seed and predict the future stream of random bytes with a small amount of the random output

 

PRNG Predicition Python Code:

import sys
def predict(out0, out1):
    e = 239;# Magic!
    n = 60491;# Magic!
    d = 38159;# Private!
    b0 = (out0 & 0xFFF) ; b0
    b1 = ((out1 ** d) % n) ; b1
    s = (b1 - b0)
    print("Discovered seed: "+str(s))
    r = out1
    sys.stdout.write("PRNG prediction: ")
    for x in range(0, 9):
        r = (((s + (r & 0xFFF)) ** e) % n)
        sys.stdout.write(str(r)+" ")
    sys.stdout.write("\n")
predict(int(sys.argv[1]), int(sys.argv[2]))

$ python break.py 59599 44528
Discovered seed: 31337
PRNG prediction: 47001 55179 46730 24863 51524 37767 31388 49000 137

• And now we can continue the original PRNG to see what “random” output would come next:

main(31337, 59599) = 47001 55179 46730 24863 51524 37767 31388 49000 137

 

Conclusion: And that folks is how great Dual_EC_DRBG is! We are paying these people millions in tax payer dollars to come up with these garbage algorithms practically equivalent to the one above. It’s kind of saddening to see…