Why use entropy at all in considering password strength?

Question

I don’t understand the password vs. passphrase analyses that I read. Let me explain.

Here is a pass phrase. It has 5 words using only lower case (I’m ignoring randomness for this purpose): friend house jump touch kiss

When I enter that passphrase, it looks like this: ••••••••••••••••••••••••••••. That’s 28 characters. Those analyses (I got most of my info from EFF articles) consider the entries as words, so there are 5 choices out of the 7,776 long wordlist. The hacker knows I am using that list. But what do the words have to do with it? Can the hacker tell where the spaces are? If they can, why use them? One could easily remember a phrase without spaces. Do the spaces count as characters? (I thought they did). Why would you use the words to figure the entropy? What difference does it make whether it’s words or just grouped characters in a random password?

I thought passwords worked like this:

number of possibilities = n^x
where: 
n = the number of character possibilities 
x = the number of characters

In that case, Tr0ub4dor&3 would be (I think it’s 95 keyboard possibilities or so) 95^11.

The password phrase I wrote earlier would be 27^28 possible combinations, which, of course, is much larger. And the fact that they are words is irrelevant, I thought. Using words it would be 7776^5. That is far fewer possibilities than either 95^11 or 27^28. Isn’t it?

EFF recommends 6 words now, and my personal passwords, I thought, had 27^40 possibilities. That’s a lot of guesses.

Why bother with “entropy”? Isn’t it really just a large number of guesses? What am I missing?

Answer 1

You're looking at it just a little bit wrong. Probability can be tricky, so the best way to make sense of it is to simplify. Rather than looking at an ~8000 word list, let's look at the following word list made up entirely from 10 letter words:

california
everything
aboveboard
washington
basketball

There are exactly 5 words on my list with 10 characters each. I make my password by picking 1 word from this list at random:

everything

Consider an attacker that knows that I chose one password from this list. Therefore, What is the maximum number of tries it will take to guess my password? The answer is simple: 5

Sure, there are 26 lowercase letters and my password has 10 characters, so if an attacker didn't know any better and just tried to guess random lower-case letter combinations, they would have 26^10 passwords to try (which is a lot more than 5). That doesn't matter though, because I picked a single word, so someone who knows my word list can guess my password in at most 5 tries.

This is the case because I didn't pick my password by randomly selecting 10 lower case letters. If I had chosen 10 random letters then the number of possible passwords would be 26^10 (and my password would be harder to remember). Instead I picked my password by randomly choosing one word from a list of 5 possibilities. Therefore the number of possible passwords is just 5^1 = 5. If I chose two of these passwords and stuck them together then the number of possible passwords I could have would be 5^2 = 25. It doesn't matter how long the words are, because I'm not choosing letters - I'm choosing words.

Answer 2

You are probably confused by the fact that sometimes you compute entropy using considering all the possible characters, other times you consider words, other times you even consider other different rules.

Entropy is just the amount of "randomness", or "noise" that an attacker cannot know in advance, provided that the source of this entropy is actually a good source. A dice is a good source of entropy if you need a random number from 1 to 6, but if you use an unfair dice then it won't work well.

But does the attacker know how you are actually generating your password? Do they know if you are choosing random characters, if you are including symbols or not, if you are using a word list instead, or what kind of word list you are using (and in what language)? They might know all this information, or they might not. But in information security it is considered bad practice to rely on the secrecy of the methods (as an extension of Kerckhoffs's principle). Therefore you need to assume that an attacker actually knows how you generated your passwords. And all you have left then is entropy.

So if you have chosen random characters, you will calculate the entropy as C^L (C = number of possible characters, L = password length). If you have chosen random words, you will use W^N (W = number of possible words in your list, N = number of chosen words). And if you have chosen a password like Tr0ub4dor&3, the entropy might be less than you think (see this famous xkcd).

As a side note, unfortunately entropy is not really enough to guarantee that a password is secure. For example, if you generate a password totally randomly, it is possible (however unlikely) that you end up generating 12345678. That password would be extremely insecure, no matter if it's actually been generated randomly and you just end up with that ridiculous string because of bad luck. So technically entropy alone is not enough to guarantee that you have a secure password, but you would also need to check it doesn't contain any obvious patterns or it isn't included in any known password lists.

Answer 3

Real-world password strength has very little to do with raw, per-character Shannon entropy (which is about both information and randomness). The insight here is that people compose passwords from "chunks" of information that are much larger than a single character.

Per-character entropy only matters when you are doing one of two things:

1. Assessing the worst-case attack time for passwords that are randomly generated, and you know what length and character composition are; or

2. Assessing the worst-case attack time for passwords that are human generated, that you're not sure how they were generated, and that you know what the length and character composition are.

What raw entropy doesn't cover:

3. Assessing a human-generated password's real-world resistance to expert attacks that are informed by leaked password lists, human psychology of password selection, and overall password-cracking strategies - ones that exploit many non-random patterns long before falling back to brute force.

Since most passwords are human-generated, they will be cracked much sooner than the time that a brute force attack would take, rendering entropy-based password strength assessments useless.

Instead, password crackers do talk about "keyspace" for their attacks - the effective information entropy based on how many pieces of information are in a password. If someone only has to remember four things to reconstruct their password from memory - for example, that it's their kid's name and birthdate, with name capitalized and birthdate as MMDDYYYY - then the attack only has to assemble lists of those four things to crack most such passwords. (For people who have taken psychology classes, this is the "chunking" that we do when memorizing things.)

In other words, at a high level, if you only have four "chunks" of information in your password, than the effective information entropy of your passwords is based on only four discrete pieces of information and the variability in each of those pieces - often much less than the raw, per-character entropy.

But since the "numbers game" of optimizing password-cracking attacks is to crack as many passwords early, as quickly as possible, by assembling these "chunks", quantitative calculation of that entropy can be tricky. It is about the total number of guesses that must be exhausted for the attack.

For some types of passwords, a human can look at them and tell exactly what the person who made the password was thinking, and decompose the password back into its original components. Simple methods can be used to even automate this. But for others, it's difficult for a human to tell what the original method was - let alone trying to automate it enough to perform an automatic calculation of the underlying complexity.

And even if it could be automated, it's also about the attack speed. And such speeds vary widely depending on the demographics of the users, how much they've been educated about password strength, complexity requirements of the target system, the strength of the hash, the attack type, the attack inputs, and the skill and tooling of the attacker.

In other words ... password strength assessment is a non-trivial challenge!

Answer 4

Entropy is not a property of passwords; it's a property of how they were chosen. If you use N random bits to select a password uniformly at random from a list of 2^N candidates, then the password you picked has N bits of entropy by virtue of how it was chosen. It makes no difference how long it is or what characters it uses.

When a password strength checker rates your password as "strong" or "weak", it is guessing the method by which you produced it, and rating the strength of that method, not of the password itself. Guessing well is an AI-hard problem, and the strength checkers in the wild generally are not very sophisticated; they have only a few candidate methods and use only superficial properties of the password to select between them. Humans can do somewhat better.

Take your password Tr0ub4dor&3. This password could have been generated by gluing together 11 independent random printable ASCII characters, or by taking a dictionary word and mutating it in various ways. The first method tends to produce passwords that look like Mc*]Z.-S--r, A=Ek+]/BQzq, $2"*LQ>rMe7, and so forth, while the second method tends to produce passwords that look a lot more like Tr0ub4dor&3, in the subjective judgment of the fairly sophisticated neural net that is my brain. I conclude that it's much more likely that the password was generated by the latter algorithm (with around 28 bits of entropy) than the former (with around 72).

In fact, though, I don't think you used either of those algorithms. I think you got the password from a widely circulated online comic strip. There are only two passwords in that strip, and only one was suitable for your purposes. This method of password selection can only produce Tr0ub4dor&3, so I conclude that it's much more likely that you used this method than the other two. The entropy of this method is 0 bits.

---

Why does entropy matter? Essentially because it gives you a provable upper bound on the risk that your password will be guessed, subject to some reasonable assumptions.

The threat model is an attacker who tries different passwords until one works or until they get bored and give up. The number of passwords they'll try is independent of the password you chose, so you can imagine they just have a fixed list of passwords, try every password on that list, then give up.

If their list has length K, and you select your password randomly from 2^N candidates, and every password on their list is also on yours, then the chance that they'll crack your password is exactly K/2^N. If not every password on their list is on yours, the chance is less than that. The worst(-for-you) case chance is K/2^N.

You could try to guess which passwords are likely to be on their list and avoid them to keep the chance down, but if N is large enough then you don't have to worry about that. You have a fundamental advantage because adding bits to N only linearly increases the difficulty of memorizing and typing the password, but it exponentially decreases the chance that the attacker will be able to guess it. It's better to choose the passwords on your list by ease of memorization. The advantage of correct horse battery staple-style passwords over other styles has nothing to do with their length in characters or likelihood to be tried by attackers, and everything to do with their being easy to remember. (They may also be faster to type, if you're a good typist or you're on a smartphone with a swipe keyboard.) The security of any style of password comes not from any property of the passwords themselves, but solely from the value of N.

How do you know the value of K? You don't, but it's easy to roughly estimate it by assuming that the attackers aren't far ahead of the state of the art in computing technology, and aren't willing to spend more than a certain amount of money and time (a function of how important you are to them) to crack your password.

Answer 5

I do password cracking for customers from time to time (to know whether their employees use good passwords). Here's how I would attack your passphrase or password.

First off, we should assume the key or password is secret, not the method that it was made with (Kerckhoff's principle). I may not know the details, for example which dictionary you used, but I can usually work around those limitations, in this example by using a sufficiently large dictionary. In most organisations passphrases are not common, but recently we found a single passphrase after doing a dictionary attack (a "dictionary" consisting of previously cracked passwords). I followed up on the pattern and it turned out there were more four-word phrases among the sysadmins. Always assume the method is, or will become, known.

So given that I'll probably find out how you generate your passwords, let's see how I would approach an organisation with a mix of various password styles:

1. Try to find standard passwords

Most people choose predictable passwords. One or sometimes two words, uppercase the first letter of each word, numbers at the end, sometimes special characters, often leetspeak. There have been so many attacks on these kinds of passwords that a large dictionary (containing previously cracked passwords) plus some mangling rules is usually sufficient.

Assuming standard (poor) password storage such as Microsoft's hashing scheme, cracking takes a few hours, depending on the mangling rules.

2. Start a brute force attack

After that is done, I usually run a brute force attack for a few hours or days to find any "short" (up to and including 8 characters usually) passwords that the dictionary missed. This usually results in nothing, but sometimes it works and then it's great because the person probably thought they were quite secure by memorizing random characters, so it's often an important password.

3. Analyse the results so far

While the brute force is running, have a closer look at the previous results. Any patterns?

The example I mentioned before was a long password, something like: F4stH0nd4F4stH0nd4. So I found a list of all adjectives (like "fast"), car brands (like "Honda"), made a list of all possible combinations, and fed it to Hashcat with some custom rules:

1. replace "a" with 4 and "o" with 0,
2. uppercase the first letter of each word,
3. then write it twice after each other.

This is not really a passphrase because passphrases are supposed to be random, nonsensical words ("correct horse battery staple"), but it's similar. But let's say I found an actual passphrase, maybe someone actually used correct horse battery staple? Or a real phrase like "MaryHadALittleLamb"? Then I would continue with passphrase cracking.

4. Try to find standard phrases

Similar to how standard dictionaries and previously cracked passwords can be used for cracking more passwords, I can use pre-existing phrases for cracking passphrases. I did some research on this which is available here. In summary, downloading Wikipedia and trying every possible subsentence combination yields good results. A lot of people just use an existing phrase rather than random words, and Wikipedia contains a lot of phrases.

5. Start a passphrase brute force attack

Where step 4 was similar to step 1, this step is similar to step 2, except we now don't try all possible characters but all possible words. Take a reasonably-sized dictionary and just start trying combinations. First two-word combinations, then three-word, and if you have time left then try four-word combinations. A few mangling rules are needed like putting spaces between words or uppercasing the first letter of each word (or a combination thereof).

This is very rare, though, and so this will almost never yield any results. If passphrases become more popular it might become more effective. Or if you have a specific target person (if you work for a security agency) and you observed that they had a long password, this would be a good thing to try.

---

In conclusion, a password or passphrase is only as strong as the method by which you generated it. You can have a strong 16-character random password or a strong 6-word random passphrase, it doesn't really matter. Entropy is a fancy way of saying "number of random guesses needed", and that's all that counts, because each extra character or word adds an exponential amount of guesses necessary and you can easily get to a point where no computer could realistically guess it.

Answer 6

Why bother with “entropy”? Isn’t it really just a large number of guesses? What am I missing?

A Large entropy itself doesn't guaranty the strength of the password, you need to add complexity. For instance if the attacker knows that the system generating the random password allows some patterns like repeating characters, then he would start up with guessing passwords that have repeating characters, which could save him time in a successful attack.

Below image shows a real example of random password that misses complexity