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.

  • To clarify, are you mainly interested in low entropy keys used in encryption schemes (and inferring / exploiting this based on ciphertexts that you see), or low entropy seeds used in CSPRNGs (and inferring / exploiting this based on random numbers the target is generating), or both? – puzzlepalace Jul 23 '15 at 7:12
  • Entropy in terms of passwords means "how hard is it to guess this password (or whatever)". In a stream of traffic, someone eavesdropping would not know which string has low entropy and which one has high entropy, but if they are decrypting everything some things (the ones with low entropy) would show up quicker. See security.stackexchange.com/a/21147 – Purefan Jul 23 '15 at 7:15
  • @puzzlepalace Both. My reasoning was that since a attacker cannot know if was used a low entropy source to generate e.g ssh keys/dh parameters why it matter? Why would anyone try this attack ? And all those attacks are only possible via active attacks and not passively watching the traffic? – Freedo Jul 23 '15 at 7:27
  • @Purefan i know about entropy on passwords when i say "keys" is SSH keys/certificate private keys/etc. Hope I made my question clearer – Freedo Jul 23 '15 at 7:30
  • @Freedom In the case of someone only passively watching network traffic: if a CSPRNG has a low entropy seed it will still produce output indistinguishable from random which reveals nothing about the entropy of the seed. Same with a secure encryption scheme, the ciphertext will not leak information about the key. – puzzlepalace Jul 23 '15 at 7:44
up vote 6 down vote accepted

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).

  • Then usually attackers can guess that a low entropy is being used by making the server keep sending a "secret" and then see if they get the same numbers ? But how would this apply to say a key or something else that is only generated once, and the attacker cannot force you to regenerate it ? – Freedo Jul 23 '15 at 17:45
  • @Freedom: As mentioned by puzzlepalace, "if a CSPRNG has a low entropy seed it will still produce output indistinguishable from random". This means that given a single key, you have no direct mean to conclude whether it has been generated using enough entropy or not. That's why Debian's issue went unnoticed during so long. And that's also why, while it could be tempting to use keys which "look" random, I advise to be on the safe-side and take appropriate measures to ensure that the keys are really random. You know, Murphy's law and stuff... – WhiteWinterWolf Jul 23 '15 at 19:11
  • Ok thanks . Do you know if different unix offer more secure implementations? If yes which? I use OpenBSD because i feel its safer – Freedo Jul 23 '15 at 21:42
  • The mains issues I encountered regarding UNIX OS provided PRNG mainly concerns: A) The lack of mixed sources (ie. when the OS trust too much some sources, Theo de Raadt was quite offensive against FreeBSD trusting too much CPU provided RNG). B) Denial-Of-Service caused by the OS locking the PRNG device (Linux implementation of /dev/random). So, all-in-all, OpenBSD PRNG implementation seems to be sane and fine :). – WhiteWinterWolf Jul 24 '15 at 8:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.