How can a poor RNG impact security?

Question

I have read this article and I do somehow "understand" that the reduction of entropy makes it easier to guess.

But how exactly can the security be reduced by that? Can you give a concrete scenario, where a poor (P)RNG leads to security issues?

Answer 1

Suppose that you generate a brand new RSA key pair, that you will use, say, to authenticate yourself when connecting to a SSH server. This will be done through some library that implements RSA key pair generation (say, OpenSSL). That library will produce the key elements by generating random integers of the right length until such integers appear to be prime number.

The random generation uses a seed obtained from "true randomness" and then expanded into an arbitrarily long sequence of random bits with a cryptographically secure PRNG. The point is to make it infeasible for an attacker to predict the bits you came up with.

Now suppose that the seed is of low entropy (e.g. 40 bits) or the PRNG is poorly designed and reduces the entropy. Saying "40 bits entropy" more or less means "there are only 2⁴⁰ possible values for the seed or internal PRNG state". Take note that in the synthetic description above, the conversion from seed to generated private key is completely deterministic. Thus, an attacker can generate all these 2⁴⁰ states, and, for each of them, work out the private key that your application would have come up with, starting with that seed value. It then suffices for the attacker to check these keys against your public key (which is public, as the name says) to learn your private key. And impersonate you. Which is bad.

This actually happened in Debian in 2008 and people had to regenerate new SSH keys (both client and server).

Answer 2

The 2012 paper: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices.

In this case the RNG itself was ok, but poor (ie predictable) entropy was used to seed it. The abstract opens:

RSA and DSA can fail catastrophically when used with malfunctioning random number generators.

So that seems to fit your question. The authors did a survey of SSL/TLS servers on the open internet and found that

0.75% of TLS certificates share keys due to insufficient entropy during key generation, ... Even more alarmingly, we are able to obtain RSA private keys for 0.50% of TLS hosts and 0.03% of SSH hosts, because their public keys shared nontrivial common factors due to entropy problems, and DSA private keys for 1.03% of SSH hosts, because of insufficient signature randomness.

Their guess is that most of these vulnerable devices are headless embedded devices that are generating keys on first boot using basically only the entropy (seed values) they came out of the factory with.