Re: Strong Passwords Revisited

From: Ernst-Udo Wallenborn (ernst-udo.wallenborn@freenet.de)
Date: 01/21/03


From: Ernst-Udo Wallenborn <ernst-udo.wallenborn@freenet.de>
Date: 21 Jan 2003 22:46:33 +0100


"Lohkee" <Lohkee@worldnet.att.net> writes:

> Strong Passwords (DRAFT FOR COMMENT)

> Ironically, it results in passwords that are provably weaker and thus easier
> to crack.

I seriously doubt that.

> Conventional wisdom states that one should not use the name of a spouse,
> pet, child, etc. for a password because to do so will make it easier for an
> attacker who knows you to guess your password.

No, the attacker doesn't have to know you. There is a limited number
of names on this planet, and trying all of them is a matter of seconds,
at most.

> Passwords derive their strength from the statistical
> improbability of an attacker being able to guess the correct sequence of
> characters chosen by a particular user when there are an extremely large
> number of possibilities to choose from (a concept that most people who play
> the lottery, and routinely loose, are painfully familiar with).

Correct so far, except for s/loose/lose/g;

> Any device
> that eliminates a significant number of those possibilities serves only to
> weaken the overall mechanism because the attacker will have fewer
> possibilities to try thus increasing the probability of success.

This is true only under a very limited set of circumstances. In
particular you assume here that the probability distribution of those
passwords eliminated by the device is equal to the overall probability
distribution of all passwords. This is normally not true, by
design. Password enforcers are designed to specifically exclude the
most probable passwords and so increase the password entropy. That's
the point of using them in the first place!

You seem to think that all passwords are equally likely to be chosen
by a user, and equally likely to be tried by a cracker. If you were
right, password entropy would only decrease with a decreasing number
of possibilities. But if the password probabilities are not
equidistributed, eliminiating the most likely ones will, while
decreasing the number of possibilities, actually increase the entropy.

And entropy is what counts. You want entropy in your passwords,
and you want a lot of it.

> By enforcing this rule for "strong" passwords we have, in the name of
> hardening our system against someone attempting to gain unauthorized access
> by cracking passwords, just eliminated almost two-thirds of the
> possibilities that our attacker would otherwise have had to of tried thus

Losing two thirds of all possible passwords translates to an entropy
decrease of little more than one bit. This is not good, but choosing a
dictionary password usually costs a lot more.

With DES crypt, your password has an entropy of at most 56 bit. If
you use completely randomly generated passwords that use the entire
ASCII set, you get 56 bit. A randomly generated eight-character
password that consists of characters, letters and a few special
characters (say a set of 64=2^6 characters) will give you 8*log_2 64 =
48 bit. Under normal circumstances, that is the most you can expect
from a password. Even if you use MD5 hashes, the additional security
will come only if you use a longer password. A (similar to above)
randomly generated password with 21 characters will have an entropy of
21*log_2 64=126 bit. Thats safe for the forseeable future of this
universe, but remember: you have to actually use those 21 characters.

Choosing a word from a dictionary with 65536=2^16 words will give you
an entropy of 16 bit. That's not the same ballpark. That's not
even the same league. Cracking a 48 bit password requires
2^(48-16)=4294967296 times the amount of work than cracking a 16 bit
password. The incentive for Joe Cracker to use a dictionary
attack before trying anything else is therefore huge.

If now half of your users use a dictionary password, and the other
half proper, randomly generated passwords, then the average entropy of
your passwords is, according to Shannon, 33 bit.

If, on the other hand, you restrict the passwords and forbid using
those from the dictionary, and everybody begins to use randomly
generated passwords (except those passwords that are in the
dictionary), then the Shannon entropy will be

S = \Sum_i p_i log_2 1/p_i bit = log_2(2^48 - 2^16) bit = 47.9999999996641 bit

See? You reduce the number off possibilities yet increase the entropy.
If you take into account that normally a hacker is not even interested
in the average entropy but in the entropy of the weakest password on
the system, the gap becomes even wider.

> Diehard critics will undoubtedly be quick to point out that an attacker is
> far more likely to try "zucchini" before "#4H!F%a2" and attempt to support

yep.

> this argument by referring to the results commonly obtained by running
> password crackers (remember, it is generally possible to crack about 90% of
> the passwords on a typical system within an hour or so using a dictionary
> attack). There are numerous problems with this rebuttal, the most obvious of
> which, is that it has absolutely nothing at all to do with password
> strength. It also attempts to project a conclusion based on results obtained
> under one set of circumstances to another very dissimilar set of
> circumstances. On one hand we have an "attacker" who is literally handed the
> password file which he then runs against a password cracker on a dedicated
> system at extremely high speeds (essentially an unlimited number of attempts
> to identify a given password), on the other hand we have an attacker who
> must first somehow penetrate your system and successfully capture the
> password file (all without ever being detected and stopped - in which case
> you have a far more serious problem on your hands than weak passwords)
> before he can even begin to think about cracking those passwords! Attempting
> to equate these two vastly different scenarios is absurd. Think about it for
> a moment; hackers would have had free reign on almost every system
> imaginable for the past twenty years if the results typically obtained by
> password crackers were representative of anything even remotely close to
> reality.

> demonstration hundreds of times and have yet to see anyone succeed. Frankly,
> if an attacker can capture your password file then it is not going to really
> matter if a password is "zucchini" or "#4H!F%a2", both can be cracked by a
> competent technician within a matter of days. On the other hand, trying to

Well, since "Cracking DES" came out, this statement is, strictly
speaking, true for many unixen. But cracking "#4H!F%a2" requires
specialized hardware and a few hundred thousand dollars, while
"zucchini" will be cracked by an average workstation. And of course,
if your friendly sysadmin has set up your system to use MD5 instead of
DES hashes, you can use longer passwords, and you can be sure that the
MD5 hash of, say "9sd:oziA=an24Gplb%os4!h3;36" won't be cracked during
our universe's life span, while i would not bet much on the security
of "iwantsomefriedgreentomatoes".

> The professional security community, on the other hand, has little to offer
> in rebuttal other than the results generated by password-cracking software,
> which have absolutely nothing at all to do with password "strength" and
> prove only that a given password was on the wordlist used for the test.

If a professional security expert showed you how to open the door to
your house with a common credit card and recommend you to install an
extra lock, would you listen to someone who told you "most burglars
don't have credit cards"? No you would not. If doors can be regularly
opened with credit cards, burglars will have credit cards. If a security
expert can crack your password with a dictionary attack, nothing stops
Joe Cracker from using the same software and crack your password, too.
Do you really think that crackers will look at password cracking software
and say "Gee, this is powerful, but unfortunately, the security experts
know it, so i can't use it"?

-- 
Ernst-Udo Wallenborn


Relevant Pages

  • Re: Strong Passwords Revisited
    ... the attacker doesn't have to know you. ... most probable passwords and so increase the password entropy. ... and equally likely to be tried by a cracker. ... Cracking a 48 bit password requires ...
    (comp.security.misc)
  • Re: Strong Passwords Revisited
    ... the attacker doesn't have to know you. ... most probable passwords and so increase the password entropy. ... and equally likely to be tried by a cracker. ... Cracking a 48 bit password requires ...
    (microsoft.public.win2000.security)
  • Re: Strong Passwords Revisited
    ... >> attacker who knows you to guess your password. ... > most probable passwords and so increase the password entropy. ... and equally likely to be tried by a cracker. ... Even if you use MD5 hashes, the additional security ...
    (microsoft.public.win2000.security)
  • Re: Strong Passwords Revisited
    ... >> attacker who knows you to guess your password. ... > most probable passwords and so increase the password entropy. ... and equally likely to be tried by a cracker. ... Even if you use MD5 hashes, the additional security ...
    (comp.security.misc)
  • Re: Strong Passwords Revisited
    ... >> attacker who knows you to guess your password. ... > most probable passwords and so increase the password entropy. ... and equally likely to be tried by a cracker. ... Even if you use MD5 hashes, the additional security ...
    (comp.os.ms-windows.nt.admin.security)