How was the concept of password entropy developed?

Question

I understand how to calculate password entropy and what the Length and Character values represent. I also have a reasonable understanding of other types of entropy (e.g. Shannon). However, password entropy seems to be considerably different (in form) than other types of entropy; a simple log₂(D) where D is a difficulty or complexity metric. I'd like to understand how the concept of password entropy was developed to understand other applications of this entropy form.

Does password entropy satisfy the requirements of other types of entropy: additive, linear, etc. For a stupidly simple example, if my system requires two passwords, can I just add the entropy of each password?

EDIT: I've clearly not phrased this question very well. My apologies. Let me try again from a more cyber security perspective: We can define the size of the information H₀(A) in a set A as the number of bits that is necessary to encode each element of A separately, i.e. H₀(A) = log₂|A|. Now let A be the information needed to defeat a protection system on device. For a password, the size set A (and hence the size of the information H₀(A) ) can quantified in a straightforward manner, N^L. I'm trying to get some insight into situations where the size of A is not so easily quantifiable, but I have some metric that captures the set of information, say 'B'. What are the arguments against using H₀(B) = log₂(B) to quantify the size of information needed to defeat the protection system? Again, my apologies for a poorly worded question.

Answer 1

Entropy in physics and in information science is just the logarithm (typically natural log in physics; base-2 log in computer science) of the number of equally likely possibilities, because it's generally easier to deal and think about with the logarithm of these exceptionally large number of possibilities than the possibilities directly.

If I randomly generated 128-bit as my random AES-128 key (that I store somewhere), it's easy to see there are 2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456 possible keys I could have used (2 equally-likely choices for each bit; and probabilities multiply). When talking about informational complexity, it's just simpler to talk about the key having 128-bits of entropy than saying about 340 x 10³⁶ or 340 undecillion (short scale), especially if you want to compare it against say a 256-bit key with 2²⁵⁶=115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 possibilities.

Now if I hand you a random user's password, technically it's not possible to uniquely assign an entropy to it.

You can only assign an entropy to a model of generating passwords. So if you are asked to estimate an entropy for a password, your task is to assume the model that might have generated that password.

If I gave you a password like P[rmDrds,r you might assume I randomly chose 10 characters from a set of 95 printable ASCII characters and to brute-force you would have to go through 95¹⁰ ~ 2^65.7 possibilities and it would have an entropy of 65.7 bits. However, it's just a very weak password OpenSesame where I shifted my hands on the keyboard over to the right one letter (which is probably one of say 2^6 ~ 64 common ways to alter typing an easy to remember low-entropy password). If you could find OpenSesame on a list of say the 1,000 (1000 ~ 2¹⁰) most common passwords then in fact the entropy of P[rmDrds,r is closer to 16-bits (possibilities of 2¹⁰ x 2⁶), when the password generation is pick one of 64 common ways to obscure a password and then choose a password off a list of 1000 common passwords. Thus after about 64,000 attempts a sophisticated brute forcer who tried this avenue of attack could arrive at P[rmDrds,r, so it's more accurate to estimate it's entropy as about 16 bits than 65.7 bits, which is 2^65.7-16 ~ 2^49.7 ~ 914 trillion times times easier to brute-force than the 65.7 bit password.

Now, obviously some less-sophisticated brute force attacker might have ignored the possibility of shifting characters over on the keyboard one space to the left while going through common password lists. But to be safe you ignore dumb attackers and assume very sophisticated attacker has considered all of your methods of password generation (Kerckhoffs's principle says avoid security by obscurity; assume the enemy has considered your secret technique among many other methods). So when someone says you need a high-entropy password, your goal isn't a password that appears to be highly random (and some simple password tester labels it as high-entropy). You want a random password that was built off of lots of random choices being input into your password generation procedure. You should not pick meaningful words to you and make up a password for it with obscure tricks like shifting letters around or leetspeak substitutions. For a strong password, you should rely on 80+ bits of non-human randomness being input into your procedure. You should note that one bit of entropy in a password generation procedure is equivalent to a two-option decision (e.g., something that could be determined by a coin flip).

And again, with very small likelihood you can randomly generate a password with a lot of random choices and it ends up a very weak password; e.g., it's technically possible that you randomly choose 12 characters and get password1234 or dddddddddddd. In practice, that's a possibility though it's unlikely to happen (e.g., if you use a procedure that generates an 90-bit password, the chance that it generated a password that also could have been generated with a simpler procedure with only 34-bits is 2³⁴/2⁹⁰ = 1 in 2⁵⁶ which is roughly the odds of buying exactly two Mega Millions tickets in a row and winning the jackpot both times).

Answer 2

Actually, from your description, I'm not sure if you do understand how to calculate password entropy. The entropy of a password would be more correctly described as log(R) where R is a randomness metric, not a complexity metric.

For example, this has nothing to do with using special characters. The password Tr0ub4dor&3 has 0 entropy because I took it from somewhere. On the other hand, the password 1101111110101000001011001110101110011111010100101111001110101011 has an entropy of 64 bits, because I just generated it by taking 8 random bytes and printing them in binary.

The entropy of a password is the entropy from information theory. It measures the quantity of information that someone trying to break the password does not know. Unless specified otherwise, security people assume that the system has to defend against people with at least normal intelligence. Per Kerckhoffs's principle, we assume that the attacker knows the method by which the password was chosen. Thus the information content that the attacker lacks about the method is 0. What the attacker can't know, however, is the output of my random generator. Thus the entropy of a password is the information content provided by the random generator. Assuming a perfect random number generator and a password generation method that turns distinct RNG outputs into distinct passwords, this information content is equal to the amount of data read from the RNG.

Password entropy is additive. If a system has two passwords such that you need to provide both to log in, then the entropy of the pair of passwords is the sum of the entropy of the two passwords. Note that there is an independence assumption here! If you can find out whether one password is correct without knowing the other, then the entropy of the two-password system is less than the sum of the entropy. (As an extreme case, consider a password of fixed length N bits: you could consider each bit of the password to be a separate mini-password; if you can test each bit independently then only 2N attempts are needed to break it instead of 2^N). Once again, this property comes from information theory: you can add the entropy of two separate information sources, but it doesn't make sense to add the entropy of two sources that overlap.

Answer 3

The reason why password entropy typically looks like log₂(D) is that this is the Shannon entropy for an information source that has a uniform probability distribution for all the potential outcomes when the number of potential outcomes is D. In this context, outcomes means outcomes from a stochastic password-generating process.

And as others here have pointed out, entropy is not a property of any individual password. Entropy is a property of an ensemble of passwords that is defined by a particular set of rules. However, if you don't care about being stringent, you can sometimes loosely infer what those rules are by inspecting an individual password, e.g. the presence of digits and uppercase letters loosely imply rules that specify a larger ensemble (with a uniform probability distribution) than when only lowercase letters are present.

For an individual password there is a different measure called Kolmogorov Complexity that measures how many bits of information are necessary to produce that particular password from a predetermined algorithm. This is obviously a relative measure since it depends on the algorithm, but loosely speaking you can use the compressed length of the password as a proxy for Kolmogorov complexity.

Answer 4

A better way to think of the entropy of a password is the minimum amount of bits required to convey the information contained in the password. A few examples:

If my password is 'aaaaaaaa', then one valid way to view the entropy of the password would be 5.9 bits (entropy for single case-sensitive alphanumeric character) plus 3 bits (to indicate it repeated 3 times).

If a service requires two passwords, and I set both to match each other, then I haven't significantly increased the amount of information to communicate the passwords over a single password, since 'Password123' and 'Password123 1' aren't that different in terms of entropy.

If a service requires two passwords, and both are (separately) randomly generated, then I have doubled the entropy in the passwords (although it would make more sense to just have a single password with more strict minimum requirements).

Answer 5

As others have said, it is not password entropy, it is password generation entropy: how hard is it to duplicate a given password given full knowledge of how it was created.

To calculate the entropy, write down the process, step by step. Then determine how many attempts it would take, to find a password generated by those steps.

Password: 01012006

Process: my child's birthday in mmddyyyy format. 365.25 per year, current maximim age of people and minimum age of successful child birth gives range of no more than 115 years. 115 x 365.25 = 42,004 attempts before you are sure to have found the password.

Process: pick 8 random numbers using a 10 sided dice. 10^8 attempts before you are sure to have found the password.

Same exact password, one is vastly easier to get and subject to out of band optimization (information not directly part of the process, but which limits the options). If I know the birthdate of your children the current max attempts is probably under a 1000 and as low as 1.

As for whether it is additive: not exactly. You only have one password generation algorithm, it just includes a step that was used elsewhere as a complete process for generating a password.

Answer 6

The password's entropy is like the entropy of every source of information: it is -log_2 of the Bayesian probability of that exact password for the attacker. As such, the entropy of a password is, strictly speaking, attacker-dependent, because it is the Bayesian probability for him, including all information he already possesses.

The entropy of the password for you is zero, because the Bayesian probability of the right password is 1 for you: its universe consists of only one single password, because you know it.

If you decided to take a uniformly randomly selected word out of a 4096-word dictionary, and the attacker knows this, then the password entropy is 12 bits. If however, the attacker doesn't know which of the 256 possible dictionaries (with different words, let's say, because different languages) you have picked, and if he assigns equal probabilities to each of them, then your password will have 20 bits of entropy for him.

If, on the other hand, he gives it 50% chance that you took it from the right dictionary, and he assigns the other 50%/255 to the other 255 dictionaries (in other words, he guessed the right dictionary with 50%), then your password will have only 13 bits of entropy for him. Note that if he guessed the main dictionary wrong, then your password has actually 21 bits of entropy for him, because he only assigned 50%/255 to the right dictionary! In other words, the entropy of a password is depending on what the attacker already estimates to know about your password.

The only absolutely safe way to have a high-entropy password is using a true random number generator (based for instance, on the second law of thermodynamics, or quantum physics), where physical entropy is used to generate information entropy. The point is that nobody has any better Bayesian estimator than the physically given entropy (or otherwise, the second law of thermodynamics would be violated: that's exactly what the second law is saying in fact).

Cryptographic one-way trapdoor functions do not add entropy: in the best case, they conserve entropy. If you pick a number from 1 to 32, and then you calculate SHA-256 or SHA-1 or just any funny combination of hash functions, you will have a thing that LOOKS like a very random password, but it will only have 5 bits of entropy if your picking of 1-32 was uniformly random: there are only 32 possible outcomes, no matter how many bits you have in your final password.

Pseudo-random generators also do not add entropy: they obfuscate the entropy that is in the seed. They are nothing else but a complicated sequence of hash functions applied to the seed.

Answer 7

The password entropy is given by how long it would typically take an attacker, who knew your password generation scheme, to run through all the possible passwords it could generate.

For instance I use a password generator that is basically dicewords. I use a cryptographically strong method to generate a random word, then use groups of 6 bits from that to choose from a dictionary of 64 english words of 3 letters (rat, cow, men ...), to make the password more human readable/usable/memorable.

Although the apparent entropy (attacker doesn't know the method) of a character from the resulting password is roughly 5 or 6 bits (one character from 26 alpha or more alphanumeric) , the true entropy (attacker does have my program) is only 2, because of the knowledge that went into how it was generated.

A strong password is arrived at simply by having sufficient number of characters. A 39 character string will have 78 bits of true entropy.