Attacks on keys generated with low entropy

Question

If I were to give someone a two 4096 bits keys, and say one was generated in a Linux OS with very very low entropy available, and one was generated in a Linux OS with more than enough entropy.

Would be possible to differentiate between the two? Would be them be able to do any kind of attack on the low entropy generated key?

I ask this mainly because I often generate a lot of 4096 bits keys/certificates/DH parameters and more on VM's and my little knowledge of this is that I want a lot of available entropy to use because it makes more harder to predict things.

I did some search on why randomness is important and I found a blog article (Why secure systems require random numbers) which tries to explain why randomness matter and describes a hack of the popular programming and technology website Hacker News:

And all pseudo-random number generators need to start somewhere; they need to be seeded and that's where Hacker News failed. The random number generator was seeded with the time in milliseconds when the Hacker News software was last started. By some careful work, the attacker managed to make Hacker News crash and could then predict when it restarted within a window of about one minute. From it he was able to predict the unique IDs assigned to users as they logged in and could, therefore, impersonate them.

Ok I get that, but doesn't this still need the attacker to make a active attack instead of just passive attacks? I mean you couldn't get a stream of someones traffic and says "Hey this Diffie-Hellman parameters/SSH keys appear to be generated with low entropy so lets attack them", right?

So lets say I've just generated a key or something else with low entropy, but the attacker is not able to launch an active attack and currently does not know which randomly chosen pre-master secret has been used, so what?

I still don't feel I'm being able to really express what I'm saying so I'm going to add this one more example :

Here's part of how a computer using WiFi establishes a secure connection to an access point using the popular WPA2 protocol:

• The access point generates a random nonce and sends it to the computer.
• The computer generates a random nonce and sends it to the access point.
• The access point and the computer continue on from there using those random nonce values to secure the connection.

Ok that's fine. Says I'm MITM you and passively watching the traffic, and it happened that the router had ran out of entropy, so what? How could I somehow know this to even think about launching an attack to cause a new handshake and from them try to predict the random nonce used and thus defeat the encryption?

If the answer is " you can't " like I think, why then it even matters? This wouldn't be the first attack anyone would try unless they could know that a low entropy source was used like they knew on Hacker News event.

Also feel free to edit my title if you can come up with a better title lol.

Answer 1

Entropy will basically define the maximum number of different states you random number generator may have at a given moment (more information on the subject can be found here). The higher the entropy is, the higher possibilities there are.

The main problem with low entropy is that the random number generator will have less different possible states to switch over, therefore it will begin to repeat itself.

The main way to detect such issue is to try to detect such repetition. A common issue for instance may affect session ID: an attacker may request a lot of session ID from the server (or nonce from the AP in the case of the Wifi access - did someone talked about WEP?) and analyse if the server can be tricked into generating the same ID twice. If another flaw allows it, he can also cause several quick application restart to analyse the first ID generated.

A very good, historical example of entropy issue affects Debian (and its numerous derivative). During two years, they broke Open-SSL random number generator limiting the ssh-keygen command (used among other thing to generate keys used to authenticate people on servers and authenticate the server itself to avoid Man-in-the-Middle attacks) to 32 767 different keys. As a result of this:

• A server affected by this issue could be immediately identified since he will present the public part of one of these vulnerable key to authenticate itself: the private par being known by the attacker a wide range of attacks become available,
• If one user uses such vulnerable key to authenticate itself (the server itself does not need to be vulnerable), an attacker could gain access to his account just by trying each key from the set which should be relatively fast.

As a final word, you must not rely on the fact that low entropy "looks like" good entropy and that you do not know yet a way to detect it. This is called security through obscurity and it does not bring any good security. Indeed, the fact that you do not know such a way do not mean that nobody else does, and if one single attacker does the consequences could be catastrophic (I guess WEP people initially considered their system to be secure...).

For your concerns regarding VM's entropy, you may be interested in this discussion. Basically, a simple yet efficient fix consists in "seeding each VM with a seed obtained from some other random source elsewhere; this is as easy as writing some file into /dev/random" (quoted from Thomas Pornin's answer).