Re: Password Cracking

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

From: Fireglyph <fireglyph@gmx.net>
Date: 24 Jan 2003 10:20:25 GMT

Hi!

First of all, there was an error in my post. The first part is correct,
but it is not true that all password generation schemes are bad and
therefore interchangable. Because of entropy, password generation schemes
can be compared to each other and can be ordered. That also means that
passwords taken from a language/scheme with a high entropy will always
be stronger than those taken from one with lower entropy. It is still true
though that truly randomly generated passwords will have the highest
entropy and therefore are the most secure.

Lohkee <Lohkee@worldnet.att.net> wrote:
>
> Let me state that before I say anything else that I have just come in from
> dinner and am half crocked. If I go off sideways, please forgive me. I was
> impressed with your response and wanted to reply immeditely. Having said
> that, I am in a quandry. I agree **in principal** with everthing you said,
> *but* still feel a little wary. I do agree that there is another component,
> however, it is still arbitrary in that it relies on several gross
> assumptions (as you pointed out, user's nationality/language vs. attacker's
> nationality/language vs.dictionary used). Because these are unknown
> variables, it seems safer to go with what is known, i.e., number of choices.
> How can we calculate the other with so many unknown values? A good example
> is California where we have a large Hispanic population (I have yet to see a
> "professional" password cracking team use a spanish dictionary -
> ethonocentric to say the least).

You have to take into account the entropy of natural languages *in
general*. Since it is low for most natural languages, the particular
language doesn't play a big role, at least not for "intelligent"
password crackers. An intelligent password cracker wouldn't try words
from a pre-defined word list, but would generate words itself by
combining syllables, trying out those combinations which are most
likely over *all* spoken languages first. Moreover, since dictionaries
are public, it shouldn't be too difficult to assemble a nice collection
of word lists from all over the internet. I only tried to give an
example. (All this under the assumption of course that the passwords
were taken from a natural language.)

The big difficulty you seem to have is that you aren't ready to make
any assumptions about the hacker's word lists. In fact, you don't want
to make *any* assumptions at all. Without reality, I could agree with you,
but there is a reality out there which can be explored and which can be
used to *our* advantage.

That's where password crackers come in.

Deriving a statement about the usefulness of password crackers and
the bad choice of passwords from one single run of a password cracker
in one single company is rubbish. Of course, we need a sample big
enough to be representative. Let us assume that testing 1000 companies
would suffice. Now, if we find out that in most cases 90 % of all
passwords can be found with a password cracker, what do we know?

What we know is that 90 % of all users (in the real world!) actually
use passwords taken from our word-list, in this case natural language
(= low entropy). Once we make this information public, hackers all over
the world can make a good guess about the distribution most people are
taking their passwords from. In other words, having empirically shown
that most users are using such passwords, the hacker has good chances
to break into a system by using LC4 with a word-list assembled from
different languages (which he can get easily online).

Since he has good chances, why shouldn't he use it?

IMO, because it has become general knowledge that most users choose
passwords which are easy to remember and are taken from a dictionary,
we *can* safely assume that most hackers would first try out word-lists
with words from a dictionary.

So we shouldn't use them. What else should we use? Rules? If we do,
we have to be overly careful to choose those which will produce
passwords with high entropy. Again, the best choice is to generate
all passwords equally distributed truly randomly and exclude those from
dictionaries, because it is highly likely that hackers would try out those
first.

Moreover, entropy doesn't only come from special characters, but from
the randomness involved in the generation process. A password like
"#A!+Opz/" is as good as "TzPMjkL" if both were generated truly
randomly, but "Orange" is definitely a weak password.

>> 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.
>
> This is precisely my point with regard to the typical rules for strong
> passwords. It is not that the advice is bad, per se, but when the advice
> becomes a rule that is systemicaly enforced, we create the above situation
> and "strong" passwords become provably "weaker." I am not even against
> systemically enforced rules, we just have to make sure the rules do not have
> the unforseen consequences.

I fully agree with you.

>> 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.
>
> Again, I agree **provided** we do the math and know exactly what we are
> eliminating, and its effect on the overall pool - the point here is that we
> still need to make sure that our rule does not unintentionally make other
> attacks feasible (brute force) because we have eliminated too many
> possibilities.

That's what I said - the keyspace has to be big enough. ;-)

> I believe that we could use 9 char randomly generated
> passwords (which automatically eliminates many proper words in all
> languages) and format them into chunks, i.e., like a social security number
> to make them easy to remember.

Let me think. With 95 possibilities for printable chars and under the
assumption that they are generated truly randomly (that is, by throwing
a special dice), that would make 95^9 = 6.3 * 10^17 = 60 bit of entropy.
Not bad. Under your own assumption (you make some, too ;-) that it is
possible and feasable to try 1 billion keys per second, it still would
take about 20 years to break such a password from our today's
perspective.

> I am confused. Your response seems more titled towards my strong password
> paper that it does PW cracking.

Sorry, I first wanted to include something about password crackers, too,
but hadn't the time to do so at the end.

> Because of the many other issues I raised with PW cracking I am
> still very much against it. I would, however, be **very** interested
> in your thoughts on that subject and the points raised within my paper.
> Email to me is fine, or to the group.

I more or less agree with you, but at the moment I don't have the time
to comment on all those points. Maybe later.

Many greetings,

Fireglyph

PS: Have a look at
http://www.stack.nl/~galactus/remailers/passphrase-faq.html

Relevant Pages

  • Re: Safe password?
    ... >> but as was pointed out by others, what kind of characters? ... >> that gives you the theoretical ability to put 512-bits of entropy into the ... >> yes I do have passwords that I memorized in octal, ... >There are plenty of European languages which provide quite a few more ...
    (sci.crypt)
  • RE: [fw-wiz] strong passwords (was Radius/MS ISA stuff)
    ... When they see that you can find passwords so easily, they will start demanding better passwords. ... difficult to convince them to go much further past 6 characters. ... entropy per ... bits than DES) but not a home computer assuming MD5 is not harder than ...
    (Firewall-Wizards)
  • Re: MD5 for passwords
    ... lessen the entropy present? ... would not be such as to make the hash less secure than than passwords. ... amount of entropy. ...
    (sci.crypt)
  • Re: MD5 for passwords
    ... the hashes are publicly available. ... MD5 ten thousand times) to make dictionary search as expensive as ... lessen the entropy present? ... would not be such as to make the hash less secure than than passwords. ...
    (sci.crypt)
  • Re: ssh gives "Permission denied, please try again"
    ... possibly have enough entropy to be secure. ... as secure as those Debian generated keys... ... If you always pick passwords whose first four letters are 'A' you're ... I've seen a lot of dictionary attacks, ...
    (uk.comp.os.linux)