[Cryptography] The hypothetical random number generator backdoor

[Jerry Leichter]

On Sep 24, 2013, at 7:53 PM, Phillip Hallam-Baker wrote:
> There are three ways a RNG can fail
> 
> 1) Insufficient randomness in the input
> 2) Losing randomness as a result of the random transformation
> 3) Leaking bits through an intentional or unintentional side channel
> 
> What I was concerned about in the above was (3).
> 
> I prefer the hashing approaches. While it is possible that there is a matched set of weaknesses, I find that implausible.
Then I'm mystified by your proposal.

If enough bits are leaked to make it possible to feed all possible values of the generated value R into whatever algorithm uses them (and, of course, recognize when you've hit the right one), then the extra cost of instead replacing each such value R with R XOR H(R) is trivial.  No fixed transformation can help here - it's no different from using an RNG with problem 1 and whitening its output:  It now looks strong, but isn't.  (In fact, in terms of "black box" behavior to someone who doesn't know about the limited randomness/internal loss/side channel, these three weaknesses are functionally equivalent - and are subject to exactly the same attacks.)

The encryption approach - replacing R by E(k,R) - helps exactly because the key it uses is unknown to the attacker.  As I said before, this approach is fine, but:  Where does this magic random key come from; and given that you have a way to generate it, why not use that way to generate R directly rather than playing games with code you don't trust?

                                                        -- Jerry