1

I have gained interest in creating a way to check password strength (think password strength meters - yes - another one). I've found many ways to award a score on a policy driven approach (one capital, special character - you get it), but I've also begun to look into string entropy. Specifically, I've found this JavaScript implementation of Shannon entropy

In their example, "1223334444" awards 1.8464393446710154 in bits of entropy per character. I assume, then, the entropy for the string is the character count multiplied by the length - then being 18.464393446710154

My question is, though, in real-world terms, what does this value mean? Is it decent? poor? Where does the poor/decent/strong acceptability rate begin and end for values such as this? Likewise, whats considered "overkill" for an acceptable user expectation?

scniro
  • 205
  • 2
  • 5
  • 2
    Per-character Shannon entropy is going to be a very poor measure of password complexity. Using the same algorithm, I get an entropy of 2.75 bits per character for "password", or a total entropy of 22 bits. That implies that it would take 2^22 = 4194304 guesses to crack; in reality, the number of guesses for "password" will usually be in the low single digits. – Soron Oct 23 '15 at 04:50
  • My KeePass password are usually 200+ bits of entropy... – Freedo Oct 23 '15 at 06:20

2 Answers2

4

As I understand it, the amount of entropy in a password represents the number of guesses required to know what that password is. Each bit is a single yes-or-no decision, and ideally, the attacker would either get a "correct password" or "incorrect password" result (so, they have to guess the whole thing, all at once). For n bits of entropy, that requires 2^n guesses.

The desired strength depends on what sort of threat you expect to face. In particular, it depends on how fast the attacker can make guesses, and how long you expect the attacker to keep trying.

Once you have those numbers, your target minimum entropy (in bits) should be:

n = log_2(totalGuesses) = log_2(guesses/sec * durationInSeconds)

The persistence of the attacker is something which I don't know how to estimate. For the sake of argument, let's assume that you want your password to be secure for 1 week after the attacker starts guessing.

Number of guesses per second depends on how the password is protected, and what sort of access the attacker has. For an online attack (i.e., trying the login form of a website), you could rate-limit it to a fairly low value; 10 per second would be achievable. For unsalted MD5, it's safer to assume billions of guesses per second. For a strong hashing algorithm like bcrypt, it will be somewhere in-between (MUCH slower than MD5, in any case).

So, at 1 billion hashes per second (offline MD5 cracking), you would need to defend against about 6*10^14 guesses total, requiring about 49 bits of entropy. At 10 guesses per second (online, rate-limited attack), you need to defend against about 6*10^6 guesses, so you need about 22. bits of entropy.

Of course, per-character estimates of Shannon entropy will not accurately estimate the difficulty of cracking a password, and the percentage error will vary wildly depending on various factors. The approach you're taking will only give reasonably accurate results for computer-generated passwords, NOT for human-generated passwords.

Soron
  • 2,809
  • 1
  • 12
  • 19
  • Excellent explanation, thank you. Would you have any good resources where to find a formula to "estimate" strength of a human generated password? – scniro Oct 23 '15 at 13:29
  • Not specifically, but I think a good starting point could be password cracking techniques, such as described [here](http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/2/). Unfortunately, that's as much art as science, and I don't know of any good, fast algorithms for estimating how many guesses would be needed by someone who knows what they're doing (and remember, you have to defend against _clever_ humans, with a static entropy estimation algorithm). – Soron Oct 24 '15 at 11:27
  • If you really want a good entropy estimation using arbitrary human-generated passwords, I would recommend asking that as a separate question, or checking to see if it's been asked already. I see some other answers which allude to [how not to check entropy](http://security.stackexchange.com/a/73385/80588), but I don't know of any that provide a good way to estimate the entropy of an _arbitrary_ human-generated password. I think the question is worth asking, although it might be that nobody knows an answer. – Soron Oct 24 '15 at 11:35
1

This NIST recommendation is 80 bits of entropy for passwords.

At 350 billion guesses/sec, such a password will take a maximum of 109,528 Years to crack, 54,764 years on average.

Although you can ensure your own passwords are of such a strength, you can only guide your users to select such a password.

Password strength checkers such as zxcvbn can help, however these are only as good as their preloaded word lists, or checking methods (such as Shannon Entropy). In a targeted attack, it may already be known that the password generation method is a non-standard method only used by the victim. In that case, password strength meters cannot help - the entropy here is based upon the number of possibilities that that particular method can encode, and not those that the password strength meter is based upon.

Community
  • 1
SilverlightFox
  • 33,698
  • 6
  • 69
  • 185