Password diversity

[Toshio Kuratomi]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
Url : http://lists.fedoraproject.org/pipermail/infrastructure/attachments/20111201/dfab5108/attachment.bin