[Cryptography] The hypothetical random number generator backdoor

Gerardus Hendricks konfkukor at riseup.net
Tue Sep 24 18:11:17 EDT 2013


> So we think there is 'some kind' of backdoor in a random number
generator.
> One question is how the EC math might make that possible. Another is how
might the door be opened.

I'm assuming you're talking about DUAL_EC_DBRG. Where the backdoor is and
how it can be exploited is pretty simple to explain – if you know your way
around the elliptic curve discrete logarithm problem, which I really
don't. See [0]. Please allow me to stumble up an explanation in an attempt
to learn how this shit works.

In any case, in the algorithm as the NIST specifies it [1], two constants
are used: the generator P of the curve and a specific point on that curve
Q. It hasn't been explained why point Q has been chosen. The potential
backdoor lies in the existence of a constant e so that Q^e = P.
Calculating e, knowing only P and Q, would require solving the discrete
logarithm problem. It is however trivial to generate Q and e together,
just like in any other public-key cryptosystem (with e being the private
key).

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.

If the NSA in fact specially crafted point Q, it would have been the
perfect backdoor for them. Only they had the keys to the kingdom. As long
as the private key remained secret, other attackers wouldn't have any
advantage from the existence of the backdoor.

Would I be correct to say that backdoors with such properties cannot exist
in PRNGs based on symmetric crypto or hashing functions?

> 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.
You also seem to think that evoking random numbers from a system somehow
constitutes a side channel attack. It does not. Pretending that it does
will only lead to security by obscurity (hiding the algorithm).

If you really doubt implementations, instantiate multiple algorithms with
independent seeds and XOR the output together. The combination will be at
least as strong as the strongest individual PRNG (assuming good seeds).
That seems silly as well.

Regards,
Gerard

[0] http://rump2007.cr.yp.to/15-shumow.pdf
[1] http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf






More information about the cryptography mailing list