Let's see how to break passwords!
We have been looking at how passwords work and how they are designed to provide security for user authentication. Check out the earlier page for those details, especially if a search engine just dropped you here. Now let's look at how to break passwords! What does that involve, and how much work does it take?
A reasonable threat is only going to attack systems where the potential benefit is greater than the expected effort required to subvert it. We can't make anything perfectly secure, but maybe we can make it secure enough.
What forms of attack are we worried about?
We must consider two types of brute-force attacks. The associated risks are very different, and operating system design details matter less with one of them. However, as this section shows, brute-force attacks just aren't practical against reasonably strong passwords (unless you are using Microsoft's LANMAN hashing). It's your choice, continue through this rather theoretical section to see the details, or jump to its conclusion and move on to the next section.
The first category is the attacker who pre-computes password hashes in advance, so an attack on an observed hash/salt value is a matter of looking up the answer. We could call this one the exhaustive pre-computed attack to emphasize the amount of computation invested before the actual attack begins.
The second category is the attacker who first observes just
a few, perhaps only one, especially interesting hash and salt
The hash and salt for the user
root on Unix
or the hash for
Administrator on Windows
would be especially interesting!
The attacker then hurries away to search for a password
that would generate that hash.
We will call this the targeted attack to emphasize how
it is limited in scope or focused on more privileged accounts.
As discussed in Part 1, where we looked at the degree to which the space of possible hash values is covered by password inputs, an attacker targeting practical systems will not have to worry about covering the entire enormous search spaces of the outputs of the MD4, MD5, and SHA-1 hash functions.
As an author and presenter of information security courses to employees of the U.S. military and government and their contractors, I have observed that 12-character passwords (based on a rich character set) is usually about the strictest requirement. Administrative accounts might need slightly longer passwords, maybe 14, at least at especially cautious organizations, but 12 is usually the upper limit. 
 Don't panic, I am not giving away secrets here! Go see public documents like the US DOD STIGs, the Security Technical Implementation Guides.
So, to focus on the threat from the more thoughtful and
realistic threat, let's assume that the strictest
password policy that probably will be encountered is:
"Passwords must contain at least
14 characters length, and must include
all four categories of characters:
upper case letters, lower case letters,
digits, and punctuation."
In other words, our theorized attacker might have to compute
the hashes for all possible 14-character strings based on the
94 printable ASCII characters, which is this many:
9414 = 4,205,231,901,698,742,834,534,301,696
That's a very large number, but the MD4 and MD5 128-bit hash output space is about 81 billion times larger and more secure hash functions have larger output spaces yet.
However, remember that if the target account is on a Windows
system with LANMAN enabled, the password is broken into
7-character chunks and all letters mapped to upper case.
Those transformed chunks are hashed, and the resulting
That means that, even using the full printable ASCII character
set, there are now only 68 possible characters (no lower-case
letters) and so
there are only 687 possible inputs to consider
for a 7-character password, and for any arbitrary password, 
enough for the first 7-character chunk and some or all of
the second one, or:
681 + 682 + 683 + 684 + 685 + 686 + 687 = 6,823,331,935,124 possibilities
 If the user enters a Windows password longer than 14 characters, the 7-character chunking is not done and LANMAN authentication is disabled for that account. So, organizations still using LANMAN will tell their users not to enter passwords longer than 14 characters.
Let's see how many password strings are possible for different lengths and character sets, and compare that to the MD4/MD5 and SHA-1 search spaces. Because of the LANMAN processing, only the boxes with the lighter yellow background are possible in a Windows environment with LANMAN enabled.
|Number of Possible Password Strings|
|Character set||Characters in string|
|Single case letters (26)||3.089×108||8.032×109||2.088×1011||5.430×1012||1.412×1014||3.670×1015||9.543×1016||2.481×1018||6.451×1019|
|Single case alphanumeric (36)||2.177×109||7.836×1010||2.821×1012||1.016×1014||3.656×1015||1.316×1017||4.438×1018||1.706×1020||6.141×1021|
|Mixed case letters (52)||1.977×1010||1.028×1012||5.346×1013||2.780×1015||1.446×1017||7.517×1018||3.909×1020||2.033×1022||1.057×1024|
|Mixed case alphanumeric (62)||5.680×1010||3.522×1012||2.183×1014||1.354×1016||8.393×1017||5.204×1019||3.226×1021||2.000×1023||1.240×1025|
|All printable ASCII minus lower case (68)||9.887×1010||6.723×1012||4.572×1014||3.109×1016||2.114×1018||1.438×1020||9.775×1021||6.647×1022||4.520×1025|
|All printable ASCII (94)||6.899×1011||6.485×1013||6.096×1015||5.730×1017||5.386×1019||5.063×1021||4.759×1023||4.474×1025||4.205×1027|
You can easily see that moving to the right in that table (lengthening the password) or moving down (increasing its complexity) increases the work required for the attacker. The best possible Windows LANMAN authentication security is easily beat by 8 or 9 character passwords based on much less diverse character sets.
For non-LANMAN systems, the above table shows that an attacker
would have to pre-compute or compute on demand an enormously
large data set.
For targeted attacks,
consider the computational power (and motivation)
available to the attacker,
the length and complexity of the password,
and the time that the password must resist attack.
As an example analysis, consider 8-character passwords
including all ASCII character classes, where there are
6.096×1015 possibilities, and imagine
that the attacker's system can calculate the hashes of
ten million potential password strings per second.
A brute force search would cover the total password
(6.096×1015 passwords) / (107 passwords/second) = 6.096×108 seconds = 19.3 years
I get about 3.6 million hashes per second on a single core of a 3.4 GHz AMD Phenom II X4 965 processor. A Raspberry Pi can do about 220,000 per second. To go much faster, use a GPU.
However, for 8-character passwords based only on lower case
letters, the required search drops to:
(2.088×1011 passwords) / (106 passwords/second) = 20,880 seconds = 5.8 hours
Increase that all lower case password to 10 characters and
the required attack time grows back to:
(1.412×1014 passwords) / (106 passwords/second) = 1.412×107 seconds = 163.4 days
As for exhaustive pre-computed attacks,
let's consider the Windows LANMAN password situation first.
To handle any Windows password, our attacker needs to handle
all strings of 1 through 7 LANMAN characters (of which there
Let's assume that our attacker is clever enough to store the
required input passwords in a table that is indexed by the
hash value (hey, look, it's a hash table!), and so the
required storage would be:
1×681 + 2×682 + 3×683 + 4×684 + 5×685 + 6×686 + 7×687 = 47,661,482,770,724 bytes
So, less than 48 terabytes. The theorized attacker able to calculate ten million hashes per second could build such a table in about 7.8 days and store it in a 48 TB storage array. An exhaustive pre-compute attack is quite feasible against Windows LANMAN passwords.
But we must also consider the effect of the salt value for non-Windows operating systems. As discussed in Part 1, the salt value was originally added to hide accidental collisions in user password choices. Even with the move to shadow password storage, the use of protocols like NIS meant that password hashes might still be observed by capturing network traffic and so it remained important to continue to hide situations of two users having identical passwords.
A second advantage of salt values became obvious with increasing computer speed: The use of a salt value vastly increases the work required for an exhaustive precompute attack on passwords (except, of course, on Windows, where there is no salt). Such an attacker would have to compute as many lookup tables as there are possible salt values, since there is no way to anticipate the salt value that will have been randomly chosen for hash of interest. We had already calculated the number of salts in Part 1:
|Salts used by various operating systems|
|Operating system||Salt bits||Number of possible salt values|
Mac OS before OX X 10.4 (ref re Mac OS)
(an empty salt)
|Unix (SunOS, Solaris 2.6 through 2.8, HP-UX, etc)||12||4,096|
|Mac OS X 10.4 and later||32||4.294×109|
|Unix (Solaris 9 and later, older Linux)||48||2.814×1014|
| Linix with Glibc
|OpenBSD with Blowfish crypt and 128-bit salts||128||3.403×1038|
Let's consider an attempted attack on an organization requiring 10-character passwords using all ASCII character classes. The required storage for a hash table of salted (non-Windows) passwords is therefore the product of three numbers:
- 10 bytes per stored password string
- The number of possible passwords in our scenario: 53,861,511,409,489,970,176
- The number of salt values for that operating system.
In other words, the required
storage using S-bit salt is:
10 × 9410 × 2S bytes
For Windows systems not using LANMAN, therefore true
10-character mixed-case passwords but no salt, the required
10 × 9410 bytes
For completeness, for Windows with LANMAN hashing still
enabled, the required storage is:
(7 × 687) + (3 × 683) bytes
 "The World's Technological Capacity to Store, Communicate, and Compute Information", Martin Hilbert and Priscila López, 10 February 2011, published online.
According to a February 2011 paper in Science , all the world's known computer storage at the time amounted to only about 295 exabytes (295×1018 bytes), hence the right-most column in the following table. There is not enough computer storage on the Earth to store a non-Windows exhaustive lookup table for 10-character passwords.
|Storage required for an exhaustive set of 10-character password hash lookup tables|
|Operating system||Salt bits (S)||Required storage in bytes||Required Earth-equivalent storage facilities|
|Windows with LANMAN||0||4.706×1013||Easily stored today in just one 47 TB storage array fitting into a medium-sized cabinet!|
| Windows without LANMAN
Mac OS before OX X 10.4
|Unix (SunOS, Solaris 2.6 through 2.8, HP-UX, OpenBSD, etc)||12||2.206×1024||7,478|
|Mac OS X 10.4 and later||32||2.313×1030||7.841×109|
|Unix (Solaris 9 and later, older Linux)||48||1.516×1035||5.139×1014|
| Linix with Glibc
This is about 5×1017 times the estimated number of stars in our Galaxy, thought to be between 2×1011 and 4×1011.
| OpenBSD with Blowfish
This is about 2×1027 times the estimated number of stars in our Galaxy, thought to be between 2×1011 and 4×1011.
Brute-force attacks against Windows are practical. Against Windows with LANMAN enabled, 47 TB of storage would support a lookup in a precomputed table.
Against non-Windows operating systems, targeted attacks are impractical if long and complex passwords are used, and exhaustive precomputed attacks would require (quite literally) astronomically more storage than available on Earth..
But don't interpret the above tables as showing that passwords cannot be broken! The above section has a lot of math but it is somewhat naïve. We need to consider passwords that people actually use.
Will it help if I change my password every 90 days? Every 60? 30?
If you use Windows, or Mac OS X before version 10.4, you have very little hope of password security because of the lack of a salt. Even with LANMAN disabled, the Rainbow Table attack described in a following section can discover well over 99% of all Windows passwords in a matter of minutes.
For non-Windows operating systems, see the above table "Number of Possible Password Strings", showing the numbers of possible passwords based on length and character types, and analyze the situation. Easy to guess passwords shouldn't be used in the first place. Well constructed passwords should be adequately resistant to brute-force search. The use of salt values makes pre-computation, including that required for building a collection of Rainbow Tables, entirely impractical.
Here is what Gene Spafford said
in his blog on 11 April 2006.
to do this search:
spaf "security myths and passwords"
if you can't easily find the original:
In summary, forcing periodic password changes given today's resources is unlikely to significantly reduce the overall threat — unless the password is immediately changed after each use. This is precisely the nature of one-time passwords or tokens, and these are clearly the better method to use for authentication, although they do introduce additional cost and, in some cases, increase the chance of certain forms of lost "password."
So where did the "change passwords once a month" dictum come from? Back in the days when people were using mainframes without networking, the biggest uncontrolled authentication concern was cracking. Resources, however, were limited. As best as I can find, some DoD contractors did some back-of-the-envelope calculation about how long it would take to run through all the possible passwords using their mainframe, and the result was several months. So, they (somewhat reasonably) set a password change period of 1 month as a means to defeat systematic cracking attempts. This was then enshrined in policy, which got published, and largely accepted by others over the years. As time went on, auditors began to look for this and ended up building it into their "best practice" that they expected. It also got written into several lists of security recommendations.
This is DESPITE the fact that any reasonable analysis shows that a monthly password change has little or no end impact on improving security! It is a "best practice" based on experience 30 years ago with non-networked mainframes in a DoD environment — hardly a match for today's systems, especially in academia!
The Chief Technologist for the U.S. Federal Trade Commission more recently wrote about how mandatory password changes are harmful. She cited a 2009 U.S. NIST publication "Guide to Enterprise Password Management" (SP 800-118), a 2009–2010 University of North Carolina study of password expiration, "The Security of Modern Password Expiration: An Algorithmic Framework and Empirical Analysis", a 2013 Carnegie Mellon University study "Measuring Password Guessability for an Entire University", a 2015 Carleton University study, "Quantifying the Security Advantage of Password Expiration Policies". These studies discovered that policies that enforce password change lead to weaker passwords. Password change reduces the impact of a successful password-guessing attack, but it makes such an attack more likely to succeed.
The physical world analogy would be an airbag system for cars that made crashes more likely to happen.
Dictionary attacks on passwords
People want to remember their passwords, and so they pick words you would expect to find in a dictionary, especially if you include local terminology or slang.
Start with the on-line dictionary used for applications for spell checking. Add to that the list of all users' names (first, middle, and last, plus nicknames), computer account names and e-mail addresses, plus their telephone extension numbers, plus all products and projects of the organization, plus all building names and street addresses and so on. Add the list of towns, townships, and counties in that state and surrounding states. Stir in all the local and regional sports teams, the names of the teams, the coaches, and the players (and if this is Indiana, go all the way down to the junior-high school level and include the last several decades). Finally, add this list of 10,000,000 passwords released by a security researcher.
That will break most of the passwords if there is no
automated enforcement of password quality,
and the vast majority will
be the word
keyboard sequences like
and witticisms like
To do a dictionary attack, get a copy of the hashes and salts (if any), and do the calculation to see if any of the strings in your augmented dictionary generate the needed salt. Once you find a match, that's what works.
For this and the attacks described below, you need the list of hashes. To get that list:
- Sniff the network traffic for NIS/NIS+ or LDAP messages from an authentication server to a Unix desktop where a user is attempting to login. This is why you should run LDAP/S, not LDAP.
I suppose you could violate file system
security and read the
/etc/shadowfile, but doing that generally requires getting
rootprivilege. Mere user passwords are of little interest at that point!
Cracking attacks on passwords
So you put in some rules forcing users to use a password that is not in the dictionary. What will they do?
Add digits and punctuation to the end:
Spell something backward:
Combine two short words, possibly with digits and
punctuation sprinkled in, maybe with one of the
words spelled backwards:
Replace some letters with digits or punctuation that
resembles those letters:
And so on. That was the basis for Alec Moffett's Crack program, also available here. Its logic was nicely expanded and wrapped in a pretty interface in the LCP Windows password cracker.
My experience has been that Crack or LCP may find over 75% of the passwords in a typical environment without strict and automatically enforced requirements on password complexity.
These are very good overviews of password cracking:
How I became a password cracker
A journalist's description of his first day cracking passwords (he broke 8,000).
Anatomy of a hack: How crackers ransack
passwords like "qeadzcwrsfxv1331?"
... and "StefoN2012", and "muffinhug92", and "Wtamu@13", and "momof3g8kids", and more. Sophisticated attacks use masking and hybrid approaches with lots of data from exposed password lists.
Password complexity rules more annoying,
less effective than lengthy ones
A light overview of the 2011 paper Of Passwords and People: Measuring the Effect of Password-Composition Policies. The really short version: the rules don't do what we would hope.
Why passwords have never been
weaker—and crackers have never
About the combination of better modeling of typical password construction with more powerful cracking hardware.
Why your password can't have
symbols—or be longer than
Pointing out that major companies have surprising arbitrary restrictions. The brokerage and banking firm Charles Schwab says passwords can only be 6, 7, or 8 characters long. AT&T restricts punctuation marks to just "-" and "_", and you can use many (but not all) vulgar words as substrings.
User-Selected Passwords Still Getting
Telling how current cracking techniques running in parallel on graphics processors can test trillions of combinations per hour. The oclHashcat-plus program can test from hundreds of thousands to tens of billions of combinations per second, depending on the hash algorithm used.
How LinkedIn's password sloppiness hurts us all
About how the continuing leaks of password hashes help us understand how humans generate passwords. There is plenty of data to analyze:
- 32 million from RockYou in 2009
- 6.4 million from LinkedIn leaked in 2012
- 24 million from Zappos in 2012
- 50 million from Evernote in 2013
- 50 million from LivingSocial in 2013
- 130 million from Adobe in 2013
- Over 30 million from Ashley Madison in 2015
- 177.5 million password hashes for 164.6 million users of LinkedIn, obtained in 2012 and leaked in 2016
Password cracking tools include:oclHashcat-plus for Linux and Windows, can use GPU hardware The Password Project Cracking tools at Packet Storm Unix Crack at Packet Storm Unix Crack at CERIAS Windows Crack LCP for Windows John the Ripper for Unix John the Ripper for Windows FSCrack (John the Ripper Windows GUI) L0phtCrack Crackerjack Slurpie Qrack Hades NTSweep Password Policy Enforcer Word lists in many languages including Croat, Finnish, Irish, Polish, ...
Also see the Windows password cracking tools listed at openwall.net. Boot disks that let you get in and reset passwords, including the NT Password and Registry Editor, John the Ripper, MDcrack, and pwdump through pwdump7.
Rainbow Table attacks on passwords
So you have disabled LANMAN authentication on all your Windows systems, and you require long and complicated passwords. Are you safe?
There is an attack based on something called a Rainbow Table. It is a space-time tradeoff, gaining lots of speed during the attack itself by pre-computing large chains of hashes. They aren't quite perfect, in that some passwords will go undiscovered, but a typical Rainbow Table may cover well over 99% of the possible password space.
Rainbow Tables are only practical against Windows, because of its lack of a salt value, and they can discover almost any password within minutes.
A non-Windows Rainbow Table attack would require as many Rainbow Tables are there are possible salts. For very old versions of Unix, that means 4,096 Rainbow Tables, each around 35 GB. More recent versions would require at least 248 or 281,474,976,710,656 of those 35 GB tables, or over 66,000 times the data storage capacity of Earth (in 2006, probably a few less now).
A Rainbow Table attack works in two stages. First, figure out which chain contains the hash of interest. Second, search forward through that chain to find the hash. The password is the value just one step before.
- Click here for the technical details of Rainbow Tables from the inventor of the technique. It's a nicely written explanation.
- Click here if you want more details, including the math.
- Ophcrack is a bootable CD with a Rainbow Table covering just the alphanumeric passwords.
- The Shmoo group has built a free Rainbow Table that covers the entire printable ASCII character set. It's enormous, a 34.5 GB download you get with BitTorrent:
- Here is how to compile the RainbowCrack tools on OpenBSD, and you may need to look at that for some suggestions on getting it to compile on recent Linux distributions.
- The Free Rainbow Tables project has some short and insightful articles.
Back to the main Security Page