Attacking Passwords on Linux, macOS, and Windows

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 to be a less attractive target.

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 values. 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. [1]

[1] 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:
94¹⁴ = 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 values stored. 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 68⁷ possible inputs to consider for a 7-character password, and for any arbitrary password, [2] enough for the first 7-character chunk and some or all of the second one, or:
68¹ + 68² + 68³ + 68⁴ + 68⁵ + 68⁶ + 68⁷ = 6,823,331,935,124 possibilities

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.

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×10¹⁵ 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 space in:
 (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 are 68). 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×68¹ + 2×68² + 3×68³ + 4×68⁴ + 5×68⁵ + 6×68⁶ + 7×68⁷ = 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:

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 × 94¹⁰ × 2^S bytes

For Windows systems not using LANMAN, therefore true 10-character mixed-case passwords but no salt, the required storage is:
10 × 94¹⁰ bytes

For completeness, for Windows with LANMAN hashing still enabled, the required storage is:
(7 × 68⁷) + (3 × 68³) bytes

According to a February 2011 paper in Science [3], all the world's known computer storage at the time amounted to only about 295 exabytes (295×10¹⁸ 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.

To Summarize:

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?

No.

If you use Windows, or macOS 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. Ask Google to do this search:
   spaf "security myths and passwords"
if you can't easily find the original:

Mandatory Password Changes Are Harmful

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"; and 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 password, keyboard sequences like 1234567 or qwerty, and witticisms like letmein.

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:

• Windows
  • Dump the hashes from the local SAM with a buffer overflow attack like pwdump (several versions exist) or fgdump.
  • Use a multi-purpose tool like Cain & Abel to get it in a variety of ways (local dump, network sniffing, etc).
• Unix
  • 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/shadow file, but doing that generally requires getting root privilege. 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: password42, letmein!
• Spell something backward: drowssap
• Combine two short words, possibly with digits and punctuation sprinkled in, maybe with one of the words spelled backwards: dogcat, dog7tac!
• Replace some letters with digits or punctuation that resembles those letters: p@55w0rd

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, both of them 1990s tools, may find over 75% of the passwords in a typical user population 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 been stronger
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 16 characters
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 Cracked
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

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.

Related tools include Troy Hunt's database of over 320 million breached password hashes. Note that it isn't the passwords themselves, but their hashes. The point is to test whether a possible password choice has been exposed in a breach. This is similar to the haveibeenpwned.com search service.

Don't use cracked passwords

Attacks use these cracking techniques because the complete brute-force search space is way too large. We only need to search the much smaller segment making up the password strings that humans select. The problem for the attacker is that we're not certain of just what that does and does not contains.

Yes, human-selected passwords do include obvious choices like password and letmein and P@55w0rd.

And, it is reasonable to say that they do not contain highly random strings that are awkward to type. However, there is no good definition of what is "random enough" or "awkward enough" to go (mostly) unused.

The risk is that previous breaches provide very good guidance on the range of human-selected passwords.

A previously breached password is very likely re-used elsewhere by the same person. And, if one person thought it was good, there's a good chance that a second person will independently think of the same thing.

U.S. NIST Special Publication 800-63-3, Digital Identity Guidelines, came out in June 2017. It states that users should not be allowed to use a password that has been discovered for any user in any breach.

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?

No.

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 Windows does not use a salt value, and an adequate Rainbow Table 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 2⁴⁸ 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. It's OK for a demo
• 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:
  • Download the Rainbow Table.
  • Read about Shmoo's project.
• 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.