[Cryptography] The hypothetical random number generator backdoor

[John Kelsey]

On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker <hallam at gmail.com> wrote:

> So we think there is 'some kind' of backdoor in a random number generator. One question is how the EC math might make that possible. Another is how might the door be opened.

We don't know that there is a backdoor in dual ec, but we know that there could be one of a particular form, and it works like you describe--if you know the backdoor, then given output[i], you can predict all future outputs.  

The other kinds of weaknesses I would expect to see in the wild would be lack of entropy, which means that you can try some reasonable number of guesses about the value of the output and expect to have a decent probability of being right once.  

> Either way, the question is how to stop this side channel attack. One simple way would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. 
> 
> nonce = E (R, k)

This would work if you had a secure key I couldn't guess for k.  If the entropy is really low, though, I would still see duplicate outputs from time to time.  If the RNG has short cycles, this would also show up.

> Or hashing the RNG output and XORing with it 
> 
> nonce = r  XOR H (r)

This works against the dual ec type backdoor, but does nothing for low entropy or short cycles.  Also, it's kind-of sensitive to how H() works.  If H(x) = P(x) xor x then this will be invertible.  Still, the basic idea is nice.  It would be interesting to see if you could prove something about its security.

How about:

nonce = r[1] xor H(r[2])?

The other thing that you can do is to XOR multiple RNGs together.  As long as at least one is unbroken and all other RNGs are independent of that one unbroken one, the resulting random outputs should be secure.  

--John