Password Cracking Goals, Techniques and Relative Merits and Cracking Times of Different 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. 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
•Password Cracking Programs’ Feature List
•Password Cracking Program Examples
•How Long Does It Take to Crack Passwords?
•Table of Times to Crack Passwords
•Brute Force, Dictionary Comparison
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.
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.
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 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 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 tested passwords multiplies rapidly. Every “clever” way of manipulating words to hide their origin is know 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.
* Append or prepend defined characters to a word.
* Reverse a word.
* Duplicate a word.
* Mirror a word, i.e. append the reversed word.
* Rotate a word either left or right, i.e. move the first letter to the end or the last letter to the front.
* Upper case a word.
* Lower case a word.
* Make only the first letter a capital.
* Male all but the first letter a capital.
* Toggle the case of all characters.
* Toggle the case of a character at a set position.
* Minumum and maximum word lengths can be set or long words can be truncated at a set length.
* Suffixes (s, ed, ing) may be added to words.
* First, last or any specific character may be deleted.
* Characters can be replaced at a set location.
* Characters can be inserted at a set location.
* “Shift” the case, i.e. substitute the other character on the same key, e.g. ‘a’ and ‘A’ or ‘5′ and ‘%’.
* Shift the characters left or right by keyboard position (so an ’s’ becomes an ‘a’ or ‘d’).
* Replace all of one character with another.
* Replace all characters of a class (for example vowels, letters, non letters, digits) with a specific character.
* Remove all occurrences of any character from a word.
* Remove all characters of a class from a word.
* Reject a word if it contains or doesn’t contain a character, or characters from a class.
* Reject a word if the first, last or set character is or is not a specific character or from a class.
* Reject a word unless it contains at least so many of a character or characters from a class.
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.
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:
* Lower case pure alpha words.
* Lower case and pluralize alpha words.
* Append digits and punctuation to all pure alpha words.
* Lower case and reverse pure alpha words.
* Lower case and mirror pure alpha words.
* Capitalize all alphanumeric words, i.e. first letter only.
* Capitalize all alphanumeric words and add a variety of common punctuation so ‘cats’ becomes Cats! Cats? Cats. Cats, Cats- etc.
* Upper case all alphanumeric words.
* Remove vowels from pure alpha words.
* Remove white space and punctuation from those words that have it.
* Duplicate short words.
* Perform most of the similar looking character substitutions identified in the list of dont’s.
* Lower case and prepend digits (all words).
* Capitalize then reverse alphanumeric words.
* Reverse then capitalize words.
* Upper case words adding common punctuation and swapping zero for O.
* Upper case then duplicate, reverse and mirror words.
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 deteremine 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 password2.
Probably 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.
The table below is calculated by assuming 100,000 encryption operations per second; this is a plausible number for a desktop PC today. In “Password Cracking Using Focused Dictionaries”1, Paul Bobby refers to 48000 “password combinations per second” on a “P2-400Mhz computer”. In “UNIX Password Security - Ten Years Later”2, 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 eleven years later. Using L0phtCrack5, 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.
Password lengths from 3 to 12 are shown. The numbers at the top, 26 - 94, 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, 68 is single case letters with digits, symbols and punctuation, and 94 is all the displayable ASCII characters including mixed case letters. The times shown are the times to process the entire set of passwords thus the average time to crack passwords would be one half the listed times.
26 36 52
3 0.18 seconds 0.47 seconds 1.41 seconds
4 4.57 seconds 16.8 seconds 1.22 minutes
5 1.98 minutes 10.1 minutes 1.06 hours
6 51.5 minutes 6.05 hours 13.7 days
7 22.3 hours 9.07 days 3.91 months
8 24.2 days 10.7 months 17.0 years
9 1.72 years 32.2 years 8.82 centuries
10 44.8 years 1.16 millennia 45.8 millennia
11 11.6 centuries 41.7 millennia 2,384 millennia
12 30.3 millennia 1,503 millennia 123,946 millennia
68 94
3 3.14 seconds 8.3 seconds
4 3.56 minutes 13.0 minutes
5 4.04 hours 20.4 hours
6 2.26 months 2.63 months
7 2.13 years 20.6 years
8 1.45 centuries 1.93 millennia
9 9.86 millennia 182 millennia
10 670 millennia 17,079 millennia
11 45,582 millennia 1,605,461 millennia
12 3,099,562 millennia 150,913,342 millennia
Even if a cracker has a thousand times more power available than assumed, e.g., 100,000 is significantly low and the crackers has lot of fast computers or a supercomputer, it’s very easy to find passwords that can’t easily be cracked. Eight character passwords using the entire character set will do, as it will take nearly two years to work through all possible passwords. 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 the same 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 may impose an additional significant overhead. On today’s computers, small dictionaries (less than 100,000) 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
It is highly unlikely that any cracker has ever gotten even a single password, eight characters or longer, randomly created from the entire 95 printable ASCII character set.
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
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 subsequent pages in this section.
source:from:\ Geodsoft
Posts
