Re: Password Cracking

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

  • Next message: Chucky: "Service access to share possible?"
    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



    Relevant Pages

    • Re: guest account
      ... > (hacker who's workstation is named Mikel). ... you'll still want to secure your system. ... Choose a good password for all your login IDs [and change all the passwords ... install all microsoft security patches and ...
      (microsoft.public.security)
    • Re: IRC security
      ... >> I have an ecommerce site with a chat place. ... >> It is said that a hacker could attempt to take user names and passwords ...
      (comp.security.misc)
    • Re: Password Cracking
      ... The one users choose their passwords from. ... > In case the hacker hasn't any pre-knowledge of Dist U, ... > distributions dist U and dist A actually chosen by a particular user ... > is a password generation scheme, which changes the entropy of course, ...
      (comp.os.ms-windows.nt.admin.security)
    • Re: US Military bans HTML in emails
      ... Now the MIS departments has tightened security. ... You mean like requiring 6-character passwords to now be "complex"? ... the need for non-alpha characters. ... I assume here that the hacker has somehow obtained a backup tape ...
      (comp.os.vms)
    • Re: Password Cracking
      ... The one users choose their passwords from. ... In case the hacker hasn't any pre-knowledge of Dist U, ... distributions dist U and dist A actually chosen by a particular user ... is a password generation scheme, which changes the entropy of course, ...
      (comp.security.misc)