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.

In early 2007 I wrote the following: ' 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.'

In other words the data that I used in 2007 to estimate cracking times was likely two and perhaps three years old. Using Moore's law only and extrapolating from my original calculations, my 2007 numbers should have been about 25 times faster than my 2001 numbers based on data from 2000, rather than merely 10 times faster. This time, late May 2012, I'm using Moore's law only and applying it to data from 2000. Allowing for doubling every 18 months, in 12 years we get 2 ^ 8 or 256 times 100,000 or 2.56 million cracks per second. I think in mid 2012, 25,000,000 cracks per second is a reasonable number for a fast desktop - one with a fast Intel i7 or top end AMD 6 core processor.

The table below is calculated by assuming 25,000,000 encryption operations per second. Password lengths from 3 to 15 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; a major online brokerage service also has similar limits. Why do some of the institutions with the most sensitive data have the worst possible password policies? 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.0007 seconds     0.0019 seconds       0.006 seconds  
 4   0.018 seconds      0.067 seconds       0.292 seconds  
 5   0.475 seconds       2.42 seconds        15.2 seconds  
 6    12.4 seconds       1.45 minutes        13.2 minutes  
 7    5.35 minutes       52.2 minutes        11.4 hours    
 8    2.32 hours         1.31 days           24.7 days     
 9    2.51 days          1.57 months         3.53 years    
10    2.18 months        4.64 years          1.83 centuries
11    4.66 years         1.67 centuries      9.53 millennia
12    1.21 centuries     6.01 millennia       496 millennia
13    3.15 millennia      216 millennia    25,781 millennia
14    81.8 millennia    7,789 millennia   1.34e+6 millennia
15   2,127 millennia  280,408 millennia   6.97e+7 millennia
             69                      95        
 3       0.01 seconds            0.03 seconds  
 4       0.91 seconds            3.26 seconds  
 5       1.04 minutes            5.16 minutes  
 6       1.20 hours              8.17 hours    
 7       3.45 days               1.08 months   
 8       7.93 months             8.41 years    
 9       44.9 years              7.99 centuries
10       3.10 millennia          75.9 millennia
11        214 millennia          7215 millennia
12     14,772 millennia       685,388 millennia
13    1.02e+6 millennia       6.51e+7 millennia
14    7.03e+7 millennia       6.19e+9 millennia
15    4.85e+9 millennia      5.88e+11 millennia

* If you don't know what 5.88e+11 means

If you think I got the cracks per second wrong, or would like to see the effect of different computer speeds, password lengths, or character set sizes try the Crack Time Calculator.

Even if a cracker has a thousand times more power available than assumed, i.e., 25,000,000 is significantly low, and the cracker can encrypt 25 billion passwords per second, it is still not difficult to find passwords that can't easily be cracked. Ten character passwords using the entire character set will do, as it will take about 7 years to work through all possible passwords. Even this may be questionable as that is an average of 3.5 years for one fast desktop. In 2001 I suggested 8 character passwords. Today, such passwords are inadequate for important accounts.

Three things have changed that make strong passwords for important accounts more important than ever. The replacement of single core computers with multi core computers has quickly increased the computing power available in home and typical business environments. I don't think Moore's law has changed with regard the the fastest computers available, but I do think the change to multi core computers has caused a short term spike in the total amount of computing power that is generally available. Today a mid range to high end desktop has the processing power of supercomputer from not much more than a decade ago. There is little reason to think most of these are much more secure than home computers were in the past. I believe the average home computer represents only a modest challenge to a skilled cracker and that there are millions of compromised computers in homes and offices available to non owners for illicit use.

Second, a variety of cracking tools are available that take full advantage of multi core computers and that are also network ready. Few tasks are better suited to distributed network processing than password cracking. It doesn't matter whether these are computers left on overnight in a business that only works in the day, or a college computer lab, or a network of dozens to hundreds or more computers previously compromized by a cracker. Even if someone is working on a computer that is working on cracking passwords, the chances are good they will never notice that activity. I can run three, CPU intensive processes on my six core AMD tower, and never notice that anything unusual was going on, if I did not routinely check my performance monitors that record what each core is doing, and log CPU levels continuously with custom tools I've developed.

Third, and probably most importantly, hacking or cracking has changed form a hobby like activity persued for intellecutall satisfaction or reputation in certain "communities" to a mainstream criminal activity. With the move of much commerce to the Internet, criminals were bound to follow. Organized crime can spend as much on targeting a large financial institution as big business can spend on computer security. Why not employ several reasonably skilled crackers to do nothing but break into home and business computers to assemble a network of slave computers to perform any computational task required. It's a lot cheaper to steal CPU cycles than to buy the equipment to provide comparable perfomance. How would you like criminals to have access to your bank or brokerage account?

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 14 character, all lower case password is as strong as a good 10 character password using mixed case, number, symbols and punctuation. That's a mathematical fact. It may not seem right but it is. 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, as the exclamation mark is the first visible typeable character in the ASCII sequence.

Brute Force, Dictionary Comparison

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.

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

This was written in 2001 and never changed. Then I listed the cracking time for all 8 character passwords as just under 2 millennia. Multi core processors were only in high end servers and network cracking tools were not available. I know there is is a demonstration project using a large network of volunteer computers that has cracked stronger passwords. Things change quickly in the computer world and a decade plus is a long time.

If someone is cracking passwords for real, it means they have the hash file (the file of all passwords) for some computer or institution. While no one might spend months or a year trying to get your password, if they have the password file for online access to a major bank or brokerage service they may have hundreds of thousands or even millions of passwords to try to crack. For a criminal organization, that would easily be worth months of computer time. All weak passwords would be cracked and many that looked like good passwords. If you use this bank or brokerage service and your password is not mathmatecally strong, and entirely free of any dictionary or related weaknesses, it will be one of those cracked.

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. This was true in 2001 when it was written. Today, with one fast desktop, it would be less than a month.

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. Again, no longer true.

One of the password crackers today includes a multilingual unabridged dictionary with 21 languages. Interestingly Chinese, Indian, Spanish and Portugese are not included; this leaves out the two most populous countries in the world and all of Central and South America. Arabic and Farsi were also missing. Still it's a good indication where cracking tools are going. Afrikaans was included, as were nearly all industrialized countries including Japan.

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.

I discussed programmed dictionaries in 2001, eleven years before I ever saw a reference to such a thing in conjunction with a password cracking tool discussed anywhere else. Now the same tool that has the multilingual dictionary, has a programed dictionary that creates passwords created by a popular password generator. The programmed dictionary feeds the generated passwords directly to the cracking tool so that they do not need to be stored to disk. It's easy to describe programmed dictionaries that have so many possible passwords, no institution on Earth has enought disk space to store them. Huge dictionaries must be fed directly to the cracking tool without using disk space. Five years ago this was not true, but it is now clear, that every method of generating plausible passwords, is comming into use with the cracking tools. Available computing power has increased to the point that all these CPU intensive processes are now becoming practical. Though I cannot predict how long it will be, it is now clear passwords have a finite lifespan, in which they must be replaced by a more secure technology.

Scientific notation may look odd to those not familiar with it, but for very large numbers, it's easier to read than the conventional fixed notation. For medium size numbers (millions to billions) it may not be easier to read, as long as a comma is used every three places, but it is shorter. I chose to use it for all numbers, one million and larger. It's very appropriate because all the cracking times are estimates based on assumptions, not the acutal time that a specific operating systems's passwords would take to crack on a specific stand alone computer or a network of known computers. The starting number I use, cracks (or encriptions) per second, could be 3 to 6 orders of magnitude higher (1000 to 1,000,000 times faster) for NSA. It is possible it's lower and not very improbable it's even higher. No one outside the agency will ever know.

Like many things, scientific notation, is best explained with some specific examples. 1.33e+6 is one and a third million. Scientific notation always starts with a floating point number between 1.00 and 9.99999... Because there is no need for precision in my numbers I limit them to three "significant figures." If 9.99999 stoped with 6 digits that would be 6 significant figures. Sometimes more significant figures are used but that is not relevant here. I assume the "e" stands for exponent. The plus sign means a positive exponent; the decimal point, plus as many zeroes as may be needed go to the right. (Negative exponents are used for numbers smaller than 1.)

The number after the plus sign tells us how many places to move the decimal point. If it's 6, it's for a number between one million and one not quite large enough to round up to an even 10 million. 7 is for 10 to just under a hundred million. 9 is for one billion to just under ten, and 11 for 100 billion to just under one trillion.

Copyright © 2000 - 2012 by George Shaffer. This material may be distributed only subject to the terms and conditions set forth in http://GeodSoft.com/terms.htm (or http://GeodSoft.com/cgi-bin/terms.pl). These terms are subject to change. Distribution is subject to the current terms, or at the choice of the distributor, those in an earlier, digitally signed electronic copy of http://GeodSoft.com/terms.htm (or terms.pl) from the time of the distribution. Distribution of substantively modified versions of GeodSoft content is prohibited without the explicit written 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 written permission is obtained from George Shaffer. Distribution in accordance with these terms, for 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