From: dlv@bwalk.dm.com (Dr.Dimitri Vulis KOTM)
Date: Tue, 15 Jul 1997 19:41:44 +0800
To: cypherpunks@toad.com
Subject: Re: Fuck the Usenet Cabal
In-Reply-To: <Pine.LNX.3.91.970713111822.728B-100000@fatmans.demon.co.uk>
Message-ID: <RaqV0D8w165w@bwalk.dm.com>
MIME-Version: 1.0
Content-Type: text/plain



Paul Bradley <paul@fatmans.demon.co.uk> writes:

> > ObCrypto: I was offered a 76GB changer for $350.  I thought of the followin
> > demo application: a user e-mails a piece of a Unix passwd file (password+sa
> > to a server, which looks up a password that works.  Problem is, 76GB doesn'
> > seem sufficient for the lookup table. :-( (Assume infinite time available
> > on a fast box.)
>
> I have to confess ignorance over the form of the password in the unix
> passwd file, how much salt is used, does it vary from ?nix to ?nix or is it
> pretty standard? Maybe a small(ish) lookup table/ dictionary attack could
> be mounted using this.

Suppose that 'foo' is a valid password for the account 'bar'. Unix computes
crypt(3)[similar to DES] using 8 bytes of zeros as the plaintext and the
password (56 bits) and the 'salt' (the 12-bit time-stamp of when the
password is set) as the key. Then it stores the salt and the (64-bit) result
of crypt, often in a place where regular users can read it.

When some program wants to verify that 'baz' is indeed a password for 'foo',
it extracts the salt and the encrypted string from the password database,
computes crypt(3) of salt (from the database) + the password being tried,
and sees if it matches the encryption result in the database.

This was designed by Robert Morris Sr [who really deserves more fame than
being the father of Robert Morris Jr of the worm fame] and Ken Thompson.

The purpose of the pseudo-random 'salt' is to make sure that if two accounts
have the same password, they'll still have different encryption strings in
the database (almost always).

Thus, given 12+64 bits of input, we want to get the 56 bits of output; and
the vast majority of 12+64 inputs can't happen.

A well-known attack (implemented by widely available programs such as
"crack") is to try various words from a dictionary with the 'salts' used by
the traget account(s) (usually using not the (slow) crypt(3) from the
library, but a highly optimized version of it. [The guy who wrote the
"Camel" Perl book got caught doing this at a place where he worked as a
consultant, and was prosecuted and convicted.]

To prevent dictionary attacks, many sites no longer make the encrypted
strings "easily" available to users; programs must use an API to check if a
supplied password matches. Unix admins call this "password shadowing".

---

Dr.Dimitri Vulis KOTM
Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps