GeodSoft How-To: Cracking Passwords Techniques

Password crackers are primarily after root or administrative account passwords when they crack passwords. Their tools are password cracking programs that use password dictionaries or brute force. The feature lists of common password cracking programs or tools are discussed. Also listed are the suggested standard dictionary transformations for Crack, the best known tool for cracking passwords. How long it takes to crack passwords and the primary factors affecting password cracking times are covered. Why password dictionary attacks dramatically lower brute force password cracking times is discussed.

Goals of the Cracker

The goal of the cracker is to obtain the root account password on UNIX systems and administrator accounts on Windows NT and 2000 systems. With some UNIX security setups, the passwords for users in the wheel, security, or root group may have significant value. Since the cracker presumably already has some degree of access to the target machine (cracking can only be performed when the attacker already possess the password hashes), it's not likely that unprivileged accounts will be of much value to the intruder, but the techniques for obtaining passwords are the same regardless of the target account.

The intruder is likely to need only one password for an account with suitable privileges. Additional accounts may be of some value in preserving access, but not likely to make much practical difference in obtaining access to the system at the desired privilege level. UNIX and Windows systems are normally quite different in this regard; UNIX systems normally only have one root account with full system privileges where Windows systems, especially servers, may have multiple administrator level accounts, each of which has full system access.

The cracking times table shows that with the computing power currently available and for the next several years, eight character passwords (the traditional length limit on UNIX systems) can be chosen that will not be cracked by brute force techniques but still most passwords are poorly chosen and fit some predictable characteristics, i.e., based on a word, often with character transformations. Most contemporary UNIX systems allow passwords longer than eight characters.

Since brute force is not likely to identify any but the weakest passwords, the intruder's best chance is to identify techniques that are computationally efficient compared to brute force techniques, and have a reasonable chance of cracking some of the passwords in the collection of accounts and password hashes in their possession. By applying what is known about how users select passwords, an intruder can tremendously increase the odds in their favor of finding passwords. With the right techniques, some poor passwords can be cracked in under a second.

Cracking Tool's Feature List

The fundamental flaw in the password system is the tendency of most people to select passwords that are easy to remember. This means they choose names and words that can be found in dictionaries as their passwords. Often such names or words are modified by applying predictable changes to them. This may be in response to system requirements to vary the kinds of characters included in a password.

The alternative to brute force is a dictionary attack. At its simplest this means treating each word in a dictionary (electronic word list) as a password and encrypting it, and then comparing the resulting hashes to the hashes in the password file being cracked. If the hashes match, the password is known. It's imperative to understand that this is only the most rudimentary form of dictionary attack, and that the real power of dictionary attacks come from understanding the ways in which most people vary names and dictionary words when attempting to create a password. By applying all the common transformations to every word in the electronic list and encrypting each result the number of tested passwords multiplies rapidly. Every "clever" way of manipulating words to hide their origin is known to the cracking tools.

To understand what make weak and strong passwords, it's necessary to understand what cracking tools can and can't do. L0phtCrack is the leading Windows cracking tool. The easy to use L0phtCrack with its GUI interface is rather limited compared to Crack 5 and John the Ripper in its dictionary transformation capabilities. L0phtCrack can append a user specified number of characters to the end of the dictionary words. It works through the entire character set and appends every combination to each dictionary word; this includes all the letter sequences as well as digits and symbols. L0phtCrack takes less than a second to process the default dictionary of nearly 30,000 words and about a minute and a half to process two additional characters in conjunction with the 30,000 word list (on a PIII 500).

Both Crack 5 and John the Ripper allow the user to define rule sets that control the transformations that are applied to the input dictionaries (word lists). Below are most of the transformations that John the Ripper can perform. Crack has the same capabilities.

In the forgoing a class might be any of the following: a letter, a vowel, a consonant, an upper case letter, a lower case letter, a digit, a symbol or punctuation, a non letter (digits, symbols and punctuation), alphanumeric or one of several others. The length limits and reject options don't increase the possibilities, but allow the cracker to skip "words" where a particular type of transformation may not make much sense; this should improve the cracking tool efficiency. For example, the dictionary may already contain normal words with one or more digits already appended to the word. By not appending additional digits to such "words", the cracking tool may save some time by not creating less likely passwords where three or four digits are appended to a normal word.

Cracking Tool Examples

The words that the transformations operate on can be either from a standard dictionary (word list, one per line) or from the user name and words (or names) extracted from the /etc/passwd GECOS field. Crack appears to be limited to words from dictionaries. Rules can be combined to perform multiple transformations on the words. Below is the list of actual transformations suggested in the Crack 5 documentation:

A number of the preceding transformations had length limitations which have been omitted for simplicity.

How Long Does It Take to Crack Passwords?

Conceptually the easiest way to crack passwords is to generate character sequences working through all possible 1 character passwords, then two character, then three character, etc. This is the brute force attack previously mentioned. It could start at any specific length password. Theoretically any possible password can be found this way, but generally there is not sufficient computing power available to successfully accomplish this. A number of factors determine how long a brute force attack will take. Some may be under a system administrators control and others are not.

One factor is the amount of computing power available to solve the problem. Computing power increases continually; Moore's law anticipated a doubling of processing power every 18 months and this has so far been a close approximation to reality. This works out to about a 100 times increase each decade. Today a computer is likely to have approximately a million times the computing power available when the first UNIX was developed.

Password cracking lends itself well to parallel processing on multiple machines with near linear gains as more machines are applied to the problem. Someone with access to many machines during off-hours at a company or educational institution may be able to apply lots of computing power. Computers with a wide range of speeds may be available. Thus the amount of computing power available for password cracking continually rises but the amount available to a single cracker or group of crackers may vary by orders of magnitude at any specific point in time.

Another factor is the algorithm used to encrypt the password. Generally this is set by the operating system but some such as Linux and OpenBSD allow the administrator to select from different types. On OpenBSD the administrator can control loop counts for some of the options. Changing the encryption method and how many times it is applied, can greatly increase the time it takes to compute a password hash. Generally, the longer it takes to compute the hash when the password is created, the longer it will take when trying to crack the password. The standard UNIX encryption method has been changed to make it slower more than once. On the other hand, some algorithms have multiple implementations and those cracking passwords have created variants that produce the same results but run as much as 100 times faster than the version that originally encrypts the password².

When cracking passwords from UNIX systems, the cracking tool must be configured to use the appropriate encryption algorithm for the system being cracked. For systems that allow the administrator a choice of encryption methods or various loop counts, the cracking tool must be configured to correctly match these. Theoretically this should not be a problem as any cracker who can access the password hash file, should also be able access the configuration files that set the encryption method and or loop count. This step may, however, be overlooked by the cracker, and a cracking tool using an algorithm that does not match that used to create the password hashes, will never find any passwords, regardless of the size of the dictionary and the number of transformations attempted.

Generally the most important factor in brute force cracking of passwords is how many passwords need to be examined to cover all possible passwords. Two factors determine this. They are the length of the password and the number of characters in the character set from which the passwords are formed. The number of possible passwords is the number of characters in the character set raised to the power represented by the password length. For example, the number of possible three character passwords formed by 26 letters is 26 cubed.

In "Password Cracking Using Focused Dictionaries"¹, Paul Bobby refers to 48000 "password combinations per second" on a "P2-400MHz computer". In "UNIX Password Security - Ten Years Later"², Feldmeier and Karn refer to a "top speed of 1092.8 crypts per second on a Sun SPARCStation." in 1989. Applying Moores law we should get between 100,000 and 200,000 crypts per second on a high end workstations 12 years later. Using L0phtCrack⁵, I've seen about 1.2 million "Tries/sec" using only alphanumeric characters and about nine hundred thousand "Tries/sec" using the full 95 character, printable ASCII character set, on a PIII 500. I believe the L0phtCrack number is at least in part a result of the weaker encryption used by NT as discussed on another page.

The best reasonably recent estimates I've seen were presented in the 2005 Ontario Universities Computing Conference. Johnathan Graham indicated in a Power Point pressentation that "A G5 running at 2.7Ghz with a highly optimized copy of John The Ripper hits 900,000 cracks per second.⁸ This was part of a presentation that was very knowledgeable and presented in to an audience of computer professionals. I've seen other much higher numbers recently but when looked at more closely these may be for applications, including web sites, and there is no reason to assume these should be a reliable indicator for cracking operating system passwords. This number is entirely consistent with the progression one would expect from other widely cited cracking studies. Though the figure may be approaching two years in age, the characterization of "a highly optimized copy of John The Ripper" suggests many crackers will not make as effective use of the resorces available to them.

The table below is calculated by assuming 1,000,000 encryption operations per second; this is a plausible number for a desktop PC today (early 2007). Password lengths from 3 to 14 are shown. The numbers at the top, 26 - 95, indicate the number of characters from which the passwords are formed. 26 is the number of lower case letters, 36 is letters and digits, 52 is mixed case letters, 69 is single case letters with digits, symbols and punctuation, and 95 is all the displayable ASCII characters including mixed case letters. The 69 and 95 numbers include the space which is not a legal password character on many systems. But then there are a number of idotic systems that do not allow any punctuation or symbols in their passwords. This includes at least one major bank which also limits passwords to 8 characters. The times shown are the times to process the entire set of passwords thus the average time to crack a specific password would be one half the listed times.


        26                36                   52          
 3  0.02 seconds       04.7 seconds          0.14 seconds  
 4  0.46 seconds       1.68 seconds          7.31 seconds  
 5  11.9 seconds       1.01 minutes          6.34 minutes  
 6  5.15 minutes       36.3 minutes          5.59 hours    
 7  2.23 hours         21.8 hours            11.9 days     
 8  2.42 days          1.07 months           1.70 years    
 9  2.07 months        3.22 years            88.2 years    
10  4.48 years         1.16 centuries        4.58 millennia
11  1.16 centuries     4.17 millennia         238 millennia
12  3.03 millennia      150 millennia      12,395 millennia
13  78.7 millennia    5,410 millennia     644,521 millennia
14 2,046 millennia  194,728 millennia  33,515,076 millennia
                69                         95 
 3          0.33 seconds               0.86 seconds  
 4          22.7 seconds               1.36 minutes  
 5          26.1 minutes               2.15 hours    
 6          1.25 days                  8.51 days     
 7          2.83 months                2.21 years    
 8          16.3 years                 2.10 centuries
 9          1.12 millennia               20 millennia
10          77.6 millennia            1,899 millennia
11         5,352 millennia          180,365 millennia
12       369,303 millennia       17,184,705 millennia
13    25,481,886 millennia    1,627,797,068 millennia
14 1,758,250,151 millennia  154,640,721,434 millennia

Even if a cracker has a thousand times more power available than assumed, i.e., 1,000,000 is significantly low, and the cracker can encrypt a billion passwords per second, it's very easy to find passwords that can't easily be cracked. Nine character passwords using the entire character set will do, as it will take about 20 years to work through all possible passwords. Previously I suggested 8 characters. This will probably still do as that will take a couple months, and this assumes the cracker has a significant array of computers or a super computer available. The figure may be off for a single desktop, but there is no way it is off by 1000 times, or even very likely by 10.

I extended the lengths of passwords covered by the table. This was primarily to show what happens with all lower case letters. A well chosen 12 character, all lower case password is much stronger than any 8 character password you can choose. That's a mathematical fact. It may not seem right but it is. And a well choosen 11 character password is almost as good, though like the good 8 character 95 character set password, may be borderline for some purposes. I will be discussing strong lower case passwords on a new page in the near future. This is closely related to the new Words Only option in the Password Generator.

Depending on the password and the brute force sequence, some passwords might fall quickly. For example if passwords were generated in the order of ASCII collating sequence, the poor password !!!111Aa might be found rather quickly.

The time to process a cracking dictionary is determined in a similar manner. The total number of passwords to be tried, which is a product of the number of words in the dictionary, times the number of transformations per word, is divided by the rate it takes to encrypt passwords. Complex rule sets will impose an additional significant overhead. On today's computers, small dictionaries (less than 100,000 words) with a few transformations will complete in a few seconds. The total number of passwords with large dictionaries and many transformations or huge dictionaries will be huge and the processing time correspondingly large.

Brute Force, Dictionary Comparison

As brute force is the only alternative to dictionary based password cracking it's worth taking a close look the table above. Look at how long it should take to crack eight character passwords drawing from the 95 typeable characters. One simple statement should put this in perspective. Not including NT systems, that have a seriously flawed password storage method

Randomness does have it's surprises. If numbers are randomly selected from a billion number sequence, there is a one in a billion chance that the first number will be drawn on the first try. Very unlikely but still possible. To have a 1% chance of cracking a specific random, 8 character password from the full character set takes about 20 years of computing, at 100,000 passwords per second.

An obscure word in the Afrikaans language, mirrored and all uppercased except the first letter is more likely to be used as a password than any single random character sequence of similar length. Further, where the single random sequence cannot be reliably found by existing technology today, the Afrikaans derived password surely can; it's simply a matter of the cracker having and choosing to apply sufficient resources. As a practical matter, it is unlikely that many crackers will bother with unabridged dictionaries, and foreign language dictionaries, especially obscure foreign languages, as the rewards will not likely match the effort.

Any word and all the mechanical transformations that can be described to change that word into something else is a subset of all possible combinations of the same characters. As the length of the word increases, the standard transformations become an ever smaller subset of the possible permutations. For a word of meaningful length, say more than 5 characters, the word and its transformations is an infinitesimal subset of all possible combinations of the same number of all characters. In other words, the longer the passwords to be cracked, the larger the advantage of a dictionary based attack will be compared to a brute force attack. Here "dictionary based attack" is understood to include custom programmed dictionaries as described in a subsequent page in this section.

Copyright © 2000 - 2006 by George Shaffer. This material may be distributed only subject to the terms and conditions set forth on http://GeodSoft.com/terms.htm. These terms are subject to change. Distribution is subject to the then current terms, or at the choice of the distributor, those defined in a verifiably dated printout or electronic copy of http://GeodSoft.com/terms.htm at the time of the distribution. Distribution of substantively modified versions of GeodSoft content is prohibited without the explicit permission of George Shaffer. Distribution of the work or derivatives of the work, in whole or in part, for commercial purposes is prohibited unless prior permission is obtained from George Shaffer. Distribution in accordance with these terms, for private, unrestricted and uncompensated public access, non profit, or internal company use is allowed.

Good and Bad Passwords How-To

Password Cracking Goals, Techniques, Relative Merits, and Times

Goals of the Cracker

Cracking Tool's Feature List

Cracking Tool Examples

How Long Does It Take to Crack Passwords?

Brute Force, Dictionary Comparison