Re: Password Cracking

• Previous message: Martin Ireland: "Re: Strong Passwords Revisited"
• In reply to: Lohkee: "Password Cracking"
• Next in thread: Lohkee: "Re: Password Cracking"
• Reply: Lohkee: "Re: Password Cracking"
• Reply: Mark Gordon: "Re: Password Cracking"
• Reply: Ernst-Udo Wallenborn: "Re: Password Cracking"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]

From: Fireglyph <fireglyph@gmx.net>
Date: 24 Jan 2003 01:48:05 GMT

Hi Lohkee!

I think you're somewhat confused yourself about a premise which is
important for your argumentation. Let me elaborate on that please,
in the hope that things become clearer and will help others to
understand your point (which is a good one, IMO).

Lohkee <Lohkee@worldnet.att.net> wrote:
>
> 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. As the numbers of possibilities increase, so do the odds
> against someone being able to guess the correct sequence. Lotteries are a
> perfect example of this.

This is only half of the truth. The strength of a password doesn't only
depend on the size of the "pool" it was taken from, but also on the
probability with which it is chosen from that pool. The problem is not
comparable to a lottery, in which all events (numbers) can occur with
equal probability!

So what we have to take into consideration here is not only the size
of the keyspace, but two different probability distributions:

Dist U: The one users choose their passwords from.
Dist A: The one an attacker chooses his passwords from.

The risk of someone breaking into a user's account now depends on
the ability (or luckyness) of a hacker to guess (come close to) the
probability distribution U from which users are taking their passwords.

A simple example:

Users can choose from 5 different numbers: 1, 2, 3, 4, 5.
That is, the size of the keyspace (= pool) is 5.

In reality, although they *could* choose from 5 different numbers,
users *most often* are using the numbers 3 and 4.

Dist U:
Prob(1) = 0.04
Prob(2) = 0 1
Prob(3) = 0.4
Prob(4) = 0.3
Prob(5) = 0.16

In case the hacker hasn't any pre-knowledge of Dist U, all he can do
is to assume that the numbers are equally distributed. With a brute
force attack, he has to put the numbers into any sequence and since
he assumes all numbers are equally distributed, that sequence can be
arbitrary. For example, choosing the sequence 1, 2, 3, 4, 5, a hacker
will find the password in step 3 or 4 *most of the times*.

But in case the hacker can make a good guess about or even knows
Dist U, it is much better for him to try the numbers in the order
of descending probabilities, that is 3, 4, 5, 2, 1. With that strategy,
he will find the password of a user in step 1 or 2 *most of the times*,
which is much faster, of course.

Now, the "strength" of a password depends on the keyspace and the two
distributions dist U and dist A actually chosen by a particular user
group and a particular password cracker (with a particular word-list).
But it is important always to consider *both* distributions.

For example, if we assume we had some device which could generate
the passwords for us truly randomly, all passwords generated would
be equally distributed. Under the assumption that hackers will try out
each password with equal probability and in arbitrary sequence,
there are no strong or weak passwords *at all*.

But once this assumption breaks, things may look differently.

I think Ernst-Udo Wallen has overlooked the problem that once there
is a password generation scheme, which changes the entropy of course,
and the hacker knows about that entropy, he doesn't need to try some
words at all. That is, if he finds out about the password generation
policy, he can safely assume that some words have Prob=0.

Entropy is a function of the language and once you have a different
language (= password generation scheme), the entropy changes. The only
reason why dictionary attacks work is because the hacker has some
pre-knowledge about the language (German, French, etc.) users are
choosing their passwords from - and because the entropy of those
languages is well-known.

Words from a Japanese dictionary can be strong passwords if you know
beforehand that most of your attackers will only try English, German
or French dictionaries. It all depends ...

In other words, you're completely right that if *all* users are
following the advice of security experts, hackers could adjust their
password crackers to the entropy underlying the well-known password
generation scheme and suddenly former weak passwords could become
strong passwords - and strong passwords could become weak ones.

The problem you're pointing us to is that once there is *any*
scheme (bias) involved in our distribution, security depends on keeping
the generation scheme secret. That is security by obscurity and that
is always bad.

Can we do better? Yes, we can.

There is *one* "scheme" which is superior to all others, because only
words are generated which are equally "strong". I already mentioned it:
the best way to create secure passwords is to generate them truly
randomly, using the whole keyspace (that is, without any bias = scheme).

Since it is likely that hackers will still try dictionary attacks, we
could reject passwords from dictionaries and those from the known
password generation scheme you mentioned. As long as the keyspace is
big enough and the rest of the words is generated truly randomly,
this wouldn't make a big difference.

Hope that helps,

Fireglyph

• Next message: Chucky: "Service access to share possible?"
• Previous message: Martin Ireland: "Re: Strong Passwords Revisited"
• In reply to: Lohkee: "Password Cracking"
• Next in thread: Lohkee: "Re: Password Cracking"
• Reply: Lohkee: "Re: Password Cracking"
• Reply: Mark Gordon: "Re: Password Cracking"
• Reply: Ernst-Udo Wallenborn: "Re: Password Cracking"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]