Newsgroups: alt.security
Subject: Re: passwd security check
Summary: Two questions about encrypted passwords
Expires: 
References: <1992Jul22.190827.30077@iitmax.iit.edu>
Sender: 
Followup-To: 
Distribution: 
Organization: Princeton University
Keywords: 

In article <1992Jul22.190827.30077@iitmax.iit.edu> technews@iitmax.iit.edu (Kevin Kadow) writes:
>
>Can somebody point me to a program that will do a security "audit" on the passwd
>file, e.g. reporting (either in a file or as e-mail to the concerned parties)
>when 2 or more accounts have the same password, and other "holes" that would
>not be found by crack?
>

	Not sure that such a thing is possible, in the general case.
Lemme consider two cases:  the easier case first, of course :-).  User
A and user B both have the same password, and they *happen* to both have
had their passwords encrypted with the same salt.  Happy day! Now you
can just compare the encrypted passwords - if the encrypted result is
the same, *probably* the unencrypted passwords are the same.  (This is
still an open question, as far as I know.  Almost everyone I've asked
has responded with some variation of "I don't really know, but I don't
think the likelihood of 2 different passwords encrypting to the same
result is very high.")

	Ok, so that was the easy case - and the case taken care of by
some ``cut -d: -f4 /etc/passwd | sort | uniq -d''ish type filter.  Now
what happens if User A and user B both have the same password, but
their passwords were encrypted under a different salt?

	This is tougher, as far as I know.  (understatement,
understatement :-)   I wonder if it's possible to generate what the
result of encrypting a password with salt X will be, given only the
result of encrypting it with salt Y.

	Let me restate.  Lemme call 'E(p,s)' the encryption function,
where 'p' is the password and 's' is the salt.  The easier case asks
if this is possible:

[1]	E(p,s) =  E(q,s)		with p,q two different passwords

The second (tougher) case asks if a function 'f' exists so that:

[2]	f(E(p,s),s,t) = E(p,t)		with s,t two different seeds



	My intuition would suggest that satisfying [2] is at least as
hard as satisfying [1] (if DES isn't broken 1/2 ;-).  Any ideas?

>
>R.E. crack- is there a good reason not to simply build a file consisting of the
>crypted and uncrypted entries for an entire dictionary? this would be twice
>as large as just a word dictionary, but much faster than re-crypting...
>

	Yeah, as Rob Quinn (rjq@phys.ksu.edu) mentioned in his followup,
for each word you'd have to encrypt it 4096 different ways because of
the salt.  The final encryption of any word is a function of the salt
and that word...  So let's assume there are 100,000 entries in
/usr/dict/words - for each of those words, Crack generates a "perversion"
based on (for example) replacing 'o' with '0', that is, changing 'cool'
to 'c00l'.  For each word there are probably at least 20 different rules
that Crack applies to each word: so you would have to have 100,000 *
4096 * 20 different encrypted results - that's about 8 billion.  Now
assume 11 characters per encrypted password, and we need almost 100
gigabytes of storage required - that's a bit steep :-)  Notice, too,
that Crack has several different ways of deriving possible passwords
from each user's full name, telephone number, etc - and this kind of
thing you could never store ahead of time.

	Now I have *heard* (emphasize the unreliability of this story
here :-) of attacks just like you were talking about with an Exabyte
tape - I would assume the attackers simply left out Crack's 20 different
rules to "pervert" each dictionary entry, so they were only left with
needing 4 or 5 gigabytes of storage... :-)

	In short - I don't think it's very feasable.  Though maybe you
*could* do the first 1% of the dictionary words, then the second 1%,
then...   Would you gain anything by doing this?  I don't think you
would unless you have more than 4096 users listed in your /etc/passwd,
though if you had managed to get a list of a few hundred passwd files
somehow, maybe it'd be worth it ;-)

[Note to the reader: this used to be an email to Rob Quinn - he corrected
some errors I made, and as I believe some of you on the net might be able
to answer my question, I'm posting here...  I've edited it since sending
to him, but note that he said Crack has about 240 rules instead of the 20
I assumed - so multiply my figure of 100 gigs by about 12 and hold on to
your hats :-]

--------------------------------------------------------------------------------
David Wagner            dawagner@phoenix.princeton.edu (or wagner@nisc.jvnc.net)