What is the best way to calculate true password entropy for human created passwords?

Question

Okay, I know it might seem this has already been beaten to death but, hear me out. I am including a fairly good password strength algorithm for my app for users on sign-up. This one, which I've copied (with minor adjustments). I also want to give a ROUGH metric in addition to the strength tester. I want to calculate and communicate users' password entropy by cost to crack in the same way 1Password has here. I think this can communicate well to users in a way that is real to them.

Here is a common problem which leads to my question, password entropy. I will give users a switch to flip, whether the password is human-created or machine random. Now machine random has its own set of entropy calculation issues such as whether it is a totally random sequence, is it a symbol-separated word sequence chosen from a 307,111 word list, etc, etc. I've got that covered. The trouble is some human passwords seem stronger than machine crypto random:

Issue with standard password entropy calc methods:

1Password machine random - rmrgKDAyeY = 57.37 bits entropy
Human created non-random - isAwtheSUN = 57.37 bits entropy

Obviously, this would not be a good estimation...

I tried using log(pow(2500, 4))/log(2) => 4 words, 2500 possible combinations based on people using easier-to-remember words, as a percentage of the average human vocabulary of about 20,000 and this gave a resulting entropy of 45.15. This seems pretty reasonable. But I need to hear from the pros and looking for other ideas.

What metrics could be used to calculate human-created passwords so the result is much less secure looking than machine randoms?

Keeping in mind I'm after entropy only so to give users a cost-to-crack estimate. I know nobody but us cares about entropy.

Answer 1

There isn't really a "true" level of entropy for passwords - all you can ever do is estimate. And this is especially true when the only information you have is the password itself.

Imagine a password like RobertAmazonMonday. On the face of it, it's three "random" words, so you can have a guess at the entropy based on your assumptions about the average size of someone's vocabulary. But if that password was set by a guy called Robert on his first (Mon)day working at Amazon, then that completely changes the situation.

So I'd question what the problem is that you're really trying to solve. If it's just giving users an idea of how strong their password is, then taking an approach where you look at length/character set initially and then reduce the strength estimate for strings within it (such as words, common patterns, their username, etc) like existing tools (such as KeePass) do could work.

But is giving them a number sensible here? Does a user care than their password has an estimated entropy of 57.23 bits vs 53.86 bits? Can they make a meaningful decision based on that information? Is the difference between your password taking 500 trillion years and 600 trillion years to crack with some arbitrary work factor (because you're using a decent hashing algorithm) relevant?

Answer 2

I’d suggest you have a look at zxcvbn. It uses a dictionary and identifies common words, other common patterns and common substitutions to provide a fairly good estimation of the entropy of the process that produces the password.

Answer 3

One password does not have entropy. A method to generate a password has entropy.

This is quite clear in the table in the 1Password page you linked to. They give entropy of the method ("3 word, constant separator", "8 char, uppercase, lowercase, digits"...), not the password. The password given is just one example.

So if the method is "15 characters picked randomly from a set of 72 values" (upper and lower basic latin letters + 10 digits + 10 symbols), then the entropy is 92.55 bits. Whether one actual result generated this way ends up being abcdefghiklmno or something that looks truly random, the entropy is the same (for a brute force crack, which is what entropy is about, abcdefghiklmno is as random as any other password).

From a password, you can try to guess how it was generated. So if you see 15 lowercase letters, you can estimate the method to be "10 characters picked randomly from a set of 26 values", and the entropy to be 70.5 bits. If you detect uppercase letters, or digits, or symbols, you'll change your estimate of what the method is, and what the associated entropy is. But the password does not have entropy. The method to generate it has.

But your guess is just a guess. Maybe the password was actually generated as a set of three 5-letter words taken from a list of 1000 words. Entropy 29.9 bits. Or a set of three 5-letter words taken from a list of 100 000 words (entropy 49.83 bits). Or anything else.

Or, more likely than not, the password was generated from a limited set of words and numbers. Say, some significant name (spouse, children, company...), some significant number (date of birth, of marriage...), a random special character thrown in there, a random character uppercased, and a few possible permutations (name+number+symbol or name+symbol+number, etc.). If you know the user, entropy is probably less than 10 bits. If you don't know the user, then it does increase, but remains quite low (I'd think less than 40 bits).

That's why people do dictionary attacks rather than brute force attacks. Because most people don't generate random passwords.

So no, you cannot determine the entropy from a single password. You can make guesses, but that's about it.

First things first:

• If you can avoid having to deal with any passwords yourself, do so! Rely on some other platform for authentication. Make it their problem.

• Check passwords against the top-whatever list of most common passwords.

• Check password hashes against known password leaks.

• Make sure the password is long enough.

I don't think much else really makes a difference, and can be counterproductive.

Answer 4

The true level of entropy depends on the probability that the attacker will consider a given password. Since nobody knows in advance how the attacker acts, this level cannot be reliably known.

1. if the attacker brute-forces by iterating through all characters, both passwords have equal entropy.
2. if the attacker uses a dictionary and combines words/characters into a password (trying longer words first), then isAwtheSUN will have a lower entropy that rmrgKDAyeY.
3. if the attacker uses a password list, the entropy will depend on whether either rmrgKDAyeY or isAwtheSUN are part of the list, and their position. It's even perfectly possible that rmrgKDAyeY has lower entropy than isAwtheSUN.

The character count corresponds to the entropy for the approach #1. Modern brute-force techniques are relying on approaches #2 and #3, so it's commonly considered that character count is a poor entropy metric, and an entropy calculation based on on #2 gives more plausible results.

Still, it's important to understand that any password entropy metric remains an estimation, and its "quality" may change at any moment. It's possible that once quantum computers become available to password crackers, the metric based on character count will once again become "state of the art".

Answer 5

As noted by others, passwords don't individually "have entropy". Entropy is a property of their relationship to a larger distribution of password choices, possibly through a method by which they were generated.

Conceptually, the "best" way to measure entropy of passwords is with an optimized compression algorithm (which is largely a matter of an optimized dictionary) that best compresses the passwords "known to be weak" (known to appear widely). You could approximate something like this using existing known sets of compromised passwords, natural language dictionaries, and advanced statistical modeling (aka "AI" language models) of relationships between words. Then, the number of bits in the compressed version of a given password might be a reasonable estimate of "its entropy".

However, even then, it will not tell you whether there are external correlations between the password and its owner, the context in which it's used, etc. that reduce the real effective entropy an attacker would be working with.

Answer 6

Your password would have entropy relative to a password guesser. You could just say that if guesser X guesses your password in 2^n attempts, you could say you have n bits entropy relative to that guesser. You could implement several password guessers and try them all.

A problem is that if your entropy is high, then guessing the right password will take a long time. If it takes you an hour to find the entropy of a password that a guesser takes an hour to crack, that's not too useful. However, you have a huge advantage: You know the password. So if you know for example that the password guesser will now guess 123,456,789 eight letter passwords, and your's is nine letters, you don't have to actually try those 123 million passwords. And if your password started with K, you can likewise skip testing all the nine letter passwords starting with A to J. So you might be able to determine very quickly how many attempts it takes your password, given that you know it.

In addition, entropy is one thing. The time it takes to try whether a password guess is correct is another thing. For example, iOS passcodes supposedly take 80ms to test one passcode. A six digit passcode would. take up to almost a day to crack.