[Cryptography] The hypothetical random number generator backdoor

Jerry Leichter leichter at lrw.com
Tue Sep 24 10:59:42 EDT 2013

On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker <hallam at gmail.com> wrote:
> I was thinking about this and it occurred to me that it is fairly easy to get a public SSL server to provide a client with a session key - just ask to start a session.
> Which suggests that maybe the backdoor [for an NSA-spiked random number generator] is of the form that ... you get a lot of nonces [maybe just one] from the random number generator ... and that allows the [next one to be predicted more easily or even the] seed to be unearthed.  One simple way [to stop this] would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. 
> nonce = E (R, k)
> Or hashing the RNG output and XORing with it 
> nonce = R  XOR H(R)
You shifted from "random value" to "nonce".  Given the severe effects on security that using a "nonce" - a value that is simply never repeated in a given cryptographic context; it may be predictable, even fixed - to a "random value", one needs to be careful about the language.  (There's another layer as well, partly captured by "unpredictable value" but not really:  Is it a value that we must plan on the adversary learning at some point, even though he couldn't predict it up front, or must it remain secret?  The random values in PFS are only effective in providing forward security if they remain secret forever.)

Anyway, everything you are talking about here is *supposed* to be a random value.  Using E(R,k) is a slightly complicated way of using a standard PRNG:  The output of a block cipher in counter mode.  Given (a) the security of the encryption under standard assumptions; (b) the secrecy and randomness of k; the result is a good PRNG.  (In fact, this is pretty much exactly one of the Indistinguishability assumptions.  There are subtly different forms of those around, but typically the randomness of input is irrelevant - these are semantic security assumptions so knowing something about the input can't help you.)  Putting R in there can't hurt, and if the way you got R really is random then even if k leaks or E turns out to be weak, you're still safe.  However ... where does k come from?  To be able to use any of the properties of E, k itself must be chosen at random.  If you use the same generator as way use to find R, it's not clear that this is much stronger than R itself.  If you have some assured way of getting a random k - why not use it for R itself?  (This might be worth it if you can generate a k you believe in but only at a much lower rate than you can generate an R directly.  Then you can "stretch" k over a number of R values.  But I'd really think long and hard about what you're assuming about the various components.)

BTW, one thing you *must not* do is have k and the session key relate to each other in any simple way.

For hash and XOR ... no standard property of any hash function tells you anything about the properties of R XOR H(R).  Granted, for the hash functions we generally use, it probably has about the same properties; but it won't have any more than that.  (If you look at the structure of classic iterated hashes, the last thing H did was compute S = S + R(S), where S was the internal state and R was the round function.  Since R is usually invertible, this is the only step that actually makes the whole thing non-invertible.  Your more-or-less repetition of the same operation probably neither helps more hinders.)

At least if we assume the standard properties, it's hard to get R from H(R) - but an attacker in a position to try a large but (to him) tractable number of guesses for R can readily check them all.  Using R XOR H(R) makes it no harder for him to try that brute force search.  I much prefer the encryption approach.

                                                        -- Jerry

More information about the cryptography mailing list