[unisog] RE: is the current password std flawed?

Russell Fulton r.fulton at auckland.ac.nz
Sun Feb 27 03:06:20 GMT 2005


Well, I'm pleased I dropped that one out to the list as it has generated
some interesting discussion and raised some ideas that I have not
thought of before (more on that later).

So here is my take on the issue.

First I'll state a few assumptions that I am making:
      * That, for the most part, we are defending against
        unsophisticated attackers who do not know our policies.
      * Any solution that we come up with must work at least as well as
        the default situation if the attacker does know our policy and
        takes it into account.
      * Left to their one devices most users will choose passwords
        comprising lowercase letters (possibly with a few digits).
      * That brute force password crackers also make this assumption by
        default.

The first thing to do is to get a grip on the maths. Even though I did a
lot of maths at university (6 years) I still find it very hard to
formulate combinatorial models (it takes a lots of practise ).   My
brother in law (who makes a hobby of recreational maths) has just
dropped in and started beating this problem: Here is Fred's analysis:

=======================================================================
Best case scenario where we assume that that after our four class
characters have been selected the others will be randomly chosen from
each class:

Take the password as being exactly eight characters long.  The password
is some permutation of N.L.U.S.x.x.x.x where 

N is numeric (10 values)
L is lower-case alpha (26)
U is upper case alpha (26)
S is special (33 cases)
x is any of the above (95 cases => ascii 32-126 inclusive)

There are 8*7*6*5/(4*3*2*1) = 70 ways of arranging N.L.U.S.x.x.x.x
(permutations).

Total space is 70*(10*26*26*33*95*95*95*95) = 1.27 x 10^15.  Original
space is 95^8 = 6.63 x 10^15.

The restricted space is 19% of the original space.

Worst case, where we assume that all the remaining characters (x) are in
fact L which is far more likely:

pushes it down by a factor of about 10^3 from the 95^8 space, which
leaves us just a bit better off than with plain lowercase and digits.

Fred is not entirely happy with the worst case analysis and is sure that
there it is not quite right although he is happy that the answers are in
the right ball park (two different ways of formulating the problem gave
slightly different answers).  I'll go and consult friends in Maths and
Stats tomorrow to get this stuff checked.

====================================================================

So it turns out that CS's concerns are justified by the maths. By
forcing some choices you do cut down the the whole space significantly
and if you assume that users will go back to lowercase and digits for
the rest of their characters then the pools shrinks to a space only a
little bigger than L+N.

Is this a fatal flaw?

I don't believe that the picture is as bad as the above analysis
suggests since, in my opinion, what we are trying to do is to force
users out of the small corner of password space that they normally
occupy (L+N = 36^8 = 2.8x10^12))and which brute force attacks normally
target.  The key thing is to make sure that our policy does not leave us
worse off when faced with attackers who know our policy and adjusts
their tactics accordingly.  This is the bit that needs careful checking
and is at the root of CS's argument.  If the worst case analysis above
is correct we are left with a space a bit bigger than than the L+N. 

But crucially you have eliminated the very part of the space that brute
force systems focus on.  So I assert that we are well ahead of attackers
who don't know our policy and no worse of against those who do.

Most of the brute force algorithms I have seen first exhaust lowercase
characters, then add numbers and then uppercase and lastly special
characters for each additional character.  Many don't check specials at
all by default.

Here is part of James Harper's criticism (James is a senior tech/IT
manager in CS who has worked closely with us on several project and is
very good at keeping us on the straight and narrow ;) 

> What they do do is make it harder for a user to select a password that we'll
> accept. We should be aiming to give users as much freedom as possible in
> selecting a password while ensuring that what they select is not easily
> crackable. In my opinion, the best was to achieve this is "any password you
> like (that's not in our dictionary) as long as it contains at least one
> character that's not a lower case letter".

I do not believe that this is adequate any more.  I have seen two
example during penetration tests that would have met your test that were
broken by the attackers.  When I asked the pen testers what policies we
should adopt they said, forget dictionaries we just use brute force and
the only defence is complexity and length.  This assumes that the attacker has
somehow managed to get the hashes and for MS systems this is still
relatively easy.

The two password in question were both 7 characters, non dictionary and
had at least one digit.  OK, we are now forcing 8 char minimum but I I
doubt if the extra character would have been enough to foil to attack.
The testers told me that if these password had had either uppercase or
special characters in then they would not have been broken.

The point I am trying to make is that dictionaries only protect against
dictionary based attacks.  With brute force attacks the problem is that
you have to stop people using just a small part of the whole space and
the only practical way of doing this is by enforcing complexity.  Yes,
you throw a way a large chunk of the theoretical space but at least you
force the users out the of the tiny space they usually occupy.

I'll now comment on some of the things that the discussion on the list raised:

I really like the idea that Valdis raised as being used by Fedora (a
mixture of lenght vs complexity) but the down side is that it is
difficult to describe simply for users so they can pick password that
they know will be acceptable.  

Nothing pisses people of faster than having their choices repeatedly
rejected!   I've heard people swearing at the dictionary based systems
that we used to use because we had preloaded the dictionary with all the
common permutations, combinations and substitutions that users usually
try.  I can see users having similar problems with this scheme.

You could write a good feed back system for this scheme which would tell
the user the score of your current choice and make a number of
suggestions (based on analysis of the current choice ) that would make
it acceptable.  Hmmm.... I like this idea may have a go at implementing
it -- does the Fedora system do anything like this?

When we formulated our current policy we made a conscious effort to
"Keep It Simple and Predictable" for the users so they could formulate
passwords that they would know in advance were acceptable under the
policy.

I have also been aware for some time of the issue that complexity rules
make it easier for shoulder surfers and I am please to see that PaulFM
raised this issue that I have not seen mentioned before.  One answer to
this is to use pass phrases as an alternative to complexity.  I believe
that password guessing by visually observing key strokes is a *very*
underrated threat.  One of my colleagues claims to be able to guess any
password after seeing it typed twice -- I can't do it but I have seen
him do it.

Several people referred to pass phrases and I agree they are a good idea
for some users (I've used them for 10 years on my pgp key). The problem
with pass phrases is that they assume the user is a competent typist,
many of our users are not and would find typing 20 characters with no
feedback very daunting.  (School kids are not formally taught typing in
NZ, even with all the computers currently in schools :(  and many of my
colleagues still hunt and peck after 10 (or more) years using
keyboards).  

I really like Dave Dittrich's idea for making that one password that you
use on many systems safer by adding something predictable (to you) to
your standard password or phrase.  I will be slightly changing quite a
few passwords on on Monday!   It is such a simple idea that I am
surprised that it isn't better known.  Thanks Dave!

I have often used slight variations on an single password before but the
idea of systematically tying the variation to something in the host name
(of some other attribute of the machine) had not occurred to me.

Cheers, Russell

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 307 bytes
Desc: This is a digitally signed message part
Url : http://www.dshield.org/pipermail/unisog/attachments/20050227/696d5b59/attachment-0002.bin


More information about the unisog mailing list