[Cryptography] The hypothetical random number generator backdoor

[Jerry Leichter]

On Sep 24, 2013, at 6:11 PM, Gerardus Hendricks <konfkukor at riseup.net> wrote:
> I'm assuming you're talking about DUAL_EC_DBRG. ... According to the researchers from Microsoft, exploiting this would require
> at most 32 bytes of the PRNG output to reveal the internal state, thus
> revealing all random numbers generated with the same instantiation of the
> PRNG from that moment on.  Would I be correct to say that backdoors with such properties cannot exist in PRNGs based on symmetric crypto or hashing functions?
Well, that depends on how they are used and what you believe about the primitives.

If you use encryption in counter mode - E(k,counter), where k is random - then the assumption that the generated values are random is, as I remarked in another comment, pretty much equivalent to the indistinguishability assumptions that are commonly made about symmetric cryptographic algorithms.  If you don't think you have an appropriately secure symmetric cipher to work with ... it's not clear just what you're going to *do* with your random numbers anyway.

It's harder to know what to make of hashing approaches because it depends on the hash algorithm and what you believe about *it*.  For most uses, a cryptographic hash function just has to prevent first- and second-preimage attacks.  If that's all you are willing to assume your hash function provides, it's enough for the standard, intended uses of such hashes, but not enough to prove much more.  (For example, nothing in these two assumptions, on its own, says that the hash function can't always produce an output whose first bit is 0.)  People generally do assume more, but you really have to be explicit.

>> 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.
> 
> That seems silly. You are just shifting the responsibility from the PRNG
> to the cipher and its (random) key/seed. In any case, the result is just a
> new, needlessly complex PRNG, since you might just as well encrypt zeroes.
Indeed - though you could safely reuse the random key in counter mode up to some limit determined by the security guarantees of the cipher, and if the encryption function lives up to its guarantees, you'll still be secure.  "Stretching" a short random key into a long effectively random sequence is exactly what symmetric encryption functions *do*!
                                                        -- Jerry