Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!usc!snorkelwacker!bloom-beacon!athena.mit.edu!jik From: jik@athena.mit.edu (Jonathan I. Kamens) Newsgroups: comp.unix.questions Subject: Re: passwds and crypt(3)... Message-ID: <1990Jan4.202253.27867@athena.mit.edu> Date: 4 Jan 90 20:22:53 GMT References: <21966@adm.BRL.MIL> Sender: news@athena.mit.edu (News system) Reply-To: jik@athena.mit.edu (Jonathan I. Kamens) Organization: Massachusetts Institute of Technology Lines: 80 In article <21966@adm.BRL.MIL>, mchinni@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@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710