Re: Password Cracking

From: Fireglyph (fireglyph@gmx.net)
Date: 01/24/03


From: fireglyph@gmx.net (Fireglyph)
Date: 24 Jan 2003 07:32:22 -0800

Mark Gordon <spamtrap@flash-gordon.me.uk> wrote in message news:<20030124114600.1747d3b6.spamtrap@flash-gordon.me.uk>...
> On 24 Jan 2003 01:48:05 GMT
> Fireglyph <fireglyph@gmx.net> wrote:
> [...]
> A very good explanation. I've snipped most of it since I agree with it.
> However, it ignores a problem with the people involved. If you use truly
> random passwords then there is a high probability of the password being
> one the user will find hard to remember (people can generally remember
> a word more easily than a non-word, and something close to being a word
> more easily than something that *looks* like a random sequence of
> characters). So you are increasing the probability of users writing down
> the password and hence the risk of security breaches through people
> finding written down passwords.

You are right. I have thought about the whole problem again and I think
I have found what is really confusing so many people in this thread,
including myself and Lohkee. Like many others I made the mistake to mix
up the words "strength" and "risk". To gain insight into the problem, one
has to differentiate cleanly between them.

The error I made was to state that the *strength* of a password depends
on two distributions, namely the one underlying the chosen password generation
scheme and the one the hacker generates passwords from. This is not true.

Instead, the *strength* of a password is *defined* by the entropy of the
password scheme we have chosen, which means that it only depends on one
distribution. The strength of a password therefore is completely independent
from the actions of the hacker. The strength is a feature of the
language/scheme the password was chosen from and the entropies of several
different known schemes can be calculated, letting us compare the schemes
to each other. It is important to calculate the entropy, because otherwise
one might choose a scheme which generates a lot of weak passwords.

Natural language has a low entropy. Therefore it is a bad choice to generate
passwords from a dictionary. Truly random generation has highest entropy.
In general, a password scheme is the better the bigger the keyspace is and
the more randomness is involved in the generation process.

This is important, because someone could have the idea to propose a simple
substitution scheme. For example, the scheme could replace all vowels by
special characters: a=#, u=*, o=(, i=%, e=$. Though the passwords generated
will look like gibberish to any human being, this scheme has the same
entropy as natural language, so the passwords have the same strength
(or, in this case, weakness).

Two distributions come into play though if we want to calculate the *risk*
of a hacker finding our password by a dictionary attack or brute force
(just for the moment, let us assume that he has no other possibilities).

Then, if we can make a well-educated guess about the strategy the hacker
will choose to attack us, things look a bit differently.

For example, if we *know* that the hacker tries passwords blindly with
equal probability, the *risk* that he will find our password is the same
for strong and weak passwords alike.

If we *know* that the hacker won't try words from a dictionary, there
is no risk at all in choosing weak passwords, because they won't be tried.

If we *know* that the hacker will only try English words, it is completely
safe to choose passwords from a German dictionary.

The problem is, in most cases, we don't know. Since many people take
passwords from a dictionary, we could assume that a hacker will try
words from a dictionary first, but that's all. So the best we can do
is to use a good password generator, because password strength is
independent from the distribution the attacker chooses in the sense that
strong passwords remain strong over all possible probability distributions
the attacker *could* choose.

As we can see, as long as the ability of a hacker to find our passwords
depends on cracking a password file only, the advice to use strong
passwords is a reasonable one.

The problem begins if we want to estimate the *overall risk* of someone
getting our passwords, coming back to your point (and Lohkee's, too).
The overall risk doesn't depend on the strength of our passwords alone, but
on many other factors.

1.) Strong passwords are often hard to remember, so they will be written
    down. We have to weight the probability of a user writing down his
    password and a hacker finding it against the strength of the password.

2.) Passwords could be transfered in plain text over the wire, allowing
    sniffers to capture them. The risk doesn't depend on the strength of
    the password any longer.

3.) The hashes used for "encrypting" the password could be weak. Lanman hashes
    are a good example. (The problem here is that it doesn't matter how
    long and complicated users will make their passwords, but that the
    maximum strength is restricted to 95^7 different words anyhow.)
    
4.) Administrators and other people could be bribed by someone to tell
    their passwords. The risk doesn't depend on the strength of the
    passwords.

5.) ... (please, continue it yourself)

Does it mean now that choosing strong passwords becomes obsolete?

Of course, it doesn't. By choosing a strong password, you have minimized
the risk of someone being able to attack you with a dictionary attack in
case he is able to steal the password file or sniff the network. Not less,
not more.

You have handled one vulnerability of your system as good as you can,
but to minimize the *overall risk* other additional steps may be necessary.

Thanks for your answer,

Fireglyph