On Sep 24, 2013, at 6:11 PM, Gerardus Hendricks <[email protected]> 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
_______________________________________________
The cryptography mailing list
[email protected]
http://www.metzdowd.com/mailman/listinfo/cryptography
