GeodSoft How-To: Cracking Passwords Techniques

Historically, password crackers were most interested in root or administrative account passwords when they cracked passwords. With the movement of organizied crime, into the realm of computer and password cracking, mostly working out of Eastern Europe, and mostly targeting financial and e-commerce web sites, any accounts and sensitive customer information would likely be of interest. The methods used to gain unauthorized access to systems is beyond the scope of this discussion. The tools and methods for cracking passwords are the same regardless of who is using them. They are password cracking programs that use password dictionaries or brute force. The feature lists of common password cracking programs are discussed. Also listed are the suggested standard dictionary transformations for Crack, once 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 crackers has been to obtain the root account password on UNIX systems and administrator accounts on Windows systems. These accounts will always be of more value than ordinary users on these 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 which are not available to ordinary users on modern systems), 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.

With the movement of organized crime into these activities the targets are likely to shift. Instead of targeting the employee administrators and operators of web sites, the customers of financial and e-commerce web sites have become the real targets. So far, at least, it seems that the web servers have been an entry point to the internal networks of the compromised companies, from which they have then stolen customer information.

I have found no evidence that these criminals have targeted end user web accounts at either financial services or ecommerce sites. That they have not done so only means they have not seen the opportunity to realize sufficient gains. It seems clear a significant portion of the U.S. online financial services industry has been compromised. These criminals clearly have both the technical skills and necessary financial and computer resources to crack most web account passwords if they saw a good reason to do so.

At least for the present financially motivated criminals don't seem to be interested in consumer web accounts at either financial services or ecommerce sites. Their is little reason to be relieved at this. The accounts and password hashes are there for the taking. Security is poor enough at many sites and it's simply more rewarding to go directly for the entire customer database as Sony's 77 million customer's whose credit cards were compromised learned. At those sites that don't have absurd restrictions on passwords that prevent strong passwords, I have upgraded my passwords since I heavily revised this section in 2012, to account for the increases in computer speed and recent developments in password cracking.

Where customer's passwords are not the target, intruders are likely to need only one password for an account with suitable privileges. Additional accounts may be of some value in preserving access, but are 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.

When I wrote this page 13 years ago, 8 character passwords with mixed case, one or more digits, a symbol or puncutation mark, and designed so it was not vulnerable to a dictionary attack were sufficient to be confident your password was safe. Today, a lot depends on who is cracking a password list with your password in it. 10 characters may be safe or pretty marginal. 12 characters appear to be safe against almost anyone except government agencies such as the NSA. There are so many factors, some of which are not knowable, that I normally choose 14 characters for accounts that matter.

While all 8 character passwords would still take years on one fast desktop or hours on a fast network of computers set up for cracking passwords, a brute force approach is not likely to be necessary. Users insist on creating bad passwords. Just over 90% of all known cracked passwords are in this top 10,000 password list. All a cracker needs to do is use this list as their dictionary and in seconds they will get about 70% to 95% of the passwords on most systems. 93% of the passwords cracked in the early June 2012 compromise of the business networking site linkein.com were in this list.

If they do not get the account(s) they want or need on a system with a large common password list, the crackers will turn first to a small standard dictionary plus common names, and perhaps less common passwords and or numeric repeats and sequences, keyboard sequences, and alphabetic repeats and sequences, along with common rules. A skilled cracker will work through a progression of dictionaries and rules that have worked in the past. Only for something very important to them, that has not fallen with their normal techniques, will a skilled cracker use a brute force approach, or more unusual dictionaries and rule sets.

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 have personal meaning to them as their passwords; these can nearly always be found in dictionaries or word lists. 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 hashing 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 and those who use them.

To understand what make weak and strong passwords, it's necessary to understand what cracking tools can and cannot do. When this page was first written, L0phtCrack was the leading Windows cracking tool. The easy to use L0phtCrack with its GUI interface is rather limited compared to Crack 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 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).

L0phtCrack has been superceded by other tools on Windows. In particular there are two tools that make use of rainbow tables to target Windows systems. Rainbow tables are a form of a sophisticated dictionary attack using precomuted hashes. They include very sophisticated storage methods that do not require all the hashes to be stored. They check the ends of "chains" of hashes. They can determine if a password is part of the chain without computing every password in the chain. Only after it is determined that a password is part of a chain is each password in that chain computed and it's individual hash compared with the one in the password file. This takes more computation than if all the computed hashes were stored, but even with today's disks, all possible passwords up to reasonable lengths to test cannot be stored on disk. Rainbow tables allow enough passwords to be stored that they claim a 99% success rate on passwords up to 13 characters and 96% on 14 character passwords.

Rainbow tables only work against Windows systems because all Windows systems convert the same plaintext password to the same hash. This is incredibly stupid. The problem was well understood before Microsoft developed it's password storage method. Since Unix has had passwords, all Unix and Unix like systems have used random "salts" to cause each plaintext password to be stored with a different hash. Origninally the salts were only large enough to have 4096 variations. Today the salts are large enough it is unlikely anyone will ever find two passwords stored with the same hash on any Unix like system. Precomputation attacks cannot work against Unix like systems or any system, including web sites, that use a proper salting mechanism. For 20 years Microsoft has refused to acknowlege there is anything wrong with their grossly inferior password storage method. This will be explained in detail on my Windows Passwords page.

Both John the Ripper and Crack 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 as do several other cracking programs.

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 (Unix like systems, only). 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?

Password Strength

Conceptually the easiest way to crack passwords is to generate character sequences working through all possible 1 character passwords, then two characters, then three characters, etc. This is the brute force attack previously mentioned. It could start at any specific length password. Each trial password is hashed the same way as those under attack; if the resulting hash is identical to the attacked password hash, the test password that generated the new hash is the password being looked for. Theoretically any possible password can be found this way, but generally there is not sufficient computing power available to successfully accomplish this, once passwords reach a certain length and character diversity. Generally as computers have gotten faster passwords have needed to get longer and more character diverse. A number of factors determine how long brute force attacks will take. Some may be under a system administrators control but most are not; others may or may not be under web site developer's control.

Most of the same factors that affect brute force attacks also apply to dictionary attacks. The number of passwords to be tested is simply the size of the dictionary times the number of transformations to be made per word. There is an immidiate complication; some transformation rules are not applied if conditions in the rule are met. In such a case no number can reasonably be calculated except an upper limit. Once a number of passwords to be tested is known, it is simply a a matter of dividing this number by CPS or cracks per second. Most crackers don't just make one dictionary attempt on a list of accounts and hashes. They try a small high yield dictionary first then a larger lower yield dictionary, with more or different transformations. So with dictionary attacks there are no simple calculations to perform; it's more about predicting a cracker's course of action or an average cracker's course of action. Ultimately every cracker reaches a decision, when he has enough passwords from a list, or when fruther resources are not likely worth the return. That's why cracking times are listed for brute force attacks only.

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 lower case letters is 26 cubed. The character groupings are typically considered to consist of lower case letters (26), upper case letters (26), digits (10) and symbols and punctuation (33 if the space is included). Obviously the strongest passwords include at least one of each from all four groups or 95 characters. The general formula described above is often expressed as "characters ^ length" so an 8 character password using all four sets would be 95^8.

Some people may choose to consider subsets of characters (vowels and consonants) or other factors that affect the strength of the password. This depends on how easily and likey it is that someone attacking passwords can adjust the search criteria. For example upper case letters, when used, are almost always used in the first character position and very rarely any place else, except when all letters are upper case. Good crackers like to go with the odds and there are few things easier to do than check the first character position for upper case letters. Nearly all password cracking tools have a built in option that will do this. This should get more than 95% of the passwords with an upper case letter with a fraction the cost of checking all positions. If all passwords were done this way first, the cracker can choose to come back and do the other positions in a separate step, or if there are only a few uncracked passwords he may choose to move on to a more rewarding project. This would be even more efficient if the letters to be uppercased were orderd by the frequency that letters are used to start words in an unabridged dictionary, or the frequency that capital letters occur in the local languge, or the frequency of upper case letters in passwords the cracker had previously cracked. My Password Evaluator separates the symbols into common punctuation, common symbols, and programming symbols; if any 2 from different groups are used, full credit for 33 is given, otherwise only the number of characters in the subgroup is counted. Common punctuation marks are used much more frequently in general use than symbols from the other groups, and so punctuation marks should be more common in passwords than the other symbols.

Cracking tools are designed to provide built in options that facilitate finding commnon ways in which passwords are created, and crackers use what is widely known about the formation of common passwords, plus their own personal experience. People have shown again and again, despite the overwhelming advice to the contrary, to be highly predictable in creating passwords in ways that are easily cracked. Using the cracking tool's capabilities and what is known about how crackers work, makes more sense that to use a simple unvarying mathematical formula which makes no allowance for cracking tool capabilities and cracker behaviour. Any seriously considered variation that takes both toool and cracker capabilities into account should result in more refined estimates, than the simple formula.

Computing Power

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. In 2014, a computer is likely to have approximately a billion times the computing power available when the first UNIX was developed in the very late 1960s and early 1970s.

Speed Changes 2001 - 2014

In 2000, 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 Moore's 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. Considering these in 2001 I used 100,000 CPS for my desktop system.

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 presentation 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 resources 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. In late May 2012, I used Moore's law only and applied it to data from 2000. Allowing for doubling every 18 months, in 12 years we get 2 ^ 8 or 256 times 100,000 or 25.6 million cracks per second. In mid 2012, 25,000,000 cracks per second seemed a reasonable number for a fast desktop - one with a fast Intel i7 or top end AMD 6 core processor. In 2012, I added a table for a fast cracking network, with 10,000 times the speed of a single desktop.

In January 2014, about 20 months after I last recalulated the password cracking time tables, for the first time I have current numbers for specific hardware and identified hashing algorithms. This is thanks to Hashcat. On a single CPU PC with an AMD Phenom II X6 1090T, overclocked to 3.8 GHz, running Hashcat v0.40, 64 bit, on Windows 7, three hash algorithmes were tested. Phpass ran at 50,000 CPS, NTLM at 71,000,000 CPS and MD5 at 86,000,000 CPS. This processor is about 4 years old but overclocked to put in in the range of contemporary medium to high end desktops. I adjusted my single desktop (in the tables below) to 75,000,000 CPS.

New Developments

Multi Core Computers

Four 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. Though graphics, gaming and other CPU intensive uses will never have excess CPU power, typical office and Internet applications rarely push mid to high end desktops to full capacity except for infrequent, short spikes. In the second decade of the 21st century most home and office computers are typically doing the automotive equivalent of idling, or maybe rolling along a city street at 20 to 35 m.p.h nearly all the time.

In the past decade Microsoft has improved its performance with regard to security and the timely availability of security related upgrades. Despite this, I'd guess, is that there are tens, more likely hundreds of millions, of 1 to 4 year old Windows computers that are not up-to-date with security patches. I believe with Windows 7, fully automatic updates are the default. Unfortunately, these and the reboots which normally accompany them often occur at inopportune times. I expect that many users disable automatic updates. Even if every Windows computer in the world was fully up-to-date with all security patches, it would be naive to think this is sufficient to ensure these computers are immune to network penetration. In practice, there is little reason to think that most home and small business computers are much more secure than they were in the past. I believe the average home computer represents only a modest challenge to a skilled cracker and that there are many millions of compromised computers in homes and offices available to non owners for illicit use.

Unless the user actively monitors their CPU use they will never know anything unexpected is running on their computer. Once one of these clients is detected and reported to any security organization, anti-virus and malware scanners should be able to detect such software. On the other hand there are sophisticated methods to hide viruses and malware from the scanning tools. Few would have better motivation than criminals, to ensure the software they need, was difficult to detect on the compromised computers on which they were depending. Also, those with compromised computers are most likely to be those who do not take the steps to actively defend their computers.

Graphics Processing Units

Second, there is a fairly new development which very much does impact on Moore's law. This is the development of Graphics Processing Units (GPU), which can be added to a standard desktop computer as easily as a video card; you do need an appropriate type video slot in the motherboard. Some motherboards have two video card slots. One of the tasks that GPUs are very well suited for is password cracking. When a GPU is being used for non grapics purposes, it is sometimes called a GPGPU or general purpose GPU. GPUs are a part of high end video cards that sell for $80 to $1,400. GPGUPs add massive parallel processing capabilities to a desktop PC. Some GPU's approach 4000 streaming processors, which for appropriate tasks, like cracking passwords, is like adding 4000 cores. The performance increase varies depending on the specific hashing algorithm as well as the specific GPU.

At least two companies are selling Windows cracking software specifically designed to take advantage of GPUs. These Windows cracking programs are products I more or less stumbled on. I did no systematic search. Other well known and more general products, like John the Ripper are likely to follow with GPU optimization. Basically for the price of a high end desktop, plus a few hundred to a couple thousand dollars for the cracking software which may include rainbow tables, one can now have a small super computer to crack passwords. There are even free products with these cpabilities.

oclHashcat is free and optimized to use CUDA and Stream enabled video cards. It runs on both Windows and Linux. Its devlopers tested it with 5 GPU video cards that are available for around $400 to $700, and a variety of widely used password hashes. The Windows PC with an Nvidia gtx580 cracked NTLM hashes at 3.9 billion CPS or 55 times faster than the single CPU PC listed above; this is one of the slower machines. The fastest used eight AMD R9 290X cards (or perhaps 4 double R9 290X) and ran at 141 billion CPS or another 36 times faster than the gtx580, or 1980 times faster than the single CPU PC. For about $2500 plus a high end PC with sufficient video slots, you can make a desktop PC almost 2000 times faster than a contemporary high end multi core desktop without GPU(s), for cracking NTLM hashes.

Network Cracking

Third, password cracking lends itself well to parallel processing on multiple machines with near linear gains as more machines are applied to the problem. Computers with a wide range of speeds may be available and typically this makes no difference to distributed processing tasks. Work is parcelled out in blocks; the slave computer may take minutes or hours. When the work is returned to the controlling computer, an new block is normally sent to the slave. If no results are returned to the controlling computer after some extended time period, the work is assigned to another slave. 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 several orders of magnitude at any specific point in time.

A variety of cracking tools are now available that take full advantage of multi core computers and that are also network ready. Both Hashcat programs and John the Ripper (all free) are 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 compromised 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. Three CPU intensive processes can be running on my six core AMD tower, and I would never notice that anything unusual was going on, if I did not routinely check performance monitors that record what each core is doing, and log CPU levels continuously with custom tools I've developed.

There is an academic project working on cracking a 72-bit encrypted key. This project uses a large network of volunteer computers. It is currently running at more than 7,500 times the speed of my single fast desktop (75,000,000 CPS). Twenty months ago they were 30,000 times the speed of a single desktop (then 25,000,000 CPS). Based on Jan. 14, 2014's number of 574 billion keys per second versus their overal history of 415 billion keys per second (going back to 2004), I was going to say they are obviously not keeping up with technology advances, but their keyrate history shows they have actually dropped by about a third since 20 months ago. While the owners of the computers in this project have chosen to install client software that lets their idle CPU cycles be used by this project, there is no reason anyone who can hack into a home or business computer could not install comparable software for their cracking projects. These clients are desinged to be unobtrusive. As soon as the user starts to do something they either go idle, or scale back so as not to interfere with what the user wants to do on their computer.

The platform that has contributed by far the most CPU power to the above academic project are Stream enabled GPUs on Windows systems. The first Windows computer using a Stream compliant video card joined the project on July 19, 2009, and in less than 4.5 years, in a decade plus project, have contributed almost 61% of the work. In five more months, Linux PCs with Stream compliant video cards have contributed only 6% of the work done by Stream enabled Windows PCs. There is no reason to think the Linux PCs should be any slower than a similar Windows PC. In the oclHashcat comparison, the one Windows PC was only somewhat faster than 2 Linux PCs and much slower than two other Linux PCs; most if not all of this difference is likely to be due to the GPU processor installed on the two very fast PCs. Linux users tend to be more technical than Windows users, so there is some reason to suspect there might be more support for a project like this in the Linux community than among Windows users. The reasonable conclusion is that Windows PCs with Stream video cards are both fast and not uncommon.

oclHashcat can work with up to 128 GPUs. We saw a gain of nearly 2000 times with the NTLM hash, so 6 similary configured computers would give more than the 10,000 times estimate for my fast cracking network. If 16 such computers (16 x 8 = 128) could be found (compromised), that works out to 2,786 billion CPS or 3.7 times the speed of my fast cracking network. It would likely be a challenge to find and compromise such a perfectly suited collection of computers.

Organized Crime

Fourth, and perhaps most important, hacking or cracking has changed from a hobby like activity persued for intellecutal 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 or retail institution as big business can spend on computer security. Start with a core of several of several GPU enabled computers and extend that to network hacked systems. 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 performance.

We can only guess at how much computing resources a criminal organization may be willing or able to assemble. One public network working on a similar problem with a capacity close to my fast cracking network has already been discussed. There is nothing technological to stop an organization with large resources from going up another order of magnitude or more. An article on CNN Money stated '"If you think about the money that organized crime has, if they throw out $100,000 to attack you, it's hard for a corporation to fight against that," said Dave Aitel, president of security firm Immunity Inc. and a former computer scientist at the National Security Agency.'

What a criminal enterprise may do will depend on their estimate of costs versus payoff. In doing some reading on organized crime computer crime, I was almost ready to dismiss the relevance of financial accounts and passwords, when I read that that on May 10, 2011, "about $2.7 million was stolen from about 3,400 accounts" as reported by CNN.com. No specifics were given in this article. To date most attacks on both retail and financial institutions have gone directly for the customer data containing credit and debit card information. Most have involved using the stolen data to manufacture fraudulent credit and debit cards and then hitting thousands of ATM machines at the same time over wide areas in Eastern Europe. As soon as criminals figure out a way to make serious money out of direct access to bank and brokerage accounts, I would expect them to target the password files that are the keys to accessing these accounts

Cracking Tool

Another factor in cracking speed is the password craking tool itself. In March of 2012, Martijn Sprengers and Lejla Batina gave a presentation on "Speeding up GPU-based password cracking." They used a PC with an Nvidia GTX 295, a GPU that is older and slower than those used by oclHashcat, but still widely available. One vendor sells 3 variations ranging from $80 to $275. They provided four speed speed comparisons of software cracking the widely used MD5 hash. The first was John the Ripper, arguablely the best known password cracking tool, but is not yet able to use a GPU. It performs between 2,500 and 5,000 CPS. Sprengers and Batina's software, labeled as "Our CPU implementation," without a GPU ran at about 25,000 CPS. oclHashcat ran at 720,000 CPS. Their highly optimized version labeld "Our GPU implementation" ran at 875,000 CPS. In the same PC we see two hardware configurations with two products running without the benefit the massively parallel GPU, and two that do use it. The fastest implementation is between 175 and 350 times faster than the slowest.

Normally the cracking tool recognizes the hashing algorithm from the resulting hash. For systems that allow the administrator a choice of encryption methods or various loop counts, the cracking tool must correctly match these. The first few characters of many hashes are a code that identifies the hash scheme, includes the salt when used, and may identify the loop count. If for any reason the cracking tool uses an algorithm that does not exactly match that used to create the password hashes, it will never find any passwords, regardless of the size of the dictionary and the number of transformations attempted.

Hashing Algorithm

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. Over time as computers have gotten faster new hashing algorithms have become slower to offset the increase in computer power. 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². Newer algorithms attempt to find a logic not likely to have a fast implementation.

The Hashcat password recovery software project has published cracking times for a number of different password hashing algorithms in use in 2014. On roughly comparable hardware, of those algorithms for which Hashcat has published numbers there is a spread of about 5 million times from the slowest algorithm on the slowest PC to the fastest algorithm on the fastest PC. Here slow is better for the password owner and fast is better for the cracker. On the same PC, the spread is somewhat over 100,000 times from the slowest to fastest algorithm. Each PC setup interacts differently with each algorithm. While some PCs are generally faster than others, in one case PC3 is almost twice as fast as PC4 on one algorithm, but PC4 is about 1.5 times faster than PC3 on a different algoritm.

Hash Iterations

Since the early 2000's there has been a new development, limited mostly to some Unix variants, and not yet widely used, which has the potential to shift password security back in favor of those trying to protect the passwords. This is system administrator control of the number of hashing iterations performed, often called password loops, rounds, or cycles control. These are normally available only with newer and already relatively slow hashing algorithms.

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, or when a user logs onto the system, the longer it will take when trying to crack the password. Though older hashing algorithms have had fast implementations used for cracking, newer hashing algorithms try to make it a design goal to make alternative, fast implementations difficult to create. Thus the amount of time it takes to create the original hash when a password is created or changed, or the authentication time when a user logs onto a system is an indicator of how long a cracking cycle will take.

Loging into a local text terminal or switching users (su) in text mode have very little overhead that obscures how long the hashing process takes. In practice these normally occur too quickly for one to be aware of the passing time. On many Unix and Unix like systems the now obsolete md5crypt hashing algorithms remains the default. Many of these systems offer newer stronger algorithms. SHA256 and SHA512 are common; SHA512 should be preferred. It's clearly stronger than SHA256, and has been available over 5 years with no flaws found. Both normally offer rounds control as a system adminstrator option.

Based on the performance numbers supplied by oclHascat (near page bottom) SHA512 appears on average about 60 times stronger than MD5. Hashcat identifies SHA-512, SHA512(Unix), and sha512($salt.$pass) as different algorithms. All Unix and Unix like systems have used a ($salt.$pass) approach with all algorithms since the 1970s. The use of a salt does not affect encryption time, but it ensures that the same password is very unlikely to have the same hash for different users or on different systems. By not qualifying SHA512 in their performance table, I believe the times are for a single unsalted cycle as it might be used on a web site or in another application password and not as SHA512 is used in Unix.

On the Linux distributions with which I'm familiar, 5000 rounds is the default for SHA512, and this can usually be changed by a system admin. MD5, as it is used to hash passwords on Unix systems is hard coded to 1000 rounds. Thus by switching to SHA512 you automatically get passwords 300 times stronger. Current passwords are not affected. A password must be changed for the new hashing scheme to take effect, but on average, a password of the same length and characater diversity will take 300 times longer to crack.

On a system with an obsolete dual core CPU, the 5000 rounds is imperceptible when su'ing in a text window. I configured a million rounds and this took a little over a second to su. Combined, these yield a 60,000 times password hash strength increase over the normal Linux default. This is for changing or adding a couple of lines in a couple configurations files and imposing a minor user inconvenience. Unfortunately, where these changes need to be made is poorly documented on the systems I'm familiar with. With the last couple changes in the cracking time tables, I've started arguing for 12 character and longer passwords. With system adjustments like these, I think 9 or 10 characters may be fine. On a contemporary desktop, I think 10 million rounds might take a little over a second, though I do not know if password hashing will take full advantage of multi core CPUs.

The poor documentation, plus searches of multiple Linux fourms and mailing list archives shows this topic has never been discussed in these locations before I raised it. The near total lack of response shows almost no one who has access to this powerful tool knows how to use it or understands its importatance. SHA256 and SHA512 are available on other Unix variants besides Linux. From what I've read, it seems that iteration control is a common part of these hashing algorithms. I very much doubt the situation is significantly different on non Linux systems.

A second may sound like a lot, and an annoyance to users, as it is clearly perceptible. In fact though, nearly every day spent on a computer involves many waits longer than a second, and few if any of these waits have any beneficial results. Compare this to the time it takes someone who only uses strong passwords and never reuses them, but needs to write them down, to retrieve and return a slip of paper from a purse or wallet, a safe or strong locked file cabinet, or a good hiding place (if such exists); in this context a second is minor. With dozens to hundreds of passwords, good 9 or 10 character passwords will still need to be written down. Those that are used regularly should, however, be learned fairly quickly and not need to be referrenced.

Salts

There is one other factor that greatly affects cracking speed, or to be more accurate whether or not there is a need to even bother with cracking some passwords. This is called a salt. It is a random piece of information that is added to the password to prevent two passwords that are the same from having the same hash. In many current Unix and Unix like systems the salt consitsts of 8 random characters from a 64 character set. Password is one of the most common passwords. Without salts, every time password is used as a password on systems that do not use salts, all the hashes are the same. Using salts is like turning an eight character password into a 16 character password. Some examples will help: passwordzjJ/GP6v , passwordF2wW.oXU , passwordClq7K25A .

These look just like the passwords on many modern Unix systems would look just before being passed to the hashing function. They are obviously quite different and would create very different hashes. But two very similar salts, 1Vk8/ue0 and 2Vk8/ue0 , when combined with an otherwise identical passwords would also create very different hashes. Change any one character, passed to hashing function, and you will get a very different hash. The salt is normally stored as plaintext with the resulting hash and as available to any cracker as it is to the system.

This is not a problem. The salt must be availble to the system if the passwords are to be useable. The only purpose of the salt is to ensure that the same passwords get different hashes. Once when disk space was expensive and computers slow, salts typically only had 4096 possibilities; this was good enough to largely ensure that the same password did not have the same hash on the same computer or even in the same medium size company. The 8 character salts in wide use today have 218 trillion possibilities. There is a modest chance that even a really popular password like password has never gotten the same hash anywhere in the world on systems that use this method. Even if there are some duplicates, the chance of any one cracker ever comming across them is remote.

Ensuring that for practical purposes, every password has a unique hash prevents what are known as precomputation attacks and rainbow table attacks, which are a very specific and widely used form of precomputation attack. An excellent example of the problem of not using salts is the October 2013 compromise of Adobe and the theft of a file containing nearly 153 million user accounts with password hashes. Also, nearly a third had password hints, entered by the users, to help them remember their password (a very bad idea).

Because of the size of this file, and the tendency of most people to choose from a relatively small set of passwords, it was a assured that there would be massive duplication of passwords in this file. Graham Clueley provided an analysis of the top 50 passwords in this list. With few exceptions nearly all were familiar. Because this was one huge list from a single site, it did show some things that composite lists could not show. High in a list of site specific lists are likely to be several passwords that relate to the password list origin: company name, products, school name, etc. In this list were adobe123, photoshop, adobe1, and macromedia between 4 and 16. This was a client list; in an employee or student list, the number of passwords related to the institution would likely be higher.

In the Adobe list, because there were no salts, as soon as one password was figured out, every other matching password was known immediately. Because there were no salts, the list was huge, and also contained hints, the best approach to get many passwords quickly is to sort the list on hashes (these are large random looking strings of ordinary typeable characters). A review of many related hints together often gave the password away with almost no effort. The most common password was 123456 . If this was run through a hashing algorithm, and the hash matched the most common hash, the password to over 1,900,000 accounts would be known. Number 2 gave up over 446,000 and 3 nearly 346,000. Four and 5 over 200,000 each. Numbers 41 through 50, over 23,000 to over 21,000 each respectivly.

If I were a member of Congress, I'd introduce a law that every company doing business on the Internet, handling patient, customer, or client records on systems accessible via the Internet, or selling operating systems across state lines, be required to use salts (or a newer stronger technology) when storing passwords to assure hash uniqueness. Generally I do not think Congress should get directly involved with technology decisions, but when companies expose patient, customer and client data to attacks accross state and international boundries, and there is a huge upside with no practical downside, an exception is warranted.

Microsoft is the biggest company to willfully refuse to use salts where they are needed, with their Windows system passwords. Since the introduction of Windows NT in 1993 all subsequent systems have used the same weak password storage, without salts. As a result, every Windows system from NT, to 2000, and XP through Windows 8.1, and all server variants, store the same password, with the same hash. The only exceptions are systems using Active Directory with Kerberos and domain controllers. Even on computers that authenticate network services with Active Directory, the password for the initial local logon is stored with the same saltless method, used on most other Windows systems. I believe the only reason for this stunningly bad technical decision, was that Bill Gates, who was Microsoft's undisputed leader at the time, and involved in many technical decisions, viewed NT as a "UNIX killer" and made many decisions because they made NT look less like UNIX. The wide spread use of rainbow tables, focused mostly on Windows systems, is a development in response to the fact Windows systems, now spanning more than 20 years, can all be attacked with the same method, once the password hashes are obtained.

If a cracker has been attacking windows systems for any length of time he may have a significant collection of Windows hashes, or simply have run the 10,000 most common passwords through the Windows hashing algorithm. If I had Windows password hashes, and wanted the the passwords, instead of starting with a cracking process, I think I'd simply sort the Widows password file on the hashes, and use a small custom program that took this input and compared it to an already sorted list of previously cracked (or hashed) passwords. Someone should explain to me why this is less eficient than Rainbow tables, if it is in fact less efficient. Each match, or in a large password file, group of matches simply gets the password from the cracked file and is removed from the list that still needs to be cracked.

Tables of Times to Crack Passwords

The first table below is calculated by assuming 75,000,000 hashing operations per second. Bassed on numbers provided by Hashcat this is believed to be a reasonable figure for a desktop computer, not using a GPU. The second is calculated at 10,000 times that rate or 750 billion cracks per second, which I believe to be a plausible figure for an organized criminal activity, using a cracking network. Password lengths from 3 to 18 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 idiotic 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 alphanumeric characters; a major online brokerage service limits passwords to aplphanumeric. Why do some of the institutions with the most sensitive data have the worst password policies?

Please remember the extreme variations depending on the hashing algorithm, the attacking computer or computers, and other factors. These are plausible guesses that will fit some combinaions of many factors. For small files of uncracked passwords which are NOT salted, such as all Windows systems and many web sites, these numbers apply to the entire file. The time is likely to go up only slightly as the the number of passwords to be cracked increases. For systems which are properly salted, which include nearly all Unix like systems, these times apply to each password in the file. For example, when processing a file from a small business with 120 passwords, each second listed below becomes one minute (on average individual passwords will be cracked in half the listed times). For a password file of moderate size file with 10,800 records, each second becomes 1.5 hours. For a large file with a million passwords, each second becomes 5.79 days. In practice most crackers will start with dictionary attacks. With typical password files, most accounts will have really bad passwords. If the dictionaries start with ones based on good common password lists, most passwords will be cracked very quickly. After dictionary attacks are done, if the crackers proceed to brute force, times like these will apply to the remaining uncracked accounts. The first table is based on a single multi core CPU computer and MD5. With GPU computers the times will be much less, unless stronger algorithms are used. If faced with SHA512, bcrypt, or scrypt, these are much slower and highly iterated and do not optimize well on current GPUs.

If you have a system where you can control hash iterations, you need to find the algorithm used on your system in the oclHashcat or other online cracking benchmarks. This gives you a rough idea of what you may face. You should assume that anyone who can hack into your system has multiple GPU systems; it's safest to assume the fast cracking network or faster. If you are adding iterations, divide the number you are using by the system default. On at least current Red Hat and Debian based Linux systems, the default for SHA family algorithms is 5000 rounds. On older bcrypt systems, the defaults were 2^6 or 64 iterations for ordinary users and 2^8 or 256 iterations for root. If you are willing to wait a very noticable 1 to 2 seconds each time you login or su, you will have the most secure passwords your system supports.

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. Some passwords will fall in the first few minutes or even seconds of a run that takes days or weeks and others near the end of this same run. A select few will never be cracked.


               75 Million CPS - 1 quick desktop             
           26                 36                  52
3    0.0002 seconds     0.0006 seconds       0.002 seconds 
4     0.006 seconds      0.022 seconds       0.097 seconds 
5     0.158 seconds      0.806 seconds        5.07 seconds 
6      4.12 seconds       29.0 seconds        4.39 minutes 
7      1.78 minutes       17.4 minutes        3.81 hours   
8      46.4 minutes       10.4 hours          8.25 days     
9      20.1 hours         15.7 days           1.18 years    
10     21.8 days          1.55 years          61.1 years    
11     1.55 years         55.6 years          3.18 millennia
12     40.3 years         2.00 millennia       165 millennia
13     1.05 millennia     72.1 millennia     8,594 millennia
14     27.3 millennia    2,596 millennia   446,868 millennia
15      709 millennia   93,469 millennia      1.66 universes
16   18,438 millennia  3.36e+6 millennia      86.3 universes
17  479,379 millennia     8.65 universes     4,488 universes
18  1.25e+7 millennia      311 universes   233,380 universes
             69                      95       
 3      0.004 seconds           0.011 seconds  
 4      0.302 seconds            1.09 seconds  
 5       20.9 seconds            1.72 minutes  
 6       24.0 minutes            2.72 hours    
 7       1.15 days               10.8 days     
 8       2.64 months             2.80 years    
 9       15.0 years              2.66 centuries
10       1.03 millennia          25.3 millennia
11       71.4 millennia         2,405 millennia
12      4,924 millennia       228,463 millennia
13    339,758 millennia          1.55 universes
14       1.67 universes           147 universes
15        116 universes        13,991 universes
16      7,972 universes       1.33e+6 universes
17    550,096 universes       1.26e+8 universes
18    3.80e+7 universes      1.20e+10 universes

      750 Billion CPS - A fast network of computers
            26                  36                 52        
 3  0.000000 seconds    0.000000 seconds   0.000000 seconds  
 4  0.000001 seconds    0.000002 seconds   0.000010 seconds  
 5   0.00002 seconds     0.00008 seconds     0.0005 seconds  
 6    0.0004 seconds       0.003 seconds      0.026 seconds  
 7     0.011 seconds       0.104 seconds       1.37 seconds  
 8     0.278 seconds        3.76 seconds       1.19 minutes  
 9      7.24 seconds        2.26 minutes       1.03 hours    
10      3.14 minutes        1.35 hours         2.23 days     
11      1.36 hours          2.03 days          3.87 months   
12      1.47 days           2.44 months        16.5 years    
13      1.28 months         7.21 years         8.59 centuries
14      2.73 years          2.60 centuries     44.7 millennia
15      70.9 years          9.35 millennia    2,324 millennia
16      1.84 millennia       336 millennia  120,833 millennia
17      47.9 millennia    12,114 millennia  6.28e+6 millennia
18     1,246 millennia   436,091 millennia     23.3 universes
                   69                     95   
 3    0.000000 seconds       0.000001 seconds  
 4     0.00003 seconds         0.0001 seconds  
 5       0.002 seconds          0.010 seconds  
 6       0.144 seconds          0.980 seconds  
 7        9.93 seconds           1.55 minutes  
 8        11.4 minutes           2.46 hours    
 9        13.1 hours             9.73 days     
10        1.26 months            2.53 years    
11        7.14 years             2.40 centuries
12        4.92 centuries         22.8 millennia
13        34.0 millennia        2,170 millennia
14       2,344 millennia      206,188 millennia
15     161,759 millennia         1.40 universes
16     1.12e+7 millennia          133 universes
17        55.0 universes       12,627 universes
18       3,796 universes      1.20e+6 universes

I'm using a universe as 14 billion years.
* If you don't know what 5.88e+7 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.

If you use the second table, then 10 character passwords using the entire character set may appear safe, as it will take about 2.5 years to work through all possible passwords. Remember that is an average of 1.25 years but even with brute force attacks some passwords are likely to be found the first day. Remember the spread for slow computer, slow algorithm to fast computer to fast algorithm was 5,000,000. There is no way that I'm comfortable with a couple years for the entire set. Few people have any idea how their passwords are stored and recent events show even large software companies continue to make bad choices on password storage. I haven't used a password shorter than 12 characters in the past year on any account that matters and most are 14 or longer. The times in the tables, also assume that you have no weakness in your password that would allow any kind of dictionary attack to succeed. They are also based on estimates of something unknowable, what opponents your passwords may face, and what skills and recources they may posses.

11 characters adds some margin of safety but is another character that much harder? 12 characters from the full keyboard is almost 10,000 times stronger than 10. 12 should put your password out of the reach of almost anyone except a very few who have both great resources and great determination. You need to be someone special or have something special to warant an attempt to crack a strong 12 character password. Of course before it's cracked, anyone attempting to crack it cannot know it's a 12 character password, and if it is strong (not flawed by say a reversed rotated dictionary word) the would be cracker probably will never know what the password is. In 2001 I suggested 8 character passwords. Today, such passwords are simply inadequate for anything but throwaway accounts.

I extended the lengths of passwords covered by the tables. This was primarily to show what happens with all lower case letters. A well chosen 16.5 character, all lower case password is as strong as a good 12 character password using mixed case, digits, symbols and punctuation. That's a mathematical fact. It may not seem right but it is. Of course you cannot enter half a charcter and 16 letters is clearly weaker than a 12 character password from the 95 character set, but probably fine. I discuss strong lower case passwords on another page. This is closely related to the Words Only option in the Password Generator. 15 to 18 characters covers long passwords and short pass phrases. Short pass phrases may include capital letters, numbers or punctuation. Any of these in arbitrary and unpredictable positions substantially increases the strength of a long string of lower case letters. With pass phrases, you need to avoid obvious and common expressions just as you need to avoid dictionary words in short passwords.

Depending on the password and the brute force character order, 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. On the other hand, the superficially similar !!!!1111AAAAaaaa could not be cracked by any known method. That's 16 characters. It violates a number of common do not's regarding passwords. It uses only 2 keyboard keys, each shifted then unshifted 4 times. My password evaluator, with its original default settings, finds 4 distinct error conditions and would find more if it looked for more character repeats after finding the first. But the simple fact is, that until I displayed it publicly as a candidate for a strong password, no known cracking method could find it.

Cracking is all or nothing proposition; you get nothing for missing by one character. It would not be hard for a cracker to program all combinations of 2 to 6 character repeats in every possible combination between 6 and 20 characters. There are only 95 typeable characters and 5 different length repeats for each for 475 specific groupings. Instead of trying to figure out every possible way to fill each length, there is a much simpler way. I believe most would agree that 8, two character repeats to make a 16 character password, would not be an easy password to remember or type. Instead, I suggest a constant four groups, of 2 to 6 character repeats. Then a familiar formula applies. This is the same as a 475 "character set" for a password 4 characters long, or 475^4 = about 51 billion, a fairly small number, or about 11 minutes on a fast desktop with no GPU.

I said no known method because it is a well known that crackers try to avoid any low yield dictionaries. I doubt anyone has ever programmed a custom cracking dictionary which would have included this password, because there is no evidence these are common passwords, except as some lower case letters and some digits in short passwords (up to 8 characters). Pure brute force is not feasible at 16 characters and a 95 character set, and odd looking passwords like I used are very low yield. A few crackers may have taken dictionary attacks up to 16 characters using common long words and repeated short words with some common transformations, just to see if anything turns up.

Sequences are actually somewhat more commonly used in passwords than repeats but there are many more of these, especially as there are ASCII (alphabet and digits) and keyboard sequences and forward and reverse. Doing all of these plus the repeats would be a large dictionary, but not something that today's computers would not easily handle. At anything over 10 characters the yield is still going to be too low in 2014. If big websites keep getting hacked, websites may start forcing longer passwords with varied character sets, and if so, maybe in several years there will be some evidence of crackers trying approaches like I just covered.

What I said in the preceeding paragraphs is true of today's cracking tools, but several of these tools have been designed to accept externally programmed dictionaries. The tools themselves don't yet do these things but they can accept custom programmed dictionaries. It's also true that any password that has a structure that can be described with an algorithm can be programmed, and such passwords are small subset of all passwords of similar length and composed of randomly selected characters from the same character set as the password described by the algorithm, and the longer the password, the smaller the subset.

There are no dictionary words but 4 ones and 4 lower case a's are both common in paswords. Four exclamation marks certainly are not common; this group has never appeared in any common password list. To the best of my knowledge no one has ever before seen that exact combinations of characters. Even rainbow tables (a kind of super sophisticated dictionary attack) only go to 14 characters. The only problem with the sample password is that it has NOW been publicly suggested as an example of a strong password. Why is that a problem? Because when an example of a way to make a strong password is shown, sooner or later,someone is likely to copy it and use it exactly as it appeared. There have probably only been a few thousand examples of strong passwords in print and on the web. Smart crackers are likely to take each of these they see, and add them to one of their dictionaries to be run with no transformations.

Such a list would be very low yield compared to a common password list, but it should be a LOT better than brute force, even for 8 or 10 character passwords, and especially compared to 16 random characters. Someone my ask, what about programmed dictionaries, which I discuss later. For what? To get a more plausible grouping, we can do all 2 to 6 character sequences and repeats in groups of 4. The ASCII puctuation and symbol sequences, that hardly anyone knows, will be omitted as will the digits which repeat the keyboard, leaving only the upper and lower case alphabets. The keyboard sequences, which anyone can get, just by looking at the keyboard, will include forward and reverse as well as wrap from one line to the next. To get the weak 8 character password I started with, one set of 95 single characters will be included as both "repeats" and "sequences". This yields 1802 character groups for 1802^4 or about 10.5 trillion test passwords.

At an average size of 10 characters, plus line terminators, this is over one hundred terabytes, an awkward number for any but large organizations. It also turns out that desktops cannot create dictionaries nearly as fast as as even fast but non GPU enabled PCs can calcualte hashes. It also seems that both pure dictionary attacks (one word list without transformations) and rule based attacks (a word list with a series of rules describing word variations) do not lend themselves well to massively parallel implementations (GPUs).

In this specific case, there is an answer. It seems that GPU enabled PCs do not process a single dictionary efficiently but do combine two dictionaries, in all possible combinations efficiently. So instead of creating the whole dictionary, the dictionary creating PC creates one side of or one half of the dictionary. In this case it is 1802^2 = or 3.2 million test passwords, a number very easilly done on (a few seconds) and stored on (about 33MB) a PC. Then the same file (or if necessary, the file and a copy with a different name) is fed as two files to a GPU enabled PC in a combination attack. Every entry of the "first" dictionary is combined with every entry of the "second" dictionary. 1802^2 * 1802^2 = 1802^4, the exact result we wanted. This should take about 2 minutes depending on the algorithm used for hashing and GPU used.

Let's complicate the situation. Here are a couple more long but "simple" passwords. ertyu789@#$%DFGHJ (17 characters, all keyboard sequences, and defghz{|}~345IJKL (all ASCII sequences, which except for the "z{|}~" are pretty obvious). What about []\asd;7777777;gHIJK;3456 (25 characters: a keyboard sequence wrapping from one line to the next, seven 7's, an alphabetic sequence with odd capitalization, and a numeric sequence, all separated by semi-colons) With this last one the repeat and sequence length goes to 7, any repeat or sequence 2 characters or longer can have a keyboard shift on either or both ends, and any of 33 symbol separators may appear in 3 locations; this is 2127^7 * (2032*4) * 33^3 = 5.75e+31. The square root of this gives us the size of "half" the dictionary or 7.585e+15 test passwords. This would require well over 75,850 terabytes to store. If it were possible to get the half dictionaries to the fast cracking network, it would take 173 universes (14 billion years each) to process the combinations. Not feasible in the foreseeable future. Length makes what may at first look like bad passwords uncrackeable by any foreseeable technology, but some systems would reject them because they contain more than 2 repeat or sequence character groups. Anyone who might seriously consider trying to get such passwords would drop the idea as soon as they did the necessary calculations. After the calculations are done, no one can reasoanbly question the strength of such passwords. They may not be good passwords despite their strength; if you use several along such lines, how will you remember which goes with which account? These are only a little more memorable than truly random passwords.

Each of these specific passwords is now poor because they have been publicly displayed. I believe passwords of this type, and those that contain 3 to 5 relatively short, but unrelated words, especially if some are only 3 words along the lines of word1.longworD.word3, where longword is 7 to 10 characters, enormously increasing the potential vocabulary that needs to be included, represent a viable way to create strong passwords, for the foreseeable future. I do however recommend using a password generator, such as the one on this site will soon be, which can pick pseudo random starts, lengths, and ends to these character sequences. If you do not use a generator, then at least make a point of not starting letter sequences with abc, number sequences with 123, and keyboard sequences with qwe. Historically people who have used these kinds of sequences in passwords have overwhelmingly started them with these specific characters.

I very much doubt any cracker, in the next decade or so, will try to cover all possible sequence and repeat patterns going up to 25 characters. I do however think, that if there is any indication that long passwords or pass phrases are coming into common use, the crackers will at least try to cover the most trivial and obvious approaches to long passwords. This would include all single character passwords from 2 to 30 characters and abcdefghijklmnopqrstuvwxyz and ABCDEFGHIJKLMNOPQRSTUVWXYZ , and likely all subsets of these. It might include wraparound versions of the alphabet such as defghijklmnopqurstuvwxyzabc and maybe all single keyboard and ASCII sequences up to 15 to 20 characters. It will not likely include such variations as defgh1.klMnop.rstuvW.yz@bc . This last, is not likely to be very memorable, at least not if you have several constructed on similar lines.

Brute Force, Dictionary Comparison

The time to process a cracking dictionary is determined by 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, divided by the rate it takes to hash passwords. Complex rule sets, may generate thousands of variations per word in the dictionary. 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. The yield per each word and variation will be very low, but should be high compared to a brute force attack with the same number of encryptions.

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 Windows 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. The academic project mentioned above, using a large network of volunteer computers, has cracked stronger passwords. Things change quickly in the computer world and 15 years is a long time. (The data I used in 2001 was from the previous year.)

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 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 as well as many that looked like good passwords. If you use this bank or brokerage service and your password is not mathematically 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 reasonable in 2001 when it was written. Today, with one fast desktop, it would be less than a month, or perhaps a few seconds on a capable network.

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 may not be reliably found (depending on length) by existing technology, 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, not necessarily true.

One of the well known password crackers today includes a multilingual unabridged dictionary with 21 languages. Interestingly Chinese (or Putonghua, a standardised form of the Mandarin), Hindi, 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 are also missing. Still it's a good indication where cracking tools are going. Afrikaans is included, as were nearly all advanced 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 variations of the same characters. As the length of the word increases, the standard transformations become an ever smaller subset of the possible variations. 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 matching those 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 enough disk space to store them. Huge dictionaries must be fed directly to the cracking tool without using disk space. I'm beginning to believe that when disk space for a dictionary really begins to be a problem, that the processing power to create the dictionary, and managing the pieces of the dictionary on a network are also likely to be problematic. The available tools may not have these abilities.

Can conventional computers create dictionaries fast enough to keep up with the capablities of GPU enabled cracking computers? Probably not. Can GPU enabled computers create the programmed dictionaries? It seems likely. One of the attack modes of GPU enabled computers is the combination of two dictionaries fed to them. Creating programmed dictionaries is typically no more than assembling sets of components, words, character repeats and sequences, etc., in all possible combinations. It seems highly likely that the combination of components of programmed dictionaries, should be able to take advantage of massively parallel achitecture, whether these come from discreet disk files or internally generated arrays and other data structures. It's very possible that access to the source code would be required to combine and save preliminary dictionaries, without creating hashes.

In 2007 I could find no evidence that any cracking tools were using programmed dictionaries, but it is now clear, that every method of generating plausible passwords, is comming into use with contemporary cracking tools. Available computing power has increased to the point that these CPU intensive processes are now becoming practical. Though I cannot predict how long it will be, it seems possible passwords as we have known them, may have a finite lifespan, in which they must be replaced by a more secure technology. In 2012, typically over 90% of the passwords on compromised systems are cracked. Only a small minority use passwords that are strong enough to resist today's cracking tools. Length is the easiest way to get strong passwords. Theoretically length with arbitrary (but not random) patterns should be able to stay ahead of any technology. Will many publicly compromised systems get administrators and users to use strong passwords? If history is any indicator the answer is no.

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 actual time that a specific operating system's passwords would take to crack on a specific stand alone computer or a network of known computers.

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 stopped 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, is moved as many places to the right as the exponent indicates. Any space not provided by the available significant digits is zero filled. (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 just under 10 million. 7 is for 10 million to just under a hundred million. 9 is for one billion to just under ten billion, and 11 for 100 billion to just under one trillion, 13 for 10 to just under 100 trillion.

Copyright © 2000 - 2014 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 cgi-bin/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