Uninvertible passwd encryption (was: Re: Kmem security)

[Jonathan I. Kamens]

In article <1991Mar19.231715.28594 at comp.vuw.ac.nz>, duncan at comp.vuw.ac.nz (Duncan McEwan) writes:
|> 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.

  I think you are failing to see the difference between cracking passwords and
inverting crypt(3).  "The Cuckoo's Egg", by Cliff Stoll, makes the difference
clear, but you have to read an awful lot of other stuff in order to read the
little bit about crypt (It's good reading, but that's besides the point :-). 
I'll try to explain the difference here.

  Call the encryption algorithm C, such that the domain of C is the acceptable
Unix passwords, and the range of C is the thirteen-character values that can
appear in /etc/passwd.  We feed input keys, signified by K, into C, and we get
back encrypted strings signified by E.  That is, E = C(K).

  When people say that C is uninvertible, they mean that there is no known way
to efficiently go from any given E to a K such that E = C(K).  In other words,
there is no known function I, such that I(C(K)) = K.

  Yes, the fact that several passwords can have the same encrypted form is
mostly irrelevant, since the function I, if it existed, would only have to be
able to find *one* such form.  The point, however, is that it doesn't exist
(or, at least, is not known to exist).

  Since no known efficient I exists, the only known way to crack Unix
passwords is to encrypt a whole bunch of plaintext passwords and compare them
to the encrypted entry in /etc/passwd.  The fact that it is possible to do
this does not imply that crypt is invertible.  When we talk about
invertibility, we are talking about algorithms.  When we talk about password
cracking, we're talking about any which way you can, algorithmic, brute force
or otherwise.

  The idea of the Unix password algorithm is that *if* a sufficiently complex
password is selected, a brute force attack on that password is unlikely to
succeed because it will take too much time to complete.  Of course, as
machines become more and more powerful and it becomes possible to do things
like encrypt millions of strings with all 4096 possible seeds and store them
on-line somehow, or to encrypt strings so quickly so that the encryption speed
is no longer nearly as much of an obstacle as it used to be, Unix passwords
become more vulnerable.  Which is why more emphasis has been placed recently
on things like choosing better passwords, keeping the /etc/passwd file secure,
and/or putting encrypted passwords in a shadow password file that mortals
can't read.

  In summary, I'd like to quote from "On the Security of UNIX," by Dennis M.
Ritchie (which, incidentally, contains the "mkdir x; cd x" shell script that
someone was reluctant to post, I believe in this newsgroup, a few days ago):

	     On the issue of password  security,  UNIX  is  probably
	better  than  most  systems.   Passwords  are  stored  in an
	encrypted form which, in the absence  of  serious  attention
	from  specialists  in  the field, appears reasonably secure,
	provided its limitations are  understood.   In  the  current
	version,  it is based on a slightly defective version of the
	Federal DES; it  is  purposely  defective  so  that  easily-
	available  hardware  is  useless  for attempts at exhaustive
	key-search.  Since both the  encryption  algorithm  and  the
	encrypted passwords are available, exhaustive enumeration of
	potential passwords is still feasible up  to  a  point.   We
	have  observed  that users choose passwords that are easy to
	guess: they are short, or from a limited alphabet, or  in  a
	dictionary.   Passwords  should  be  at least six characters
	long and randomly chosen from  an  alphabet  which  includes
	digits and special characters.
	
	     Of course there also exist  feasible  non-cryptanalytic
	ways of finding out passwords.  For example: write a program
	which types out ``login:''  on  the  typewriter  and  copies
	whatever  is  typed  to a file of your own.  Then invoke the
	command and go away until the victim arrives.

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