Re: Choosing secure passwords - Feedback solicited

From: Lohkee (lohkee@worldnet.att.net)
Date: 04/03/02


From: "Lohkee" <lohkee@worldnet.att.net>
Date: Wed, 03 Apr 2002 02:18:31 GMT

Strong Passwords & Password Cracking
Copyright (C) 2002 by Lohkee
All Rights Reserved

The security community repeatedly tells us that a strong password will be
much more difficult for an attacker to break than will a weak one, and
because of this, we should encourage the use of strong passwords in order to
protect our systems from those who would attempt to gain unauthorized access
by cracking passwords. The wisdom of this advice is continually reinforced
by an army of security consultants who are more than happy to demonstrate
the ease with which commonly available password cracking software can
recover so-called "weak" passwords, i.e., words taken from a dictionary,
common names, etc.

These same experts frequently recommend the use of special password filters
designed to systematically enforce password complexity by disallowing any
password that does not meet some predefined rule set, or the running of
password cracking software in conjunction with the appropriate feedback to
any user unfortunate enough to have their password "cracked" by the program.
Some experts even recommend using both techniques simultaneously (although
to do so is a rather bizarre contradiction when you stop and really think
about it). Regardless of the method chosen, the goal is essentially the
same, to reduce risk by enforcing the use of strong passwords.

Passwords are generally considered to be reasonably "strong" if they are
eight or more characters in length and contain at least one character from
each of the following four sets: uppercase alpha, lowercase alpha, numeric,
and punctuation or other special characters. Passwords constructed using
this (or any similar) set of rules are inherently stronger than words chosen
from a dictionary because they are by design much more difficult to attack.
Looking at an example of each ("#4a!F%H2" as opposed to "zucchini") we can
easily see why; and how running password crackers to identify and eliminate
weak passwords will improve the overall security of our systems. At least
this is what many security consultants would very much like for you to
believe.

Unfortunately, passwords that follow these commonly prescribed rules are
only "strong" in an absurd fantasy world where the only possible method of
cracking passwords is by a dictionary attack. In a world where more than
one method exists for the cracking of passwords, you may want to consider
the following: If you compare any two passwords of equal length you will
find, in many cases, that selecting what security professionals insist would
be a very strong password, as opposed to randomly choosing a word that might
be found in any dictionary, will actually result in choosing a password that
is provably much easier to crack! A brute force attack, for example, will
discover the password "#4a!F%H2" long before it will ever find the password
"zucchini" because the ASCII representation for each character is
numerically lower. Conversely, a dictionary attack will only be able to
crack "zucchini" if that word happens to be in the dictionary used by your
attacker. The inherent "strength" of a password such as "#4a!F%H2" is an
illusion. It appears to be stronger only because the sequence of characters
forms a pattern unfamiliar to the average human being; to a computer, it is
just another string of ones and zeros. In fact, at the binary level one
password appears pretty much the same as another.

01001100 01101111 01101000 01101011 01100101 01100101
01000000 01011110 01011000 01110001 00110011 00100001

The simple truth is that passwords resistant to one method of attack may be
extremely susceptible to another, and prescribing or enforcing rules that
fail to consider this basic fact, is a very serious mistake.

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. This is obviously good
advice that just happens to illustrate an extremely important point. The
word "password" is not inherently weak because of its composition; it is
"weak" only because of its unique association within an extremely limited
context. There is a big difference in not choosing a password that is in
some way "connected" to yourself, and choosing a password that may be found
in some dictionary but is in no way associated with you or your particular
environment. The security community routinely overlooks this subtle, but
extremely important, distinction. Somehow good advice has morphed from "do
not use words associated with yourself" to "do not use words found in any
dictionary" to "passwords must not be found in any dictionary" to
"passwords should contain at least one of each of the following characters"
to "passwords must not be found in any dictionary and must contain at least
one of each of the following characters." The latter is one of those very
bad ideas that just happen to sound good. It is a wolf in sheep's clothing!

Ignoring for a moment those words that might somehow be associated with a
particular user because of some personal interest or a family connection,
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 anyone who has ever played the lottery is painfully
familiar with). Obviously, the systematic enforcement of any rule that
arbitrarily eliminates a significant number of those possibilities serves
only to weaken the overall mechanism because the attacker has fewer
possibilities to try thus increasing the probability of success. When too
many possibilities are eliminated, we also risk opening up avenues of attack
(such as the brute force) that otherwise may have been discarded as
impractical. Most of the commonly prescribed formulas for so-called
"strong" passwords fall into both of these traps.

Suppose, for example, we have a rule which states that all passwords must be
eight characters in length and contain at least one character from each of
the following four sets: uppercase alpha (26), lowercase alpha (26), numeric
(10), and punctuation or other special characters (33). Assuming an
eight-character password, an analysis of this rule would yield the
following: Without the rule, a user's password can be from one to eight
characters in length, and may use any one of ninety-five characters in each
position. The total number of passwords possible is (95^1 + 95^2 + 95^3 +
95^4
+ 95^5 + 95^6 + 95^7 + 95^8), or 6,704,780,954,517,120. With the rule in
place,
the user's password must be eight characters in length and include at least
one character from each of the four sets. The number of password possible,
assuming an eight-character password for side-by-side comparison, is now
only 2,297,087,021,477,818.

By enforcing this rule, we have (in the name of hardening our system against
an attacker attempting to gain unauthorized access by cracking passwords)
just eliminated 65.74% of the possibilities that the attacker would
otherwise have had to of tried. In the process of eliminating a large
percentage of the possibilities, we have also managed to transform the
simple brute force attack from an impractical means to the preferred means
of cracking passwords. Since the rule has effectively eliminated 65.74% of
the possibilities for us, we no longer have to waste time testing them. For
about $3,000.00 we could build a system capable of testing about 500,000,000
keys/second. A brute force attack specifically designed to test only those
passwords meeting our criteria for a so-called "strong" password would take
about 53 days to test all of the possibilities and have a 100% success rate.
Try that with a dictionary attack! It could be argued that an outsider
would have no way of knowing if the rule was in effect and would therefore
still have to try all of the possibilities. It being a trivial task to
discover the rule notwithstanding, what about all of the insiders who do
know about the rule?

We can prove mathematically that 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, and we can prove
mathematically that reducing the number of possibilities weakens the
mechanism. We can also prove mathematically that passwords, which follow
the generally accepted and prescribed rules (rigorously promoted by the
government and the professional security community) for so-called "strong"
passwords weaken the mechanism considerably and are a great deal easier for
the attacker to crack than "weak" passwords by using methods other than a
dictionary attack. The truth is that rules designed to systematically
enforce so-called "strong" passwords, unless very carefully crafted, may
actually perform contrary to their intended purpose. At the risk of being
redundant: There is a world of difference between simply recommending that
users choose a password containing a mix of characters and systematically
enforcing such a rule. All passwords are still equally possible in the
first instance, thus preserving the inherent strength of the mechanism. A
significant number of possibilities are eliminated in the second, thereby
accomplishing exactly the opposite of the desired result. You should test
and fully understand the practical effect of any proposed password rule
prior to implementation and flatly reject any that significantly reduce the
number of possibilities. They serve no purpose other than to weaken the
password mechanism, frustrate users, and create a false sense of security!

I am not suggesting that systematically enforced password rules, per se, are
a bad thing. Looking at the following table we can see that a rule
requiring the user to choose a password of at least eight characters (with
no other restrictions) would not significantly reduce the overall number of
possibilities (about 1%), but would still eliminate a large number of "easy"
passwords, including a lot of commonly used words, names, etc.

95 1 95
95 2 9,025
95 3 857,375
95 4 81,450,625
95 5 7,737,809,375
95 6 735,091,890,625
95 7 69,833,729,609,375
95 8 6,634,204,312,890,625

We could further strengthen this rule (again without appreciably affecting
the overall number of possibilities) by filtering out a few of the more
"obvious" passwords such as Password, PASSWORD, password, variations of the
user's logon name, any password that is simply a string of the same
characters repeated, etc.

Many within the professional security community recommend running password
crackers as a means of identifying network vulnerabilities arising from the
selection of weak passwords by system users. The results are usually quite
spectacular in that it is generally possible to crack about 90% of the
passwords on a typical system within an hour or so. However, running
password crackers is a waste of resources that serves no real purpose other
than to line the pockets of those who offer this so-called service (directly
or indirectly), which in my opinion, is an excellent reason to question the
integrity or professional competency of anyone who promotes it.

The idea of cracking passwords as a means of identifying or eliminating
vulnerabilities caused by the selection of weak passwords is seriously
flawed for a number of reasons, the most obvious of which, is that the
recommended course of action is already known without going through the data
gathering process. Cracking passwords is not a prerequisite for developing
sensible rules to enforce the use of strong passwords; protecting the
system's password file; limiting the number of attempts to enter a password
correctly before automatically locking the account; or defining from what
location/workstation the user will be permitted to access the network.

The number of passwords cracked has absolutely nothing to do with the
strength or complexity of a given password. It has everything to do with
the quality and quantity of resources applied to the task. Any password can
be broken. It takes no more time to crack an eight-character password than
it does to crack a one-character password if you design the attack to take
full advantage of inexpensive and readily available technology. Most of the
commonly available password cracking programs are antiquated in their
approach and do not do this. They are, however, the tools of choice and so
will be the topic of discussion. Since most password cracking programs are
virtually identical in their approach, we will look only at the methods
typically employed as opposed to specific products.

The dictionary attack will discover a user's password, no matter how
complex, if that password happens to be on the word-list used for the
attack. Conversely, even the weakest password will remain a secret if it is
not. What conclusion should we draw if the password cracker fails to
uncover any (or only a few) passwords? Do we automatically infer that users
have selected "strong" passwords, or should we question the quality of our
word-list? How should the quality of a word-list be measured, and against
what standard? If different word-lists give different results, then a
conclusion concerning overall vulnerability based on any one word-list would
be foolish; and if the attacker happens to have a better word-list than you,
worthless.

The "brute force" attack will always eventually discover a user's password.
Conventional wisdom discounts this type of an attack as impractical because
of the prohibitive amount of time needed to test every possible password.
This may well be true on an older single processor stand-alone machine;
however, such a myopic view of the world ignores the enormous amount of
distributed processing power readily available to anyone using the Internet.
A skilled attacker can easily harness the combined computational power of
thousands of machines and launch an extremely efficient brute-force attack.
The DESCHALL group has proven the effectiveness of this method. Using only
the idle CPU cycles of the participating clients they were able to achieve a
rate of seven billion keys tested/second. Using their work as a model we
can see that it would take only about eleven days to crack any password up
to eight characters in length. By today's standards the equipment they used
was prehistoric (they describe the key test rate of a 200 MHz Intel client).
Think of the possibilities made possible by inexpensive machines stuffed
with dual 2Gb processors and lots of memory! It is well within the
financial reach of most home users to build a system capable of cracking an
eight-character password in about 53 days (Assuming the attacker were to
design a customized brute force attack to compensate for systematically
enforced rules governing the creation of strong passwords. Remember, the
currently accepted rules for strong passwords automatically toss out 65.74%
of the passwords that an attacker would otherwise have needed to test if the
rule had not been put into effect!). The point here is that technology has
made conventional wisdom obsolete, and any conclusion regarding
vulnerability based on an obsolete truth, is absolutely worthless.

Is it reasonable to conclude that an attacker could easily gain access to a
system by guessing passwords if, by using a password cracker, we discover
that a large number of users have selected a weak password? The answer is,
"No!" Running a password cracker against the entire password file on a
dedicated system at extremely high speeds is one thing (essentially an
unlimited number of attempts to identify a given password). Attempting to
identify the password for a particular user within a very limited number of
attempts (usually three) across a network before the account is
automatically disabled, is quite another. Which three passwords, out of the
billions of possibilities available, should we try? Attempting to equate
these two very different scenarios is absurd. Hackers would be having a
field day if the results obtained by password crackers were truly
representative of anything even close to reality.

Many within the security community recommend the use of password filters and
password crackers together. The argument for this irrational behavior
sounds pretty good until you stop and really think about it. First of all,
if passwords that meet the rule represent an acceptable level of risk, it
makes no sense to try and crack them. It is a contradiction! Some analysts
respond to this by suggesting that cracking passwords will help them
fine-tune the password filter. The many issues previously discussed in
regard to the problems with "strong" passwords and word-lists
notwithstanding, it is a given that any password can be cracked. Therefore,
this exercise, taken to its logical conclusion, leads to a point where no
password can pass the test of acceptability! At some point you have to
compromise on password complexity or users will form a lynch mob out of
sheer frustration, which takes us back to square one, if passwords that meet
the rule represent an acceptable level of risk, it makes no sense to try and
crack them.

Ironically, the very exercise intended to identify and eliminate
vulnerabilities may create them in the process. Running a password cracker
compromises the integrity of the password file, and in so doing, nullifies
the system's audit trail from an evidentiary perspective because, at least
for some period of time, more than one person had access to the password for
a given account and could therefore be responsible for the actions shown on
the audit trail. Every user on the system will have to change their
password each time you run a password cracker. Having a list of
user-accounts and their associated passwords (even when those passwords are
no longer valid) is an enormous tactical advantage for anyone attempting to
gain access to a system by deducing passwords, as it enables them to focus
their attack by making educated guesses based on a user's previous password.
The operating system routinely creates copies of files without the user's
knowledge in obscure places such as the swap file or in timed recovery files
that are often readable by anyone with access to the system. Erased files
are easily un-erased, even on NTFS, with the proper tools. Unless you can
absolutely guarantee the security of the cracked password file, and any
copies that may have been made, you really have no way of knowing where that
information may eventually end up or how it may be used.

The bottom line is this:

1. You do not have to run a password cracker to enforce the use of strong
passwords or to mitigate risks caused by the selection of weak passwords.

2. There are no standards for password cracking. The data obtained from a
password cracker is purely subjective making it completely worthless for any
kind of rational analysis.

3. Running a password cracker creates serious vulnerabilities that were not
there before.

4. Every user will be forced to change their passwords (at the end of each
password cracking exercise) in order to restore integrity to the system's
audit trail.

5. When all is said and done, what guarantee is there that a user's new
password will be any less "crackable" than their old one? The exercise
becomes an endless loop.

Cracking passwords is a pointless exercise that really demonstrates nothing
at all other than perhaps the ease with which it is possible to con people
who do not know any better.

In a sense, this whole discussion is pointless. It is a given that any
password up to eight characters in length is easily cracked by even a
marginally competent attacker. In a year or so, the same will also be true
for ten character passwords. Does this mean that passwords are outdated or
that we should force the user to remember even longer passwords? Not at
all, if we keep things in perspective. Remember, running a password cracker
against the entire password file on a dedicated system at extremely high
speeds is one thing, attempting to identify the password for a particular
user within a very limited number of attempts across a network is quite
another.

There are a number of things you can do to mitigate the risk of an attacker
gaining access to your system by cracking passwords:

1. Set the number of attempts at entering a password to two, or at most,
three.

2. Define the time (days and hours) that a user is allowed to log on to the
system.

3. Specify the terminal/s that a given user is allowed to logon to.

4. Prohibit remote logons or direct remote access to the workstation unless
it is ABSOLUTELY necessary. Any user claiming to need such access should be
made to prepare a formal justification for management review. All other
avenues of satisfying the users needs should be exhausted before granting
this request. Any accounts having remote access should be rigorously
monitored.

5. Limit access to the system password file.

In conjunction with a reasonable rule for strong passwords, the above steps
will make it all but impossible for a remote user to gain access by guessing
passwords. These protective measures can be put in place at any time. It
is not necessary to waste resources by running a password cracker.

Lohkee!