- = Password Cracking = - Table of Contents 1. Cryptographic Background: Data Encryption Standard Algorithm 2. Unix Implementation of DES 3. Cracking Programs: How They Work 4. Philosophical Ramblings . . . - = Cryptographic Background - The DES Algorithm = - The Data Encryption Standard algorithm is complex and convoluted. To explain it thoroughly and in detail would take several pages, and since the algorithm isnÕt the real point of this paper, I will instead attempt a Òsemi-detailedÓ explanation. In any encryption system, one begins with ÕplaintextÕ, and ends with Ôciphertext.Õ In between occurs complex mathematical manipulation of the text as a computer perceives it - ones and zeros (also referred to as bits). Some systems are very advanced and difficult to crack, and yet lend themselves to concise and straightforward explanation. Not so with the DES. The DES algorithm relies on repeated and convoluted permutations (mixing up) of the bits which make up the plaintext. To create ciphertext and then decipher it, DES requires a key of 64 bits (64 ones and zeros). Every eighth one is used for error-checking, so actually, only 56 bits are used. On a small scale, DES encryption deals with 64 bits of plaintext at a time, encrypting them using the key. There are several different modes of operation for the algorithm on a larger scale, where the plaintext must be broken down in some manner, and then encrypted in groups of 64 bits. These different modes of operation neednÕt concern us here, since Unix password encryption deals only with plaintext 64 bits long or less. The encryption process divides the plaintext into two halves. Before beginning the repetitious core of encryption, the plaintext is given an initial mixup. Then the algorithm goes to work. Each round consists of the following steps. The current right half (R-current) becomes the left half of the next round (L-next), without undergoing any changes. The creation of the next round's right half (R-next) is more complicated . . . First of all, R-current (our current right-half) is subjected to all sorts of permutations involving a slightly different version of the key each time around, and fixed permutation matrices which are known as Ôthe S-boxes.Õ Heirein lies the heart of DES encryption. The S-boxes are the key to the security of DES, since they provide the only non-linear manipulation of the bits which are being encrypted. To those unfamiliar with cryptography and the number theory which underlies it, an encryption system which consists of strictly linear operations is broken quite quickly and easily. By linear operations I mean simple adding together or mixing of bits. For those truly interested in the inner workings of this encrypting function I have (in a piece of writing separate from this one) attempted to explain it in a manner more digestible than that presented by textbooks I have encountered. (Contact information is given at the end of this document.) But for the time being, let us leave behind this most messy section of the algorithm and create no more confusion by speaking of it. Moving right along . . . once R-current exits the Ôencrypting functionÕ discussed above, the resulting 32 bits are added together with L-current, and the answer becomes R-next. Now that, was _one_ round of encryption. Typically, 16 rounds are used to achieve the proper level of security. Having completed 16 (or more) rounds, the resulting bits go through one final mixing, exactly the opposite of the initial mixing, and there we have it, the final ciphertext. Decrypting the ciphertext follows almost exactly the same pattern as does encryption. Instead of starting with the plaintext, we start with the ciphertext. Also, the same key as was used in the encryption is needed to decrypt. Since anyone could decrypt the ciphertext given the original key, the security of DES depends on keeping the key a secret. - = Unix Implementation of DES = - The implementation of DES which is usually used by Unix systems to encrypt user passwords is slightly different from the typical implementation described above. First of all, rather than using some secret key known only to the system to encrypt a password, Unix reverses things. The password is used as the key, and the plaintext encrypted by this key is a bit-string of 64 zeros. So, why be different and do it this way? The answer is security. As was mentioned in the previous section, the security of DES depends on the key remaining a secret. If the systemÕs key were discovered by some random 12-year old hacker, the secrecy of all the passwords encrypted with that key would be compromised. Seen in that light, it makes sense to combine the two things you wish to keep secret into one, and use the password as the key. To a computer, each character within a password consists of 8 bits. The key is obtained from the first eight letters in a password. Only seven bits from each letter are used, and the eighth bit is discarded. So, with a little advanced math (7x8) we can see that we have the required 56 bits for a key. Because of the way the key is formed, having a password of more than eight letters gives no extra security - any letters after the eighth one are simply ignored by the encryption program. Using the password as the key and 64 zeros as the plaintext is not the only difference in the Unix implementation of DES. There is also something called the salt, which was devised to make it harder crack a password. The salt is obtained in the following way. First a 12-bit value is randomly chosen by sampling the system clock at the time when the password is chosen. The system then divides the value by 4096, and takes the remainder (i.e. takes the value mod 4096), which becomes the salt. Because of the way in which it is computed, the salt can be one of 4096 possible values (to see why this is so, think of all the possible remainders you can get when dividing by a certain number). This value is used to select one of 4096 possible permutations of the DES algorithm. Recall that in the description of the algorithm, I made several references to different ÔpermutationsÕ which are used. These permutations are defined by tables of numbers. What the Unix people did to make cracking passwords more time consuming was to create 4096 different tables, essentially creating that many variations of the encryption algorithm. (Luckily for those wishing to crack passwords, these tables can be found through public channels, and incorporated into cracking programs.) For a final measure of extra security, 32 rounds of encryption are used, rather than the usual 16. Having done all this work, the password-encrypted constants are stored for later reference in a password file. Each userÕs info is stored in one line of a password file. For example: jsmith:fF9b.H6Gs/jPg:0:10:John Smith:/:/home/users/jsmith The first field contains the userÕs login name, in this case ÒjsmithÓ. The second field contains password information: the first two characters ÒfFÓ are a character representation of the 12 bit salt value. The rest of the characters Ò9b.H6Gs/jPgÓ are a representation of the 64 bit constant which was encrypted using the password-key. Binary values are translated into character form by treating each 6-bit segment as the ascii binary representation of a character. The rest of the information stored for each user include access permissions, the userÕs full name, and their home directory. - = Cracking Programs - How They Work = - Cracking programs essentially mimic the steps taken by login verification programs. A login sequence is as follows. When a user enters a password at the prompt, the first step is to look up the salt value. So the program searches through the password file until it finds the userÕs login name, and converts the two characters representing the salt back into a 12-bit binary value. Then the appropriate tables are used to encrypt the zero-constant, using the just entered password as the key. If the result matches what was stored in the password file, the user is granted access. Based on the above description, itÕs obvious that for a cracking program to run, it must have a password file to work from. So, how does one get ahold of a password file? TheyÕre not difficult to find (usually at /etc/passwd) nor to read, since they are publicly accessible. The only catch is that most password files nowadays are shadowed. This means that the password information is replaced by a Ò*Ó or ÒxÓ or Ò!Ó (depending on the particular system the password file is on) and stored elsewhere, in a location known and accessible only to the system administrators. A line out of a shadowed password file would look something like this: jsmith:*:0:10:John Smith:/:/home/users/jsmith Useless to anyone wishing to run a cracking program. Suddenly even locating password information, let alone cracking it, has become much more difficult. What do you do now? You get lucky, or you get smart. How exactly one goes about getting ÒsmartÓ and finding unshadowed password files is most definitely not my area of expertise. Anyone who wishes to see some information on the subject, try convincing logik to write a text on it. But before we move on... it seems that an important detail has almost been passed over. There seems to be a catch-22 situation here - to obtain a password file in the manner described above, one must already have an account on the system. Hmm... well, if one has an account already, whatÕs the point of obtaining more? Oh, IÕm sure one could come up with many reasons and ulterior motives, but the point is, what about the cracker who doesnÕt have an account yet? ... welcome to the world of hacking. Possibilities are vast, devious, and probably endless. But in the interest of keeping this article to a somewhat manageable length, letÕs move on, assuming that our cracker has somehow managed to obtain a password file. Additional requirements for running a cracking program include a word list (or dictionary) and a machine with a minimum 32MB of RAM and at least a 66MHz processor. The amount of time required demands true dedication, since the cracking process may take days or weeks of running nothing but the cracking program, depending on the size of the password file and dictionary being used. As was mentioned initially, password cracking programs mimick the login-verification algorithm used by unix systems, except that they do it on a much larger scale. This type of cracking is referred to as brute-force cracking. The concept is simple, the process, repetitive. For each encrypted password in the password file (which you have somehow procured for the cracking program), the program first identifies the salt value. As was explained earlier, this consists of the first two characters in the encrypted field. The cracking program then goes through the entire dictionary (which you have also provided it) and encrypts each word using the salt it just decoded. Encryption is performed just as the unix system does it. Each result is compared with the entry in the password file (donÕt forget, this is still just _one_ password file entry that the cracking program is working on here). If a match is found, it is saved in a file, and the cracking program moves on the next password file entry. If no match is found, the cracking program continues to encrypt words from the dictionary until it runs out, then moves on to the next password file entry and repeats the process. It is here that the benefit of ÒsaltingÓ encrypted passwords becomes apparent. The 12-bit salt value increases the search space by a factor of 4096. Every single word on the word list has 4096 possible ways of appearing in encrypted form. This not only lengthens the search process considerably, but makes it impractical to crack passwords by means of a look up table. A look-up table would consist of a word list where each word is already pre-encrypted. ItÕs an extremely fast method, and would even lend itself to various search algorithms, but due to password salting, the storage requirements for such an endeavor are prohibitive, not to mention an enormous amount of precomputation time. So essentially, itÕs because of password salting that cracking programs must encrypt the entire word list for each password file entry. This does not make the cracking process impossible, but it does slow things down some, and makes the task somewhat more daunting and demanding in terms of computing time and power. This may seem like a trivial gain, but in reality, thatÕs what security is all about - finding the point at which something becomes difficult enough to accomplish as to make it not worth doing. Absolute security is often not needed nor is it worth it, when the same end effect can be obtained with lesser measures. ... but enough digression ... In addition to the basic algorithm described above, there exist cracking programs which give the user several additional options, often called Òrules,Ó in how they choose to encrypt a given word list. Here are a few examples of the options a cracker can incorporate into cracking programs (depending on the specific program of course, not all of them support these options, and there are varying levels of flexibility in defining these options) ... - words spelled backwards - certain letters replaced by symbols, for example, change all occurrences of lowercase ÒLÓ 's to Ò1Ó 's or Ò!Ó 's or change all ÒSÓ 's to dollar signs. - alternate upper- and lowercase lettering - adding the number 1 to the beginning and/or end of each word If the targeted password is that of someone the cracker knows, or if a few pertinent personal facts are known, the additional knowledge may also be incorporated in the choosing of rules, or even in the choosing of a particular word list. Since the rules are user-defined, there is room for as much creativity as the cracker can come up with. When a cracking program with the option for cracker-defined ÒrulesÓ is used, a passwordÕs security depends not only on whether or not it is found in some particular word list or dictionary, but more on the userÕs cleverness in choosing a password. Unfortunately for system administrators, the above examples of ÒrulesÓ that a cracker might try also tend to be the rules used by people to transform some word or phrase into what they think will make a good password. In this arena, it comes down to a battle of wits, and a personÕs ability to formulate truly random (seeming) passwords. The amount of time which the cracking process takes up varies according to the processing power of the machine(s) used. It was already mentioned that basic machine requirements consist of a 66MHz processor and 32 megs of RAM. These requirements are fairly minimal, but are offset by the large computing time requirements. As an example of the type of time-dedication the process requires, an experimental run was conducted on a 266MHz machine with 64 megs of RAM (i.e. a Macintosh G3). Using a 25 meg word list, it took approximately 11 minutes for the cracking program to test all the possibilities for _one_ entry in the password file. For ten hours the cracking program was the only thing running on the computer. In those ten hours 60 passwords were tested, and only two were actually cracked. Another test run was attempted on a Macintosh Power PC, an 82 MHz machine with 32 megs of RAM. Note the word Òattempted.Ó The program would only run for a relatively short period of time (1/2 and hour or so) before completely bringing down the machine it was running on. Typically, the success rates of cracking programs depend on how wisely users chose their passwords, but on the average fall somewhere around 30% on systems where passwords are not tested by administrators for security. - = Philosophical Ramblings . . . = - The weaknesses in Unix password security are not in the encryption method. The password cracking programs employ the brute-force method of guessing at a password, encrypting it, and then comparing the results. A brute force method of cracking can be applied to any type of encryption, and the success of such an attack has no relation to the actual algorithm which is used to encrypt the data. Instead it depends on the size of the search space for the encryption key. So the potential weakness of DES encryption lies not in the algorithm, but in the relatively small search-space for the 56-bit key (which in the Unix implementation is the password). This ÔsmallÕ search space consists of 2^56 or more than 70 quadrillion possible values. It would be possible to build a machine whose sole purpose is to perform an exhaustive search of all possible keys, and crack the encryption method that way. Given the technology available these days, this approach is becoming more and more feasible, posing a threat not only to the multitudes of unix systems out there, but also banks and other agencies which employ DES encryption for pin-numbers and the like. So, although the actual method of encryption is not a weakness in and of itself as of yet, there is definitely the potential for it to become one. Currently, the true weakness of password security lies at the human level. Most people choose Òeasy to rememberÓ passwords, which usually translates to Òeasy to crackÓ when it comes to password cracking. Oftentimes users are told to use a password which is a combination of upper-case and lower-case characters, as well as digits and other symbols. Nevertheless, there is no sure algorithm which one can follow to ensure that a password is uncrackable. On the contrary, structure, or a set algorithm, is something to be avoided when trying to devise some ÒfoolproofÓ method of choosing uncrackable passwords. For if users have access to some algorithm or trick to coming up with a good password, one can be sure that crackers have access to it as well, which just brings us right back to square one. There are several things Unix system administrators can do to greatly reduce the success rates of cracking programs. One fairly effective precautionary measure is to run a password cracking program with a typical word list on each new password as it is chosen, and to accept the new password only if the program fails to crack it. Another preventive measure is to require users to choose a new password every several months. This way a cracker would be limited to a certain time period in which they must obtain the password file, successfully crack a password, and then proceed to make the cracked account their own. Neither of these measures guarantee complete password security, merely heighten the security level somewhat. I hope that this article has been informative and enlightening ;) Have fun both in keeping the weasels out and weaseling your way in. -Kitten kitten@msec.net ************ ___________________________ ************************************* ********** / / / /\ * * **** ______/ ____/ ____/ / / * Macintosh Security * *** / / / / ____/ / ** research and development * ** / /____ / ____/ / / *** * * / / / / / / / / **** http://www.msec.net * /_/_/_/________/________/________/ / ***** hotline: msec.net * \_____\________\________\________\/ ****** * * ******* * ******************************************************************************