Hi,
At the moment while checking if a password is valid FAS does not check how many characters are present. Thus it allows things like: "aaaaaaaaaaaaaaaaaaaa" as password.
One solution is of course checking how many different characters are present in the password and I have a quick patch which does that. However while discussing about this with Kevin and Toshio on IRC we did not find what would be an optimal number of character different in the password which would be: - high enough to make the password strong(er) - low enough so that in case of brute force the number of possibilities for each character added remain high.
So, do you have an opinion on the minimal amount of different characters a password should have ?
Thanks, Pierre
One solution is of course checking how many different characters are present in the password and I have a quick patch which does that.
Nice
- high enough to make the password strong(er)
- low enough so that in case of brute force the number of possibilities
for each character added remain high.
These seem reasonable. I think someone mentioned in a related discussion about checking passwords against rainbow tables and forcing a reset once the password is flagged as existing in a public table. Maybe this would make sense considering it's now relatively cheap to buy a decent rig with plenty of powerful graphics cards.
So, do you have an opinion on the minimal amount of different characters a password should have ?
I think this is tough to answer without falling back on the old statement of ... "it depends." High character count, diverse character sets (letters, numbers, symbols, etc) and mixed case are all important but I wonder how we can balance this with usability? Should we require people to use a password management tool so they can accommodate our complexity rules? Maybe it's a good idea but I for one wouldn't like it.
For example, who can say whether a 20 character password comprised of 5 symbols, 5 numbers, 5 upper and 5 lower is better than a 25 character password with a similar composition? I realize various papers exist in this area of security and mentioned one earlier in the year on the list. The one I highlighted concluded passwords are becoming increasingly useless in light of raw computational power. It always strikes me as odd that we strive to require complex passwords with finite computations; such is our present reality.
It's a hard problem that requires complementary tools. Such tools might include randomized login delays on failures (I think we do this already), temporary account locking (on suspected brute force) and etc.
The more characters the better, the more complex the better, and the less predictable the better.
Just my two cents.
On Wed, 2011-11-30 at 20:09 -0500, Adam M. Dutko wrote:
The more characters the better, the more complex the better, and the less predictable the better.
Following this, then we should not enforce a minimum number of different characters in the password, nor should we use a rainbow table to check for existing/known password.
I guess it is all a matter of balance pros and cons but I cannot make my mind on what is best ('aaaaaaaaaaaaaaaaaaaa' still seem to be a horrible password to me).
I'll just keep the patch somewhere until we've decided if it is worth applying or not.
Thanks, Pierre
('aaaaaaaaaaaaaaaaaaaa' still seem to be a horrible
I totally agree.
I'll just keep the patch somewhere until we've decided if it is worth applying or not.
I was not implying the patch isn't worthwhile or that we shouldn't apply it. I'm interested to hear feedback as to what you think would be a good solution and the reasoning behind your thoughts. abadger1999 and nirik are more familiar with our systems than I am so beyond what you stated in the mailing list earlier I'm not sure what wasn't discussed during your IRC session. I believe abadger1999 is also the project lead so I think any changes related to security would need to be approved by him.
Where is the patch? Can you post it on ReviewBoard? (https://fedorahosted.org/reviewboard) and assign it to me please? Or can you stop by #fedora-admin and ping me with a link to it? My IRC nick is styluseater. Thank you.
-Adam
On Thu, 2011-12-01 at 09:18 -0500, Adam M. Dutko wrote:
I'll just keep the patch somewhere until we've decided if it is worth applying or not.
I was not implying the patch isn't worthwhile or that we shouldn't apply it. I'm interested to hear feedback as to what you think would be a good solution and the reasoning behind your thoughts.
I am saying it, I am really pondering whether it is something we should do (as I am not a security expert). I think we should but I do ponder how strong.
At the moment in the patch I just check if there are more than 3 different characters in the whole chain. Meaning for a 20 characters long password you would have: 26*25*(24^18) = 4.536446e+27 trials (against 26^20 = 1.992815e+28)
Where is the patch? Can you post it on ReviewBoard? (https://fedorahosted.org/reviewboard) and assign it to me please? Or can you stop by #fedora-admin and ping me with a link to it? My IRC nick is styluseater. Thank you.
I simply put it there: http://fpaste.org/Hw9s/ I can add it to the reviewboard if needed. (Actually in this version I check that there are at least 2 different characters).
Pierre
On Thu, Dec 01, 2011 at 03:47:04PM +0100, Pierre-Yves Chibon wrote:
On Thu, 2011-12-01 at 09:18 -0500, Adam M. Dutko wrote:
I'll just keep the patch somewhere until we've decided if it is worth applying or not.
I was not implying the patch isn't worthwhile or that we shouldn't apply it. I'm interested to hear feedback as to what you think would be a good solution and the reasoning behind your thoughts.
I am saying it, I am really pondering whether it is something we should do (as I am not a security expert). I think we should but I do ponder how strong.
I like something along these lines. I just don't know how many unique characters we want to enforce either.
At the moment in the patch I just check if there are more than 3 different characters in the whole chain. Meaning for a 20 characters long password you would have: 26*25*(24^18) = 4.536446e+27 trials (against 26^20 = 1.992815e+28)
Showing my possible misunderstanding of the problem, is it actually: 26*25*24*(26^17) = 1.76877e28
My reasoning is that after satisfying the diversity requirement, the remaining characters can be from the entire keyspace (including the three characters that were previously used).
However, I think my reasoning is flawed there as well. If you think about it, the attacker doesn't know which position would contain a different character. So it seems like the attacker removes a smaller number of possibilities for a low diversity
If you require a minimum of two different characters you're really just removing len(characters) combinations ('a'*20, 'b'*20, [...], 'z'*20)
If you require a minimum of three different characters you're removing all combinations in which only two characters are used (at which point, my mathematical education fails me ;-)
So for 2 characters, it doesn't greatly reduce the total keyspace. Someone with better math skills than I should look at what greater diversity requirements cost.
Looking at this from the other angle, though, if an attacker is trying likely passwords and they decide that strings with a small number of distinct characters are likely, there are 20 strings of 20 characters with a single character, ~1 million ways to combine two characters, 3.4e9 ways to combine three characters, 1.0e12 ways to combine four, etc. On yet another hand, it doesn't seem like uniform strings of characters are easy to type precisely:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa <= how many times did I hit the 'a' key?
So perhaps we're worrying overly much about this case and we should be worrying more about stopping users from using "abcdefghijklmnopqrstu" or "My name is Linus Torvalds and I pronounce Linux, Linux"
One of the things that thinking about this forces me to consider is whether the paper we based the present strength checking on took any of this into account. For instance, our rules for 9 characters are:
upper && lower && digit && symbol.
That means that even though you have 96 printable characters to work with (might be 95... I think tab is one of the printables and I don't think it can be easily entered into a browser) which have a total of 6.9e+17 combinations we are eliminating a number of those possible combinations as valid.
Someone who understands mathematical combination might be able to analyze that and come up with the total keyspace and then combine that with the paper's estimates on GPU cracking performance to get an estimate of how quickly a brute force attack could be performed.
Where is the patch? Can you post it on ReviewBoard? (https://fedorahosted.org/reviewboard) and assign it to me please? Or can you stop by #fedora-admin and ping me with a link to it? My IRC nick is styluseater. Thank you.
I simply put it there: http://fpaste.org/Hw9s/ I can add it to the reviewboard if needed. (Actually in this version I check that there are at least 2 different characters).
If my estimate of the cost of a diversity of two characters is correct, this seems pretty safe. OTOH, if my estimate of the benefit is also correct, it probably won't be triggered unless someone is intentionally working hard to use a bad password.
I think I'm for putting it in with diversity 2. Would love for someone with more mathematical skills to tell us how it affects the overall picture before putting it in with a higher diversity.
-Toshio
Pierre-Yves Chibon <pingou@...> writes:
At the moment while checking if a password is valid FAS does not check how many characters are present. Thus it allows things like: "aaaaaaaaaaaaaaaaaaaa" as password.
One solution is of course checking how many different characters are present in the password and I have a quick patch which does that. However while discussing about this with Kevin and Toshio on IRC we did not find what would be an optimal number of character different in the password which would be:
- high enough to make the password strong(er)
- low enough so that in case of brute force the number of possibilities
for each character added remain high.
So, do you have an opinion on the minimal amount of different characters a password should have ?
What about periodically running a password cracker on all the accounts, and notifying anyone whose password is cracked by it that they need to change it soon? I suspect that it's possible to choose weak passwords that satisfy any fixed set of rules for password strength.
Also, when installing Fedora, and during firstboot, the chosen root and ordinary user passwords are checked for password strength. How is that done?
infrastructure@lists.fedoraproject.org
-
Adam M. Dutko -
Andre Robatino -
Pierre-Yves Chibon -
Toshio Kuratomi