[Cryptography] The hypothetical random number generator backdoor
Jerry Leichter
leichter at lrw.com
Tue Sep 24 23:01:56 EDT 2013
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
More information about the cryptography
mailing list