- 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…

Advertisements

Well done. You should probably say “The RSA (the Algorithm, not the Company) Equivalent Of The NSA’s Dual_EC_DRBG Algorithm” otherwise it is confusing.