Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!ncar!elroy.jpl.nasa.gov!sdd.hp.com!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!gvlf3.gvl.unisys.com!lgnp1!phil
From: phil@ls.com (Phil Eschallier)
Newsgroups: comp.unix.admin
Subject: Re: Uninvertible passwd encryption (was: Re: Kmem security)
Message-ID: <5061@lgnp1.ls.com>
Date: 20 Mar 91 13:20:56 GMT
References: <1991Mar19.231715.28594@comp.vuw.ac.nz>
Organization: Lagniappe Systems [Doylestown, PA]
Lines: 63

In article <1991Mar19.231715.28594@comp.vuw.ac.nz> duncan@comp.vuw.ac.nz (Duncan McEwan) writes:
>This has drifted off the topic a little bit, so I've changed the Subject
>(again!) and killed the References:
>
>In article <1991Mar18.153201.23325@lth.se>
>	magnus@thep.lu.se (Magnus Olsson) writes:
>
>>login does *not* have to decrypt the password from /etc/passwd - indeed,
>>I don't think there's any way it could do that! (The encryption function
>>is not invertible - several different passwords acan have the same
>>encrypted from).
>
>This response to an earlier posting reminded me of something I have been
>curious about.  Exactly why is the Unix password encryption algorithm
>uninvertible?  It seems to me that the fact that several passwords can
>have the same encrypted form is irrelevent -- the cracker simply has to
>find any *one* password results in a given encrypted string and they are
>in.
>
>Is it to do with the fact that Unix encrypts a constant string using the
>password as a key -- so it *is* possible to work back to that constant string,
>but you still know nothing about the password?
>
>Apologies to any cryptologists out there, to whom this must be obvious!
>

	please forgive me if some of my details are off, it has been
	some time since i worked on unix passwds/encryption ...

	i would never say never and never say always but for all intents
	and purposes the unix passwd encryption cannot be reversed ...

	the 13 byte uncrypted passwd in the /etc/passwd has the following
	format:
		positions 1 and 2 are the salt
		positions 3 thru 13 are the encrypted passwd
	but this is not all ... the des crypt makes 16 itterations of
	encryption and within each itteration the routine shifts bits
	and re-arranges the string according to a predefined schedule.
	the result of this logic is a 66 byte output string of which only
	11 bytes are stored in the /etc/passwd file.

	/bin/passwd does not decrypt what is in the /etc/passwd file,
	rather it encrypts the user input by using the salt from the
	first 2 bytes of the current encrypted passwd then compares
	the following 11 bytes in the current encrypted passwd w/ the
	result of its own encryption.

	since only 11 bytes of the des crypt result is significant, i
	suppose it is possible to have two (or more) encrypted passwds
	equal.  however when choosing a new passwd word, the salt is
	randomly generated from the time -- this only makes it less
	likely that duplicates would show up.

	again, it may be possible to have two (or more) encrypted passwds
	equal but i will leave the proof up to someone out there with
	nothing better to do but bang there head again the wall.

-- 
Phil Eschallier     |  E-Mail to:                    US Mail to:
                    |   INET: phil@ls.com             248B Union Street
Lagniappe Systems   |   UUCP: ...!uunet!lgnp1!phil    Doylestown, PA  18901
Computer Services   |    CIS: 71076,1576              VOICE: +1 215 348 9721