6 ms·

It's ironic that allowing low-entropy passwords (for example, one-character) can actually increase the available entropy. For example, if you set a minimum pas

by _hyn3 7y ago

It's ironic that allowing low-entropy passwords (for example, one-character) can actually increase the available entropy. For example, if you set a minimum password length of six characters, an attacker doesn't even need to bother going through all of the 1 through 5 character combinations. The flip side of the coin is that, obviously, allowing low-entropy passwords will inevitably mean that some users will actually use them, which means that their passwords actually have decreased entropy.

jacobwilliamroy 7y ago
I have actually thought about this a lot and done some napkin calculations: using a set of about 93 characters the search space for 5 character passwords is about 7 gigabytes; combining all the possible passwords <= length 4 is only about 74 megabytes in comparison. I think that the entropy loss is insignificant.
- FabHK 7y ago
  Indeed, and the factor is about 95, which is close to 93, and that is not a coincidence, when you think about it. If you want to crack my password, and I tell you that my password is L characters long, by skipping all passwords of length < L you've only saved about 1/N of the required effort (where N is the size of the character set you choose from). In other words, telling someone the length of your password does not help them very much.
  - _hyn3 7y ago
    The impact of this really depends on the cost of calculating hashes, which varies based on hash algorithm. It might even be the difference between being able to ever find the hash or not. Being able to constrain the search space is the ONLY tool you can count on. If you say "No passwords less than eight characters", most passwords will be clustered around 9 or 10 characters. That's human nature. This means that your entire search space is only the character set in that very limited set of strings. And, if you're limiting that character set, and also it's expensive for you to hash (ie scrypt or bcrypt with lots of rounds), then not having to go through the first 1-8 set will save you a tremendous amount of time...
    - FabHK 7y ago
      > then not having to go through the first 1-8 set will save you a tremendous amount of time... Well, not quite. If you allow say capital letters and numbers only (36 different characters), and you have to go through all 9 and 10 character passwords, skipping the first set of 1 to 8 character passwords saves you less than 0.1% of the work, if my rough back-of-the-envelope calculation is correct. That was precisely what my statement was about - longer passwords are just so much better. (Note that this assumes that the cost of computing the hash is by and large independent of the length of the password, which is a very good assumption for the lengths we are talking about here).
FabHK 7y ago
> can actually increase the available entropy Well, the theoretical entropy, but not the empirical. You could argue that ruling out "12345678" and "password" and "Password!" reduces the "available entropy" and makes things less secure (after all, your random password generator might just randomly have generated "12345678"), but in practice quite obviously it makes things more secure.
- _hyn3 7y ago
  Agreed. > Well, the theoretical entropy, but not the empirical. Agreed. There are profound implications of that statement of that statement when applied to other problems, because we mutually accept the theory as correct, but only theoretically, when we know it has significant limitations in the real world. > You could argue that ruling out "12345678" and "password" and "Password!" reduces the "available entropy" Obviously. And yet, equally obviously, removing those from the rounds because they're preemptively banned reduces the actual number of test hashes we have to run to brute force, and introducing a rule means that we can also eliminate huge swathes of potential keyspace. So, the obvious is not necessarily so obvious after all. This gets more and more interesting the deeper the rabbit hole goes. What if we have extremely random data -- perhaps even raw binary -- but it happens to have a sequence of three arbitrary integers, which is in violation of the rules, and therefore we can eliminate all such passwords from our test cases? That's a potentially huge chunk of entropy.

by _hyn3 7y ago

jacobwilliamroy 7y ago

I have actually thought about this a lot and done some napkin calculations: using a set of about 93 characters the search space for 5 character passwords is about 7 gigabytes; combining all the possible passwords <= length 4 is only about 74 megabytes in comparison. I think that the entropy loss is insignificant.

FabHK 7y ago
Indeed, and the factor is about 95, which is close to 93, and that is not a coincidence, when you think about it. If you want to crack my password, and I tell you that my password is L characters long, by skipping all passwords of length < L you've only saved about 1/N of the required effort (where N is the size of the character set you choose from). In other words, telling someone the length of your password does not help them very much.
- _hyn3 7y ago
  The impact of this really depends on the cost of calculating hashes, which varies based on hash algorithm. It might even be the difference between being able to ever find the hash or not. Being able to constrain the search space is the ONLY tool you can count on. If you say "No passwords less than eight characters", most passwords will be clustered around 9 or 10 characters. That's human nature. This means that your entire search space is only the character set in that very limited set of strings. And, if you're limiting that character set, and also it's expensive for you to hash (ie scrypt or bcrypt with lots of rounds), then not having to go through the first 1-8 set will save you a tremendous amount of time...
  - FabHK 7y ago
    > then not having to go through the first 1-8 set will save you a tremendous amount of time... Well, not quite. If you allow say capital letters and numbers only (36 different characters), and you have to go through all 9 and 10 character passwords, skipping the first set of 1 to 8 character passwords saves you less than 0.1% of the work, if my rough back-of-the-envelope calculation is correct. That was precisely what my statement was about - longer passwords are just so much better. (Note that this assumes that the cost of computing the hash is by and large independent of the length of the password, which is a very good assumption for the lengths we are talking about here).

FabHK 7y ago

> can actually increase the available entropy Well, the theoretical entropy, but not the empirical. You could argue that ruling out "12345678" and "password" and "Password!" reduces the "available entropy" and makes things less secure (after all, your random password generator might just randomly have generated "12345678"), but in practice quite obviously it makes things more secure.

_hyn3 7y ago
Agreed. > Well, the theoretical entropy, but not the empirical. Agreed. There are profound implications of that statement of that statement when applied to other problems, because we mutually accept the theory as correct, but only theoretically, when we know it has significant limitations in the real world. > You could argue that ruling out "12345678" and "password" and "Password!" reduces the "available entropy" Obviously. And yet, equally obviously, removing those from the rounds because they're preemptively banned reduces the actual number of test hashes we have to run to brute force, and introducing a rule means that we can also eliminate huge swathes of potential keyspace. So, the obvious is not necessarily so obvious after all. This gets more and more interesting the deeper the rabbit hole goes. What if we have extremely random data -- perhaps even raw binary -- but it happens to have a sequence of three arbitrary integers, which is in violation of the rules, and therefore we can eliminate all such passwords from our test cases? That's a potentially huge chunk of entropy.