An Introduction to Password Cracking
Passwords and "pass phrases" are used for everything ranging from logging into terminals to checking email accounts, from protecting Excel spreadsheets to securing the encryption keys for PKI-enabled enterprise networks. Their use in the enterprise is widespread, to say the least.
Password crackers are programs that aid in the discovery of protected passwords, usually through some method of automated guessing. Although some applications and poorly designed infrastructure equipment will encrypt or encode passwords, most modern day operating systems and devices create a hash of the password instead. I will go into the differences between hashing and encrypting in the next section, but for now simply note that they are two different methods of storing password information.
Although some poor encryption mechanisms can be easily reversed, modern day hashing methods are one-way that is, they can not be reversed and therefore decryption is not an option. Although the use of one-way algorithms can sound like a rock-solid solution, it simply makes the task at hand a little more time consuming. To circumvent the challenges created by hashing, password crackers simply employ the same algorithm used to encrypt the original password. The tools perform comparative analysis (a process explained later in this chapter), and simply try to match their guesses with the original encrypted phrase or password hash.
Many password crackers are nothing but guessing engines, programs that try word after word, often at high speeds. These programs rely on the theory that eventually you will encounter the right word or phrase. This theory is sound because humans are lazy creatures. They rarely take the trouble to create strong passwords. However, this shortcoming is not always the user's fault:
Users are rarely, if ever, educated as to what are wise choices for passwords. If a password is in the dictionary, it is extremely vulnerable to being cracked, and users are simply not coached as to "safe" choices for passwords. Of those users who are so educated, many think that simply because their password is not in /usr/dict/words, it is safe from detection. Many users also say that because they do not have private files online, they are not concerned with the security of their account, little realizing that by providing an entry point to the system they allow damage to be wrought on their entire system by a malicious cracker.
A Survey of, and Improvements to, Password Security. Daniel V. Klein, Software Engineering Institute, Carnegie-Mellon University, Pennsylvania. (PostScript creation date reported: February 22, 1991.)
It should be noted, however, that the raw "It's-not-in-the-dictionary" approach is now somewhat misleading as well. Password-cracking dictionaries now contain hundreds of thousands of popular names, characters, musical bands, slang, expletives, and an assortment of culturally popular terms that might or might not be in a classic dictionary. We'll explore the depth and versatility of password guessing later on, but the new rule of thumb is to avoid any kind of word all together. For example, "808state" is easily guessed by most password crackers, not only because it's based on a word (state) and a number (808), but also because it's the name of a popular band out of Manchester, England. Stronger passwords can be created by using a combination of letters, numbers, and extended characters. Acronyms work wonderfully, for example, "I'm trying to learn information security techniques quickly!" could be translated to "IT2LISTQ!". This is a MUCH harder password to guess, but is not all that difficult to remember.
The simple password problem is a persistent one despite the fact that it is easy to provide password-security education. It's puzzling how such a critical security issue (which can easily be addressed) is often overlooked. The issue goes to the very core of security:
Exploiting ill-chosen and poorly-protected passwords is one of the most common attacks on system security used by crackers. Almost every multiuser system uses passwords to protect against unauthorized logons, but comparatively few installations use them properly. The problem is universal in nature, not system-specific; and the solutions are simple, inexpensive, and applicable to any computer, regardless of operating system or hardware. They can be understood by anyone, and it doesn't take an administrator or a systems programmer to implement them.
"Understanding Password Security for Users On and Offline." K. Coady. New England Telecommuting Newsletter, 1991.
One additional password pitfall that is frequently overlooked is the password overload scenario. If users have a multitude of passwords to remember, there is a greater chance that they will write them down, use weaker passwords, or introduce an assortment of other insecure password practices into your environment. This is where centralized authentication systems, directory services, and single-sign on solutions can help you. Not only do they reduce operating costs and complexity, they ultimately help you with your overall security posture.
Password Cryptography 101
The etymological root of the word cryptography is instructive. The word crypto stems from the Greek word kryptos. Kryptos describes anything that is hidden, obscured, veiled, secret, or mysterious. The word graph is derived from graphia, which means writing. Thus, cryptography is the art of secret writing. Yaman Akdeniz, in his paper Cryptography and Encryption, gives an excellent and concise definition of cryptography:
Cryptography, defined as "the science and study of secret writing," concerns the ways in which communications and data can be encoded to prevent disclosure of their contents through eavesdropping or message interception, using codes, ciphers, and other methods, so that only certain people can see the real message.
"Cryptography and Encryption." Yaman Akdeniz. Cyber-Rights & Cyber-Liberties (UK), August 1996, at http://www.leeds.ac.uk/law/pgs/yaman/cryptog.htm. Criminal Justice Studies of the Law Faculty of University of Leeds, Leeds LS2 9JT.
To illustrate the process of cryptography, I'll reduce it to its most fundamental parts. Imagine that you created your own code in which each letter of the alphabet corresponds to a number (see Figure 14.1).
Figure 14.1. A primitive example of a code.
Figure 14.1 shows part of a table, or legend. Below each letter is a corresponding number. A = 7, B = 2, and so forth. This is a code of sorts. If you write a message using these rules, only you and the recipient will know what the message really says.
Unfortunately, such a code can be easily broken. For example, if each letter has a fixed numeric counterpart, you will only use 26 different numbers (perhaps 1 through 26, although you could choose arbitrary numbers). Lexical analysis would reveal your code within a few seconds. (Some software programs perform such analysis at high speed, searching for patterns common to your language.)
Another slightly more complex method is to make each letter become another letter, based on a standard incremental or decremental operation. One system that works this way is ROT-13 encoding. In ROT-13, a substitute letter is used. Moving 13 letters ahead (see Figure 14.2) in the chosen alphabet derives the substitute letter.
Figure 14.2. The ROT-13 system of letter substitution.
This, too, is an ineffective method of encoding or encrypting a message (although it worked in Roman times for Caesar, who used a shift-by-three formula). Some programs quickly identify this pattern. However, this doesn't mean that techniques such as ROT-13 are useless. I will illustrate why, and in the process, I can demonstrate the first important point about encryption:
Any form of encryption can be useful, given particular circumstances. These circumstances might depend upon time, the sensitivity of the information, and from whom you wish to hide data.
In other words, techniques such as ROT-13 can be quite useful under the right circumstances. Here's an example: Suppose a cracker wants to post a new cracking technique to Usenet. He's found a hole and wants to publicize it while it's still exploitable. To prevent security specialists from discovering that hole as quickly as the crackers, the cracker uses ROT-13 to encode his message.
There are a number of organizations that download Usenet traffic on a wholesale basis. In this way, they gather information about the cracker community. Some organizations even use popular search engines to ferret out cracker techniques. These search engines employ regex (regular expression) searches (that is, they search by word or phrase). For example, the searching party enters a combination of words such as
When this combination of words is entered correctly, a wealth of information emerges. However, if the cracker uses ROT-13, search engines will miss the post. For example, the message
Guvf zrffntr jnf rapbqrq va EBG-13 pbqvat. Obl, qvq vg ybbx fperjl hagvy
jr haeniryrq vg!
is beyond the reach of the average search engine. What it really looks like is this:
This message was encoded in ROT-13 coding. Boy, did it look screwy until
we unraveled it!
Most modern mail and newsreaders support ROT-13 encoding and decoding (Free Agent by Forte is one; Netscape Communicator's Mail package is another). Again, this is a rudimentary form of encoding something, but it demonstrates the concept. Now, let's get a bit more specific.
DES and Crypt
Today, Internet information servers run many different operating systems. However, for many years, UNIX was the only game in town. The greater number of password crackers were designed to crack UNIX passwords. Let's start with UNIX, then, and work our way forward.
In UNIX, all user login IDs and passwords are centrally stored in either one of two files: the passwd file, usually found in the /etc directory, or a file called shadow, also located in the /etc directory. These files contain various fields. Of those, we are concerned with two: the login ID and the hashed password.
Using "shadow passwords" is the preferred way of storing password hashes. The /etc/shadow file is only accessible by the root account and system services, as opposed to /etc/passwd, which is readable by everyone. If you have any systems that are still storing password hashes in /etc/passwd, either upgrade them to shadow passwords or remove them from your environment as soon as possible.
The login ID is stored in plain text, or humanly readable English. The password is stored in encrypted form. The encryption process is performed using Crypt(3), a program based on the data encryption standard (DES).
IBM developed the earliest version of DES; today, it is used on all UNIX platforms for password encryption. DES is endorsed jointly by the National Bureau of Standards and the National Security Agency. In fact, since 1977, DES has been the generally accepted method for safeguarding sensitive data. Figure 14.3 contains a brief timeline of DES development.
Figure 14.3. A brief timeline of the development of DES.
DES was developed to protect certain nonclassified information that might exist in federal offices, as set forth in Federal Information Processing Standards Publication 74, Guidelines for Implementing and Using the NBS Data Encryption Standard:
Because of the unavailability of general cryptographic technology outside the national security arena, and because security provisions, including encryption, were needed in unclassified applications involving Federal Government computer systems, NBS initiated a computer security program in 1973 which included the development of a standard for computer data encryption. Because Federal standards impact on the private sector, NBS solicited the interest and cooperation of industry and user communities in this work.
Information about the original mechanical development of DES is scarce. Reportedly, at the National Security Agency's request, IBM made certain documents classified. However, the source code for Crypt(3) (the current implementation of DES in UNIX) is widely available. This is significant because in all the years that source has been available for Crypt, no one has yet found a way to easily reverse-encode information encrypted with it.
There are several versions of Crypt, and they work slightly differently. In general, however, the process is as follows:
1. Your password is taken in plain text (or, in cryptographic jargon, clear text).
2. Your password is used as a key to encrypt a series of zeros (64 in all). The resulting encoded text is thereafter referred to as cipher text, the unreadable code that results after plain text is encrypted. This cipher text is sometimes referred to as a hash, as well, but the term only loosely fits in this case.
One-way hash functions are frequently used as an alternative to actually encrypting passwords. By using hashing algorithms such as MD5 or SHA-1, a digital footprint can be created of the password that doesn't contain the actual password itself. This varies from the process of encryption because the output does not contain the original input in any form, and it is therefore impossible to derive the original input from the output. Many modern UNIX systems are moving towards the use of MD5 hashes instead of relying on the crypt/DES process. If you are interested in one-way hashing techniques, or cryptography in general, Bruce Schneier's Applied Cryptography (John Wiley & Sons, ISBN 0-471-12845-7) is a must-have.
Certain versions of Crypt, notably Crypt(3), take additional steps. For example, after going through this process, the encrypted text is again encrypted, numerous times, using the password as a key. This is a fairly strong method of encryption; it is extremely difficult to break. It is estimated, for example, that the same password can be encoded in 4,096 different ways. The average user, without any knowledge of the system, could probably spend her entire life trying to crack DES and never be successful. To get that in proper perspective, here's an estimate from the National Institute of Standards and Technology:
The cryptographic algorithm [DES] transforms a 64-bit binary value into a unique 64-bit binary value based on a 56-bit variable. If the complete 64-bit input is used (i.e., none of the input bits should be predetermined from block to block) and if the 56-bit variable is randomly chosen, no technique other than trying all possible keys using known input and output for the DES will guarantee finding the chosen key. As there are more than 70,000,000,000,000,000 (seventy quadrillion) possible keys of 56 bits, the feasibility of deriving a particular key in this way is extremely unlikely in typical threat environments.
"Data Encryption Standard (DES)," Federal Information Processing Standards Pub lication 46-2, NIST, December 30, 1993. http://csrc.nist.gov/fips/fips46-2.txt.
One might think that DES is entirely infallible. It isn't. Although the information cannot be reverse-encoded, passwords encrypted via DES can be revealed through a comparative process. The process works as follows:
1. You obtain a dictionary file, which is really no more than a flat file (plain text) list of words (commonly referred to as wordlists).
2. These words are encrypted using DES.
3. Each encrypted word is compared to the target password. If a match occurs, there is a 98% chance that the password was cracked.
The process itself is both simple and brainless, yet quite effective. However, password-cracking programs made for this purpose are often times a little more clever. For example, such cracking programs often subject each word to a list of rules.
A rule could be anything, any manner in which a word might appear. Typical rules might include
Alternate uppercase and lowercase lettering.
Spell the word forward and then backward and then fuse the two results (for example, can becomes cannac).
Add the number 1 to the beginning or end of each word.
Naturally, the more rules you apply, the longer the cracking process takes. However, more rules also guarantee a higher likelihood of success for a number of reasons:
The UNIX file system is case sensitive (WORKSTATION is interpreted differently than Workstation or workstation is).
Alternating letters and numbers in passwords is a common practice.
Password crackers have had a tremendous impact on Internet security, chiefly because they are so effective:
Crypt uses the resistance of DES to known plain text attack and make [sic] it computationally unfeasible to determine the original password that produced a given encrypted password by exhaustive search. The only publicly known technique that can reveal certain passwords is password guessing: passing large wordlists through the crypt function to see whether any match the encrypted password entries in an /etc/passwd file. Our experience is that this type of attack is successful unless explicit steps are taken to thwart it. Generally we find 30 percent of the passwords on previously unsecured systems.
UNIX Password Security Ten Years Later. David Feldmeier and Philip R. Karn. Bellcore.
Password-cracking programs are improving in their effectiveness, too. The newer programs incorporate more extensive rules and diverse wordlists. Most wordlists are plain text files with one word per line. These files range in size from 1MB to more than 20MB. Many wordlists are available on the Internet; they come in a wide variety of languages (so an English-speaking American cracker can crack an Italian machine, and vice versa).
There are several popular wordlist collections. Some are simply dictionaries, and others contain hyphenated words, uppercase and lowercase, and so on. Perhaps the most definitive collection is available on the Packetstorm Web site. Its page is http://packetstorm.securify.com/Crackers/wordlists/.