On Fri, 6 Apr 2001, Elias Levy wrote:
> * L. Adrian Griffis (dt26453DSTSYSTEMS.COM) [010406 23:21]:
> > Salting does not make it difficult to see if a specific account has
> > the password you are trying, because, as you suggest, you can and
> > must include the salt in your effort to "encrypt" the password to
> > check against the stored version of the "encrypted" password. What
> > salting does is make it difficult to encrypt a password once and
> > check to see if ANYONE on the system has that password. To see if
> > ANYONE of a number of users has the guessed password, you must
> > encrypt the guessed password for each of the possible salt values
> > in the set of users you want to test you guess against. So if the
> > variety of salt values is a sizable fraction of the number of users
> > on your system, the cracker doesn't get much of a break for testing
> > the same passwords against all users on the system.
>
> More precisely salting increases the space costs of a precomputed
> dictionary attack, as you are required to precompute the dictionary
> for every possible value of the salt.

That's an interesting angle, but I don't remember hearing that when
I first started learning about Unix security.

It may seem like I'm nitpicking here, but I find myself teaching
people about Unix security a lot, and it is often useful to talk
about the history of these various security issues. The point you
raise, Elias, is quite relevant, particularly now that an attacker
could hold a database of precomputed encrypted password to password
mappings on relatively inexpensive hardware. But for the sake of
understanding the history of this issue, it would be interesting
to know when the precomputed dictionary attack problem began to
be significant.

As I recall, the password encryption scheme for Unix that I heard
about was based on an analysis of some version of a World War
cypher machine. This was soon replaced by the "encryption"
scheme we use now, which, if I remember right, modifies a well
known constant with the salt, and then iteratively DES encrypts
the constant 25 times using a key derived from the supplied
password. At the time that this scheme was cooked up, computing
power was, as you might expect, relatively scarce and expensive,
by modern standards. These "encrypted" passwords were available
to all on the system to read in the second field of the password
file (/etc/passwd). This was considered safe, at the time, because
the time required to conduct a brute force attack was long and
would draw attention to the attacker. For the most part, system
administrators were the good guys, and hardware was expensive enough
that the script kiddies that we've come to know and love now could
never have afforded to have there own private machine at home that
they could use to conduct an effective attack in private. Daniel
Klein had not yet written his paper about how poor user password
typically were, so one might still have imagined that a precomputed
encrypted password to password map would have to be too large to
be practical before it could do any good.

All of the historical explanations that I've read for using a salt
and for moving passwords into a "shadow" file are based on increases
in CPU performance and more efficient DES algorythms rather than on
the possibility of precomputed dictionary lookups. Clearly, the
precomputed dictionary lookup issue is significant now, but it would
be interesting to know when historical documents show that this issue
began to become a real theoretical concern and when it progressed to
a practical concern. Also, is there evidence now that precomputed
dictionary attacks have been seen in the wild?

Thanks

Adrian

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]