duncan@comp.vuw.ac.nz (Duncan McEwan) (03/20/91)
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! Duncan.
c60b-1eq@e260-1c.berkeley.edu (Noam Mendelson) (03/20/91)
In article <1991Mar19.231715.28594@comp.vuw.ac.nz> duncan@comp.vuw.ac.nz (Duncan McEwan) writes: >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? Yes, UNIX encrypts a constant string repeatedly using the password as the key. Another key, known as the salt, is included so as to skew the encryption process, making it harder to crack. The salt is a two-character key which can contain the characters a-z, A-Z, and 0-9, and it is chosen randomly by UNIX. If you look at an /etc/passwd entry, the first two characters of the password field make up the salt, and the remaining characters make up the password. I don't see the logic in trying to "work back" to the constant string. If one were to crack passwords they would attempt to encrypt strings and compare the result to the /etc/passwd entry (since they know the salt). =============================================================== Noam Mendelson | "I haven't lost my mind, c60b-1eq@web.Berkeley.EDU | it's backed up on tape University of California at Berkeley | somewhere."
jik@athena.mit.edu (Jonathan I. Kamens) (03/20/91)
In article <1991Mar19.231715.28594@comp.vuw.ac.nz>, duncan@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@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8085 Home: 617-782-0710
phil@ls.com (Phil Eschallier) (03/20/91)
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
2004ktz@ucsbuxa.ucsb.edu (David G. Koontz) (03/21/91)
In article <1991Mar20.125811.27150@athena.mit.edu> jik@athena.mit.edu (Jonathan I. Kamens) writes: >In article <1991Mar19.231715.28594@comp.vuw.ac.nz>, duncan@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. > 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). If anyone has a sample of two passwords encrypting to the same result in the same salt, please publish them. The data value to DES starts as ZEROs, while 56 bits ( 7 bit ascii times 8 bytes max) of key are generated from the plaintext password. The DES algorithm is repeated 25 times. At the 25th iteration the chances of finding two key values that map the data values following the 24th iteration into the same result values must be quite remote. Its guaranteed not to happen in the 1st iteration, because the data values are the same.
miquels@maestro.htsa.aha.nl (Miquel van Smoorenburg) (03/21/91)
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! -> ->Duncan. I don't know exactly if this is true, but: The input to crypt() is ofcourse the salt, and a password of max. 8 bytes. However, the MSB of every byte is stripped off! So even if you could reverse crypt(), and the result has a byte > 127 in it, the result would be useless. So you have to keep track of a lot of bits if you want to reverse crypt(), right? +===============================+============================================+ | | | | Miquel van Smoorenburg, | It's nice to be important, | | miquels@maestro.htsa.aha.nl | but it's more important to be nice. | | | | +===============================+============================================+ -- +===============================+============================================+ | | | | Miquel van Smoorenburg, | It's nice to be important, | | miquels@maestro.htsa.aha.nl | but it's more important to be nice. | | | | +===============================+============================================+
sef@kithrup.COM (Sean Eric Fagan) (03/22/91)
In article <1991Mar19.231715.28594@comp.vuw.ac.nz> duncan@comp.vuw.ac.nz (Duncan McEwan) writes: >Exactly why is the Unix password encryption algorithm >uninvertible? You should take this to sci.crypt, as people there would love to bore you to death with details about it. But here is my (albeit limited) understanding of it: the algorithm is uninvertible (vertible?) because you cannot get to the previous value in any step. That is, the password starts out, and gets munged 8 (I think; could be some other number) times, with the output of each time being used as the input of the next iteration. Now, the function used to "munge" it does not have a one-to-one mapping. That is, for each output, there are many possible inputs (or the other way around, possibly). Let's say that, for each possible output, there are 8 possible inputs. As a result, you have to worry about 8**8 (16777216) possible intermediate steps if you reverse it, the final one of which is a password. Anyway, if I'm wrong, I apologise. I was half-asleep during the talk I went to about this... 8-( -- Sean Eric Fagan | "I made the universe, but please don't blame me for it; sef@kithrup.COM | I had a bellyache at the time." -----------------+ -- The Turtle (Stephen King, _It_) Any opinions expressed are my own, and generally unpopular with others.
jim@cs.strath.ac.uk (Jim Reid) (03/23/91)
In article <1991Mar19.231715.28594@comp.vuw.ac.nz> duncan@comp.vuw.ac.nz (Duncan McEwan) writes:
Exactly why is the Unix password encryption algorithm uninvertible?
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?
Not exactly. UNIX password encryption is quite complicated. It uses
DES which is supposedly strong enough to survive most cryptanalytical
attacks. (Unless of course you work for the NSA or GCHQ....) It is
theoretically possible to break DES (like any encryption algorithm),
but computationally infeasible. For example, public-key encryption
tends to be based on the fact that factorising huge integers - say a
few hundred digits - takes a long time; possibly longer than the
lifetime of the universe even if using a supercompter. In other words
it can be done, but the amount of effort required means it's not worth
the bother of trying.
DES uses a 56-bit key which fits neatly into 8 ASCII characters, the
usual maximum length of a UNIX password. This gives a key space of
7.2E16 (2**56). Assuming you could perform 1 billion DES encryptions
per second, an exhaustive search of the key space would take over two
years. In reality, a rate of even 1 million encryptions per second is
somewhat optmistic. [Even if the original assumption were true, the
password would have to remain unchanged while it was being cracked.]
Of course, this approach is crude. However, DES is designed to
withstand cryptanalytical attacks on the key space even when the
plaintext and cyphertext is known. There is a lot of speculation that
DES may have a trap-door which makes it easily cracked by the likes of
the NSA. However, it hasn't been found yet, despite serious attempts
by experts.
"What about DES hardware?", I hear you ask. Well for UNIX purposes,
DES chips are not much help. The UNIX crypt() function which
implements DES permutes an internal DES table (the E-table) using an
effectively random number - the salt - based on the PID and time. This
salt is stored in the encrypted password field and is used to
initialise the DES algorithm before encrypting the plaintext with the
password as a key. The salt means there are 4096 permutations of the
DES E-table, making DES chips useless since they only have one
hard-wired E-table. It's possible someone could go out and build
custom DES hardware, but that won't exactly be cheap or quick.
All this is explained in the classic paper "Password Security: A Case
History" by Robert Morris and Ken Thompson. It's been shipped with
UNIX systems since the time of V7, but not many vendors include it
with their documentation these days.
Jimduplain@rtf.bt.co.uk (Andy Duplain) (03/23/91)
In article <1991Mar20.061813.17416@agate.berkeley.edu> c60b-1eq@e260-1c.berkeley.edu (Noam Mendelson) writes: >If one were to crack passwords they would attempt to encrypt strings >and compare the result to the /etc/passwd entry (since they know the salt). Absolutely, One way of doing this could be using the SunOS l64a() library function, which can generate base-64 strings from long ints. But since l64a() can generate a maximum of 6 characters, and since crypt() takes a long time to run, it would take several months, and you wouldn't get any passwords longer than 6 chars. No go! -- === Andy Duplain ============================================================== British Telecommunications PLC, Customer Systems, Brighton, United Kingdom. #define DISCLAIMER My views and options are not necessarily those of my company Internet: duplain@rtf.bt.co.uk UUCP: ...!uunet!ukc!axion!bscsq1!duplain
martin@mwtech.UUCP (Martin Weitzel) (04/11/91)
In article <1991Mar20.061813.17416@agate.berkeley.edu> c60b-1eq@e260-1c.berkeley.edu (Noam Mendelson) writes: .... >The salt [of an UNIX password] is a two-character >key which can contain the characters a-z, A-Z, and 0-9, and it is chosen >randomly by UNIX. I know that it is nit picking - but to be exact: The salt can have 4096 different values. To encode these with two characters, you must have 64 distinct values for each character, where the mentioned ones only sum up to 62. (The two missing ones are "/" and ".", which can also appear in the salt.) -- Martin Weitzel, email: martin@mwtech.UUCP, voice: 49-(0)6151-6 56 83