Your entropy calculations are off. Given 52 possible choices (a-z, A-Z), the entropy per character is ld(52) ~ 5.7 bits. For 10 characters, the entropy is 57 bits.

@Ja1024: The entropy per character would be -log2(1/52) in case when every character is different. But in "myPassword" the "s" character is 2 times present.

I agree with @Ja1024's calculation. Besides, this doesn't address the entropy-per-character issue, and whether it's at all relevant.

Concrete question, which would settle the argument: how would you actually construct an attack which would crack a 10-character password in a maximum 2^31 attempts, rather than 2^57 attempts?

@QF0: If you calculate the probability based on the whole corpus of English words, then the per character wise entropy will be lower. The entropy is not a property of a single character, but the property of the distribution of characters

@QF0: I wrote about the theoretical lower bound. Let's assume you have a bijective function f, which compresses your passphrase to it's minimal representation, you would just need to brute-force the space of the minimal representations(which has lower dimensionality), and thus need fewer iterations.

Ok, but how do you use this knowledge to crack a password? How do you use this knowledge to crack a random 10-char password in a max of 2^31 attempts? How are you going to construct your attack?

There isn't a theoretical lower bound; the lower bound is 1. The only relevant bound is the upper one.

@QF0: No, we are talking now about expected values. The value for one password might be 1, but if we take thousands of passwords, the value of brute-force iterations needed will converge to the expected value. Regarding how to perform the attack: theoretically if I would have access to function f and it's inverse f^-1, then I would simply iterate the space of 32 bits bit-wise, revert this 32 bit-value to the "uncompressed" password and perform the operation (e.g. hashing) on the uncompressed one. Thus I would be able to get the password in 2^32 iterations

@oleg_zh: You said the attackers only knows the password has 10 characters from the alphabet a-zA-Z. This leads to an entropy of 57 bits. If the attacker has more information (like duplicate characters), then we're talking about a different password pattern with a different entropy.

@Ja1024: The definition of the discrete entropy is: H(X) = -sum(p(x)*log(p(x)),x, X). You just need to apply the formula. But indeed, I may have made a mistake in my calculations :)

@oleg_zh: That's the definition, but in the case of independently chosen characters from an alphabet of size n, you can simplify this to H(X) = -n * (1/n) * log(1/n) = log(n). For a password of length l, the total entropy is l * log(n).

@Ja1024: You are mixing the search space cardinality and entropy. Let's try from another angle. Imagine we have an infinite alphabet A, and [A-Za-z] would be a subalphabet of A. According your formula, the entropy of the string "myPassword" would be then infinity, due to lim(l * log(n), n, inf) = inf. Obviously, the entropy of the phrase "myPassword" cannot be infinity. I will post an update to my answer to include a more hands- on and easier to follow example, which will clarify about entropy.

@oleg_zh: I'm not mixing up anything. I'm using the standard definition of Shannon entropy which is the formula you wrote down yourself. This exact formula can be simplified to ld(n) given a discrete uniform distribution with n possible values. You actually seemed to agree with me in your first comment where you correctly stated the entropy of a single character in the [a-zA-Z] range as ld(52). You can easily extend this to words of length l using the same formula, which results in l * ld(n).

@Ja1024: I still agree with you, that the per character entropy is log(52), but if and only if X pure random and there are enough observations in X (read: at least 52 observations). The entropy is again not a function of a single character, but it is a function of the distribution of characters. The entropy metric depends on the form of the distribution, and not on alphabet size | A |. If you do not believe me, you can try out the countless entropy calculators on the internet, or also post a question on Math Stackexchange :)

@oleg_zh: Of course you can help the attacker and give them more information about your password (for whatever reason). For example, you may tell them the fifth and sixth character is actually the same. This leads to a reduced entropy of (l – 1) ld(n). Or you tell them the password is constructed of two words from a specific dictionary – this again leads to a different entropy result. What you don’t seem to understand is that the entropy calculations discussed here refer to a password pattern, not an individual password. If the exact password is known, the entropy is zero bits.

@Ja1024: "An attacker doesn’t know the password in advance[...]". An attacker doesn't need to know anything about the password in advance. The attacker just needs to know that the password has a low entropy (and the majority of user generated password fulfill this criteria, since users like to use passwords like "password123"). Again, the OP initially asked how does entropy relates to the security of passwords. I have answered the question. But we have drifted away from that initial question.

@Ja1024: "If the exact password is known, the entropy is zero bits.[...]". I am not sure, whether you really know what entropy is, and what a probability distribution is. A probability distribution is a function which takes a signal X (might be continuous or discrete) as an argument, and assigns it a value between 0 and 1. The sum (or integral in continuous case) of all those probabilities equals to 1. So, now the entropy is a property of this probability function, and defined by formula above. The entropy does not depend on whether attacker knows the shape of the distribution or not.

Given the string "myPassword" we have the probabilities: p('s') = 0.2, p(all other letters) = 0.1. So the entropy of this probability distribution will be: H = -(0.2 * log(0.2) + 8 * 0.1* log(0.1)). Is is not 57bit, and not 0bit as you write in your last message. Sorry, but I also don't think it is productive to fight with each other here and discuss who is right and who is wrong. If you have doubts, you can always ask on Math Stackexchange. I am sure the guys there will write you a similar answer as me.

@oleg_zh: You clearly have no idea how probabilities, probability distributions and entropy work. When you consider 10-character passwords, then the X in the Shannon formula is a distribution which assigns probabilities to each 10-character password. Not individual characters. There's no such thing as “p('s')”, and whatever value you've assigned to that is pure fantasy. You can calculate the probability of entire passwords, e.g., p('myPassword). The value of this does depend on the distribution assumed by the attacker. In a uniform distribution, the probability is 1/52^10.

@oleg_zh: This is basic math and has nothing to do with entropy yet. Now insert p(x) = 1/52^10 into your own formula and calculate the result. Try it. You don’t need an online calculator for that, just simplify the terms. If you’ve been successful, you’ll end up with H(X) = 10 ld(52) bits, which is roughly 57 bits. Does this look familiar? Hint: It’s the result I’ve been telling you the whole time.

@oleg_zh: Taking an individual password and then claiming probabilities for individual characters is complete nonsense, because (1) probabilities are assigned to the whole password and (2) you have no clue what the probabilities are when you don’t know how the password was generated. What’s the probability of the password 'äü'? If you’ve come up with a concrete number, you’re already wrong, because the result depends entirely on the probability distribution. If the characters were independently sampled from the small set of German umlauts äöü, then we’re talking about a probability of 1/3².

@oleg_zh: But if they were sampled from the gigantic set of Unicode characters, the probability is obviously much, much smaller (something like 1/150,000²). Since the probability cannot be 1/3² and 1/150,000² at the same time, that should tell you it depends on the distribution. In the case of passwords, the distribution must be assumed by the attacker based on available information. So, yes, it does matter what the attacker knows about the password.

@Ja1024: In the password space [a-zA-Z]{,10}, in case of unifomely distribution the probability of a single password is 1/52^10, yes. But that has nothing to do with entropy. Entropy is the theoretical measure for lossless compression of data. If string "myPassword" has an entropy of 31bit (my password manager says it is 27bit), you can theoretically lossless compress that string up to those 27bit. Lossless compression below those 27bit is not possible. This is called the "Shannon Source Coding Theorem", and the main idea behind the term entropy in IT.

@Ja1024: You can read up more here: Read more: faculty.uml.edu/jweitzen/16.548/classnotes/….

@Ja1024:Also, the entropy measures the "randomness" of a variable/signal X. If we take e.g. a continuous Gaussian distribution N(µ,sigma), the entropy will be H(N(µ,sigma)) = ln(sigma), if I remember correct (I am not going to derive it now). If you make this distribution pure random, so let the st. deviation go to infinity, you get lim(ln(sigma), sigma, inf) = inf. Entropy is also not tied to passwords only. You can calculate entropy of arbitrary files. But that does not mean that for a file with size n, it's entropy is constant and equals 256^(-n)

@oleg_zh: I'm glad you finally realize that the probability of every(!) password x in a uniform distribution is p(x) = 1/52^10. Now all you have to do is insert this exact value into your own definition of entropy. Don't give us a lecture, just insert the value and calculate the result: For the summands, you get p(x) log p(x) = 1/52^10 log 1/52^10 = -1/52^10 * 10 log 52. Agreed? Now calculate the sum: There are 52^10 possible passwords, so you get 52^10 * (-1/52^10) * 10 log 52 = -10 log 52. The total result is H(X) = -(-10 log 52) = 10 log 52 ~ 57 bits. That's it.

@Ja1024: we are talking orthagonal to each other. You are integrating p*log(p) over the password space. That would be the entropy of the "password generation procedure", and would indeed be l*log(n). I am talking about the entropy as a measure for the amount of information in a given password. OP has stated that "according to NIST, the avg. entropy per character is 1.1bit" and asked about the implications of this on the PW security. I have answered OP's question, that the security of a PW grows exponentially with it's amount of information(entropy). (ignoring dictionary attacks)

Furthermore, if you have a TRNG and a password space [a-zA-z]{10}, then the entropy of the PW generation process would be 57bits. But there is no strict mathematical guarantee that the result of this process (namely the PW) will itself have 57bit of information. Your TRNG could generate a password like 'aaaaaaaaaa' with the probability 52^(-10), but that string would have an entropy(amount of information) of 0 bits. Beside this I doubt somebody will read these 20+ messages, and don't think this dialog will be helpful for community.

this is only useful if the attacker knows the entropy of the password, or performs an attack that brute-forces password strictly by increasing order of entropy. That requires a function that, given a value of entropy, can generate all corresponding passwords. Of course it is always possible to include assumptions that reduce the entropy of a given password (such as the prior knowledge that a password is a string of English words)