passwds and crypt(3)...

[Jonathan I. Kamens]

In article <21966 at adm.BRL.MIL>, mchinni at pica.army.mil (Michael J. Chinni,
SMCAR-CCS-E) writes:
> The encryption of a trial password with all possible seeds may be required to
> guarentee a match, I don't think it is neccessary for a match. The way I
> understand the password encryption is that multiple different clear-text
> passwords will NEVER encrypt to the same encrypted password.

  First of all, I think you're missing an "although" as the first word
in the first sentence above, because otherwise it doesn't really make
any sense.

  Second, I have never heard it said that multiple different clear-text
passwords will never encrypted to the same encrypted password; what I
have heard is that the odds of that happening are so miniscule that it
is considered an impossibility from the viewpoint of practicality. 
That's different (although it isn't all that different :-), from saying
that it'll never happen.

> Given you encrypt a trial password, and then check it against the /etc/passwd
> file. Doing this you are not assured of finding all accounts whose
password is
> the same as your trial one, but you may find a match (which would mean you
> matched clear-text and seed).

  There are (theoretically) 4096 different possible seeds for each
password in the /etc/passwd file.  Therefore, any time you pick an
arbitrary seed and encrypt a password in it, even if you have correctly
picked the password of someone in the /etc/passwd file, the odds are
(once again, theoretically only) one in 4096 that you have picked the
right seed in which to encrypt that password.

  Given those odds, a method of attack which picks arbitrary seeds in
which to encrypt the /etc/passwd and then compares encrypted words
against the strings in the /etc/passwd file without taking into account
individual seeds is, as I have already pointed out, stupid.

  HOWEVER (and this is a big however, hence the upper case), if you do
have a very fast machine with a very large disk, then it becomes
feasible to encrypt all word guesses in all seeds, and store the results
in a dbm (or similar technology) database file using the encrypted key
as the dbm key. Assuming 1000 encryptions per second (which is
achievable by some machines with some crypt algorithms, a 10000 word
dictionary (which is actually relatively small; the dictionary we use to
check passwords here has 120000 words in it), and an /etc/passwd file
with all 4096 seeds represented in it, then the time to build the
database (not taking into account disk I/O, which will slow it down
considerably in most cases) is:

  10000 words * 4096 seeds / 1000 encryptions per second  
    = 40960 seconds 
    = less than 12 hours

The amount of space necessary would be (I include the size of the word
in the storage size for each seed because if you use the encrypted
string as the key and then store the word as the value for that key
you'll need to store the word for each key generated):

  10000 words * 4096 seeds * 
  (4 characters per word average length + 13 characters per seed)
    = about 700 meg

Now, even with very bad disks, you can generate the file in less then a
week on a drive like an DEC RA90 (which has over a gig of space on it). 
Once the file is generated, you read in the /etc/passwd file and look up
each encrypted key in the dbm database; if you find a hit, you've
immediately located the user's password.

  You're a lot better off doing things that way than picking random
arbitrary strings and crossing your fingers and hoping for a match --
whatever your odds are of getting a match, they are divided by 4096 if
you don't cover all the possible keys.

  All this goes to show you that (a) you should pick good passwords, and
(b) you should use kerberos :-).

Jonathan Kamens			              USnail:
MIT Project Athena				11 Ashford Terrace
jik at Athena.MIT.EDU				Allston, MA  02134
Office: 617-253-8495			      Home: 617-782-0710