28

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, NL. 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.

  • @Michael Thanks for the edit! For some reason I couldn't get the Markdown to 'stick' and finally gave up. – Aengus Dec 1 '17 at 21:58
  • 17
    Passwords don't have entropy. Password-generation methods have entropy. – Mark Dec 2 '17 at 0:37
36

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 2128 = 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 1036 or 340 undecillion (short scale), especially if you want to compare it against say a 256-bit key with 2256=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 9510 ~ 265.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 ~ 210) most common passwords then in fact the entropy of P[rmDrds,r is closer to 16-bits (possibilities of 210 x 26), 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 265.7-16 ~ 249.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 234/290 = 1 in 256 which is roughly the odds of buying exactly two Mega Millions tickets in a row and winning the jackpot both times).

  • 8
    @PieterGeerkens Perhaps it's poorly worded, but I don't think jimbob is suggesting using random choices to change the password generation method, but rather to ensure that the password generation method includes enough entropy. He's not saying anything about how to obtain that entropy, just that it needs to be included. ie a password generation procedure for an n bit password could be "flip a coin n times, if heads append a '1' to the password, if tails append a '0'". – AndrolGenhald Dec 1 '17 at 20:44
  • @AndrolGenhald: Like Horton the elephant: "Say what you mean, and mean what you say." Making readers guess at the hidden meaning of poorly worded statements is a recipe for miscommunication. – Pieter Geerkens Dec 1 '17 at 21:06
  • 4
    @PieterGeerkens - Making lots of random choices in your password generation procedure was a plain way of saying use a high-entropy password generation procedure. From the context of the example, do not use methods that generate passwords that appear random, but have one of a few secret shortcuts with very few underlying random choices (bits of entropy) and are hence weak. A bit of entropy is equal to one random coin flip. Generate a password based on a procedure equivalent to having made lots of coin flips (80+ bits for strong stuff). – dr jimbob Dec 2 '17 at 7:38
  • 8
    Also, you should realize TAOCP Chapter 3 while interesting is outdated for cryptography. You should NOT be using LCGs at all for any cryptographic purposes. (It's possibly fine for one password if it starts with a truly random seed, but a bad idea in general). You should either use true sources of randomness (e.g., roll fair dice, measure noise/quantum effects) or use cryptographically secure pseudorandom number generators. Many common RNGs like LCGs, MT19937 are NOT crypto-secure and quite predictable and attackable in crypto situations (though fine for say Monte Carlo simulations). – dr jimbob Dec 2 '17 at 7:40
  • “because it's generally easier to deal and think about with the logarithm of these exceptionally large number of possibilities” – that's true, but I think it could be misunderstood. The reason for introducing the logarithm is not so much to avoid giant numbers; the original physical motivation was that entropy is additive: when you combine two systems (e.g. two gas containers to a single one with a wall in the middle), then the number of possible microstates actually multiplies, but the physical quantities like mass add. By taking the logarithm, you thus get a “more physical” quantity. – leftaroundabout Dec 4 '17 at 12:51
18

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.

  • 4
    As Cowthulhu remarks, “entropy of a password” is really a flawed concept, and making it look like there's a single numerical measure of entropy is wrong — in a way that's analogous to how entropy measurement is only defined up to an encoding. I'm going to edit this answer in a little while to address this. – Gilles 'SO- stop being evil' Dec 1 '17 at 20:27
  • 6
    I can't in good faith upvote this, because even though Tr0ub4dor&3 is probably in every password dictionary worth its salt (no pun intended), that doesn't mean its entropy is zero, just that it's got less entropy than a properly randomly generated similar password of the same length would. Not that the latter would be all that much either... – a CVn Dec 1 '17 at 21:44
  • 1
    @MichaelKjörling I would say it has 0 measurable entropy, as the method Gilles used to come up with it isn't well defined. – AndrolGenhald Dec 1 '17 at 22:30
  • 10
    @MichaelKjörling: If we're being charitable, we can note that passwords do not "have" entropy; only distributions of passwords do. It is true that the constant distribution whose value is always Tr0ub4dor&3 has exactly zero entropy. Furthermore, this claim isn't fully meaningless: a user who is dead-set on choosing Tr0ub4dor&3 because it is their "favorite password" or something is effectively sampling from this zero-entropy distribution. – wchargin Dec 2 '17 at 1:29
  • 1
    Because of Kerckhoffs's principle, we assume that the attacker knows the user's password generation scheme is "take a secure-looking password from an xkcd comic about secure-looking passwords" - even though a real attacker probably won't know that to start with. But under this assumption the password has zero entropy (because there is only one secure-looking password in an xkcd comic about secure-looking passwords). – user253751 Dec 2 '17 at 7:34
5

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.

  • 1
    I think Kolmogorov complexity might be the key. In general, K-complexity can not be computed but perhaps my metric B might be used as an approximation. – Aengus Dec 3 '17 at 2:39
  • I think Shannon is a big part of the the answer to the question that is asked here. – JimmyJames Dec 4 '17 at 14:42
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).

  • 7
    This answer is broadly correct, but I think your example is misleading. You're making it seem like you can tell the entropy of a password by looking at it. But this is wrong, just like you can't measure the entropy of a single piece of information by looking at it. What matters is where it comes from, i.e. how it's generated. – Gilles 'SO- stop being evil' Dec 1 '17 at 18:47
  • Thanks to both @cowthulhu and very good clarification by Giles. However, this doesn't seem to get me any closer to why the log_2(Difficulty) metrics was originally chosen. – Aengus Dec 1 '17 at 18:54
  • 1
    @Gilles Thanks for your clarification. In that case, it sounds like I don't completely understand how to derive entropy - my understanding was that regardless of the method, a password is only as strong as the easiest way of expressing it. In other words, if my password manager spits out 'AAAAAAAAAAAAAAAA' as a password, while in terms of my password managers (perceived) security, this has a high level of entropy, in reality it can be expressed in much less information than the 96 bits of entropy my password manager seems to think it has, meaning it isn't as secure. Is this accurate or flawed? – Cowthulhu Dec 1 '17 at 20:02
  • 4
    @Cowthulhu That's a good remark. Information-theoretic entropy is defined up to an additive constant, because that's the only way to be independent of the encoding. When you apply this to a password, the additive constant represents what the attacker knows about the password selection method. There's no such thing as the entropy of a password, only of a password selection method (whether it's used for generation or cracking), but talking about “entropy of a password” is a common language shortcut. (cont.) – Gilles 'SO- stop being evil' Dec 1 '17 at 20:23
  • 4
    The apparent discrepancy here is that the attacker and your password manager may have different methods, hence different additive constants. AAAAAAAAAAAAAAAA is just as good as anything for 16 random letters, but an attacker who tries “simple” password first has a different entropy measure — the two are only similar asymptotically, i.e. when the “simple” guesses fail. I'm going to edit my answer to address this. – Gilles 'SO- stop being evil' Dec 1 '17 at 20:25
1

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.

1

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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