4 ms·

Entropy and min-entropy are properties of distributions, not of individual samples from those distributions. So there's no meaning to "the entropy of each chos

Entropy and min-entropy are properties of distributions, not of individual samples from those distributions. So there's no meaning to "the entropy of each chosen password".

dbaupp 5y ago
Despite that slight misuse of terminology, the point stands: the article talks about estimating the entropy of a distribution used for generating a password, but the important thing is the “distribution” an attacker is using for guessing the password. A single password should instead be treated as a sample from a (plausible) attacker’s distribution, and the complexity of that password can be used to estimate the size of the sample space required for that plausible attacker (as in, how many guesses/how much work they’ll have to do). This is, AIUI, the approached used by libraries like https://zxcvbn-ts.github.io/zxcvbn/ https://zxcvbn-ts.github.io/zxcvbn/ The entropy of a distribution for generating passwords matters when generating them in bulk, such as OTPs or implementing a password manager. This doesn’t seem to be the situation being discussed in the article, which is more about rating a user-provided password.
- less_less 5y ago
  Zxcvbn is also a good idea, but it's a complementary approach. The user or password manager should generate secure passwords (using a high-min-entropy distribution), and the website or application should check that they're secure (using zxcvbn or similar). Of these two approaches, a high-entropy generation method gives more confidence. It gives a mathematical strength "guarantee": if you design and follow the method correctly, then an attacker, whether or not they know the generation method, is mathematically unlikely to guess your password quickly no matter what order they guess in. "Guarantee" is in quotes because of course the attacker could get very lucky or the user could get unlucky (eg generate a uniformly random 8-character string and it happens to be "password"), and also if there's eg an implementation flaw then your guarantee isn't worth the pixels it's printed on. By contrast, zxcvbn has no guarantee, because it doesn't use a huge curated dictionary and generation mechanism that the attacker is likely to use. So in addition to missing well-known passwords like "correct horse battery staple", it will miss bad passwords related to current events.
BeefWellington 5y ago
A single password represents a distribution of possible bit values for each byte within it. The password itself is a distribution of characters used within the password. In fact, the author's article makes this very point, which is why I pointed out the logical flaw in the thinking. I'll reduce N to 6 for simplifying the author's absurd example but it can expand to any N. If we take the argument to hold that you roll a random die of N length (6 in our case) and the upperbound represents one strong password, while all other values equate to the word "password", the flaw is in how this logic is applied. Imagine this is our set of possible values: password, password, password, password, password, hj5^@l2jl9GGk;Clkm(0] It makes little difference if you look at this as either the bytes involved in the entire set, or the average of all passwords within the set, it's going to come out looking like you are secure. This means what they're attacking is all permutations of the following set of characters: a, C, d, h, j, k, l, m, o, p, r, s, w, G, 0, 2, 5, 9, ;, ], @, ^, ( What an attacker must know though, is the character set used within, as well as the length. This is the logical flaw the author made in their analysis. For an attacker, the entropy of an individual string is taken as possible character permutations required to discover the true password and NOT permutations of the entire strings themselves. If you look at the values for each string presented in our set, what an attacker has to attack is: a, d, o, p, r, s, w C, h, j, k, l, m, G, 0, 2, 5, 9, ;, ], @, ^, ( But in order to attack these, they need to try the full set: a-z a-zA-Z0-9;:[]!@#$%^&*(){} One of these will be VASTLY easier to break.
- less_less 5y ago
  I don't understand your argument at all. Why does an attacker need to try a full set of characters? Real attackers try from dictionaries or password generation methods (eg dictionary + numbers, dictionary + dictionary + number + symbol, etc), and "password" is one of the first passwords they'll try. They do this because they don't know exactly how you generated the password, but due to password leaks, they do have a pretty good idea of how most people generate passwords. In principle, you could estimate a password's strength by the order in which a cracker would be expected to guess it. But that's a pain, depends on the password cracker being used, and can change at any time. Also, it's not "entropy", which is a well-defined mathematical concept and is what the linked article is about. Entropy is supposed to be a bound that even if the attacker knows your generation method, they won't be able to do better than brute-force search. For this, the author is correct that min-entropy or a similarly conservative measure is the right one; though for the most common (uniform) generation methods this is the same as Shannon entropy. Entropy of the set of characters used in your password (well, sets don't have entropy, but let's say of the uniform distribution on that set) isn't the same as entropy of password generation mechanism, because the attacker might have more information. For example, if he knows (or correctly guesses) that your password is a dictionary word, then this is super helpful information that isn't captured in the entropy of the bytes.

Entropy and min-entropy are properties of distributions, not of individual samples from those distributions. So there's no meaning to "the entropy of each chosen password".

dbaupp 5y ago

Despite that slight misuse of terminology, the point stands: the article talks about estimating the entropy of a distribution used for generating a password, but the important thing is the “distribution” an attacker is using for guessing the password. A single password should instead be treated as a sample from a (plausible) attacker’s distribution, and the complexity of that password can be used to estimate the size of the sample space required for that plausible attacker (as in, how many guesses/how much work they’ll have to do). This is, AIUI, the approached used by libraries like https://zxcvbn-ts.github.io/zxcvbn/ https://zxcvbn-ts.github.io/zxcvbn/ The entropy of a distribution for generating passwords matters when generating them in bulk, such as OTPs or implementing a password manager. This doesn’t seem to be the situation being discussed in the article, which is more about rating a user-provided password.

less_less 5y ago
Zxcvbn is also a good idea, but it's a complementary approach. The user or password manager should generate secure passwords (using a high-min-entropy distribution), and the website or application should check that they're secure (using zxcvbn or similar). Of these two approaches, a high-entropy generation method gives more confidence. It gives a mathematical strength "guarantee": if you design and follow the method correctly, then an attacker, whether or not they know the generation method, is mathematically unlikely to guess your password quickly no matter what order they guess in. "Guarantee" is in quotes because of course the attacker could get very lucky or the user could get unlucky (eg generate a uniformly random 8-character string and it happens to be "password"), and also if there's eg an implementation flaw then your guarantee isn't worth the pixels it's printed on. By contrast, zxcvbn has no guarantee, because it doesn't use a huge curated dictionary and generation mechanism that the attacker is likely to use. So in addition to missing well-known passwords like "correct horse battery staple", it will miss bad passwords related to current events.

BeefWellington 5y ago

A single password represents a distribution of possible bit values for each byte within it. The password itself is a distribution of characters used within the password. In fact, the author's article makes this very point, which is why I pointed out the logical flaw in the thinking. I'll reduce N to 6 for simplifying the author's absurd example but it can expand to any N. If we take the argument to hold that you roll a random die of N length (6 in our case) and the upperbound represents one strong password, while all other values equate to the word "password", the flaw is in how this logic is applied. Imagine this is our set of possible values: password, password, password, password, password, hj5^@l2jl9GGk;Clkm(0] It makes little difference if you look at this as either the bytes involved in the entire set, or the average of all passwords within the set, it's going to come out looking like you are secure. This means what they're attacking is all permutations of the following set of characters: a, C, d, h, j, k, l, m, o, p, r, s, w, G, 0, 2, 5, 9, ;, ], @, ^, ( What an attacker must know though, is the character set used within, as well as the length. This is the logical flaw the author made in their analysis. For an attacker, the entropy of an individual string is taken as possible character permutations required to discover the true password and NOT permutations of the entire strings themselves. If you look at the values for each string presented in our set, what an attacker has to attack is: a, d, o, p, r, s, w C, h, j, k, l, m, G, 0, 2, 5, 9, ;, ], @, ^, ( But in order to attack these, they need to try the full set: a-z a-zA-Z0-9;:[]!@#$%^&*(){} One of these will be VASTLY easier to break.

less_less 5y ago
I don't understand your argument at all. Why does an attacker need to try a full set of characters? Real attackers try from dictionaries or password generation methods (eg dictionary + numbers, dictionary + dictionary + number + symbol, etc), and "password" is one of the first passwords they'll try. They do this because they don't know exactly how you generated the password, but due to password leaks, they do have a pretty good idea of how most people generate passwords. In principle, you could estimate a password's strength by the order in which a cracker would be expected to guess it. But that's a pain, depends on the password cracker being used, and can change at any time. Also, it's not "entropy", which is a well-defined mathematical concept and is what the linked article is about. Entropy is supposed to be a bound that even if the attacker knows your generation method, they won't be able to do better than brute-force search. For this, the author is correct that min-entropy or a similarly conservative measure is the right one; though for the most common (uniform) generation methods this is the same as Shannon entropy. Entropy of the set of characters used in your password (well, sets don't have entropy, but let's say of the uniform distribution on that set) isn't the same as entropy of password generation mechanism, because the attacker might have more information. For example, if he knows (or correctly guesses) that your password is a dictionary word, then this is super helpful information that isn't captured in the entropy of the bytes.